This was not a good match for me, I got pretty confident after solved the problem A relatively fast. I was careless in the problem B and forgot to consider an important case. I spend the rest of the match looking at problem C.
A. Funky Numbers
http://codeforces.com/contest/192/problem/A
In this problem we need to tell if a certain number can be expressed as the sum of two triangular numbers. At first the constraint of \(N \leq 10^{9}\) seems kind of scary... The key observation is that there are just 44,720 triangular numbers under the \(10^{9}\). Knowing this we can construct a sorted list of all triangular numbers under \(N\). The only question that remains is how to search efficiently into into this sorted list, the answer is simple binary search. For each number in our list greater or equal to \(N\) we used binary search to look for the number \(N - A[i]\) in the list, if we find a match we are done, which means it's possible to express this number as the sum of two triangular numbers, otherwise, is not. To make things clear let's check an example:
\(N = 256\)
\(T = \{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, \\ 190, 210, 231, 253, 276, ...\}\)
\(X = 256 - T[0] = 256 - 1 = 255\)
\(binary\_search(X)\)
255 is not in the list; means 1 + 255 is not the sum of two triangular numbers.
255 is not in the list; means 1 + 255 is not the sum of two triangular numbers.
\(X = 256 - T[1] = 256 - 3 = 253\)
\(binary\_search(X)\)
253 is in the list; means that 256 can be expressed as the sum of two triangular numbers 256 = 253 +3.
253 is in the list; means that 256 can be expressed as the sum of two triangular numbers 256 = 253 +3.
B. Walking in the Rain
http://codeforces.com/contest/192/problem/B
You are given a one-dimensional grid, each cell of the grid has a threshold of the amount of days can last, you need to move your troops along the grid, from position \(1\) to \(N\). From the \(i\)-th cell your troops are just allowed to move to the cells \(i + 1\) or \(i + 2\) as long as the cell is not destroyed. Output the maximum number of days that your troops can walk along this grid.
My guess is that on purpose the writer kept the constraints low enough to allow \(O(N^{2})\) solution to pass. During the match I was not thinking I tried to simulate the process... I forgot to consider the case where the troops where in the initial position. A better solution was to notice that we can't jump more that two cells at time, this means that if we get block by two destroyed cells next to each other we are not going to be able to cross them. This means that for each pair of cells we calculate their maximum destroy time threshold and for all this value we stay with the minimum of all the pairs.
My guess is that on purpose the writer kept the constraints low enough to allow \(O(N^{2})\) solution to pass. During the match I was not thinking I tried to simulate the process... I forgot to consider the case where the troops where in the initial position. A better solution was to notice that we can't jump more that two cells at time, this means that if we get block by two destroyed cells next to each other we are not going to be able to cross them. This means that for each pair of cells we calculate their maximum destroy time threshold and for all this value we stay with the minimum of all the pairs.
No comments:
Post a Comment