I was the writer for the Round 2. I'm very sad that the contest platform failed and you couldn't do your best solving them -- for me it's also sad as my work on the problems is now wasted. Hopefully you liked the problems themselves.
Here are the problem statements:
- A http://pastebin.com/raw.php?i=U8SfbSL8
- B http://pastebin.com/raw.php?i=bAi07eMm
- C http://pastebin.com/raw.php?i=R72vqKkk
- D http://pastebin.com/raw.php?i=Ar5CmJ8j
- E http://pastebin.com/raw.php?i=wiCtb0ab
- F http://pastebin.com/raw.php?i=iaMnb9cs
And below are brief solution ideas. Ask if anything is unclear.
A (ascending the stairs)
Dynamic programming in O(n).
Let W[x] be the number of ways to climb the first x steps of the stairs. (We will call that "state x".)
W[n] is the answer we want.
For each x, let y be the lowest state that we can go directly from state y to state x -- i.e., the sum H[y]+...+H[x-1] is still <= m. Then W[x] is simply the sum of W[y] through W[x-1].
Using two pointers, we can find the right y for each x in linear time. We can also maintain the sum of the Ws that corresponds to the current y and x.
B (back to the start)
Compress the coordinates. Then, realize that the optimal curve never has to pass through a corner of the unit square grid (we can always go around it on either side -- if the corner is available, so are the four sides that meet there). Thus we can turn this continuous problem into a discrete one and solve it using BFS. Consider the unit squares around the curve. Build a graph where two unit squares are adjacent iff they share a side and the curve doesn't use that side. Then, start the BFS from all four unit squares adjacent to the start and check whether you can reach at least one of the four squares adjacent to the end.
Generating good test data for this is a lot of fun :)
C (candy game)
This is known as misère NIM. Each color represents a pile in the game of NIM, and the number of candies of that color is the size of the pile.
The optimal strategy is the same as in the classical NIM: the losing positions are precisely those where the xor of pile sizes is zero. But there is one exception: if all pile sizes are 0 or 1, it is reversed: the ones with an odd number of 1s are losing.
Here is a proof: For situations where the largest pile is 1 it is obvious. In all situations where the largest pile has more than 1 token, the player who has the winning strategy in classical NIM can follow the same strategy in this NIM. This player must be the one who will eventually make the move that will lead into a situation with all pile sizes 0 or 1. And at this moment, the player may choose the opposite: if the winning move in classical NIM was to decrease the current pile to 0 she will decrease it to 1 and vice versa.
D (divisibility from last digits)
Obviously, we have to look at the k-th digit (zero-based index from the right) if and only if 10^k is not a multiple of d. Hence, we are looking for the smallest k such that d divides 10^k. This is only possible if d is of the form 2^a * 5^b, and the answer is max(a,b). Note that a can be at most 59. (Some solutions probably failed because they tried too few values for a, instead of simply dividing d by 2 while it still goes.)
E (exactly divisible by sum of largest digits)
The standard first trick is to write the answer as solve(b+1)-solve(a) where solve(x) counts all solutions in [100,x).
To implement solve(x), use three cycles to run through all possibilities for the three largest digits, and then count all numbers with those three largest digits. (I used two cases: I separately count those with fewer than x digits and then for each prefix of x I count those that are smaller than x in the last digit of the prefix. For example, if x is "1234567", one of the subproblems will be to count all numbers of the form "12341..".)
The core of the solution is a memoized recursive function go(a,b,c,found,rem,left) that generates the number from the left to the right. It has the following arguments:
- a,b,c are the three largest digits, with a>=b>=c. E.g., a,b,c = 9,7,7
- found is a bitmask stating which of them I've already used. E.g., found=5 means that a,c already appeared but b didn't.
- the number I have generated so far gives the remainder rem when divided by a+b+c
- left is the number of digits I still have to generate
Note that once I fixed a,b,c I can maintain the remainder modulo a+b+c while generating the number, and I also know that all digits other than a,b,c must be less than or equal to c.
The simplest O(n log^2 n) algorithm by Patrascu and Patrascu, described in this paper, should be sufficient. (There are faster known algorithms but I didn't want to make the problem too hard.)