You can download my codes to all problems here.
I will write a full editorial in the next few days. Now you can read hints and short solutions.
Create a variable that will denote your current distance from the North Pole. What are allowed values of this variable? When can't we go West or East?
Let x denote the initial rating (or his final rating, whatever is easier for you to think about). The information that Limak is in some division in the i-th contest gives us some inequality for x. Can you see it?
For every contest we know that the current rating is x increased by some prefix sum of c_i (changes of rating). If Limak is in the division 1, we have inequality x+prefSum >= 1900 so we have x >= 1900-prefSum. If Limak is in the division 2, we have inequality x_prefSum <= 1899 so it is x <= 1899-prefSum. From this set of inequalities, your task is to find the biggest x satisfying all of them.
Since constrains are quite low, the firework won't visit cells far away from the initial cell. There aren't that many cells that can be visited. How can we use this fact?
If the initial cell has coordinates (0, 0), we are interested only in cells with coordinates up to MAX_N * MAX_T that is equal to 30·5 = 150. So there are O(1502) interesting cells. Use backtrack with memoization. Think about possible states.
As a state you should keep: x-coordinate, y-coordinate, the current direction of this part of firework, and the recursion level (it says how much time this part will live). You can keep everything in C++ set, or use a big boolean array to make your solution faster.
The intended solution is also able to process queries of form "change the i-th digit to x". This is a big hint.
Build a segment tree to answer queries in . What should be stored in such a tree?
Imagine going from left to right over a substring, maybe removing some digits. What is important in every moment is: what prefix of "2017" we already got as a subsequence. How to apply it to segment that should be merge in the segment tree?
In the segment tree store matrices of size 5 x 5, where t[i][j] means: the minimum number of digits to remove so that if there it was already possible to get prefix of "2017" of length i, then with this segment of digits it will be possible to get prefix of "2017" of length j (i ≤ j).
The intended solution is deterministic (it doesn't use any randomization). There is just enough queries to always find the root. So, you can't waste even one query. After asking about the first vertex, you should start moving from there, asking about its neighbour and its neighbour again, till you get a leaf. After getting a leaf let's start again from the first vertex and go in some other direction, again till you find a leaf. Now you have a path between two leaves. Draw it on paper. Where you should now go, to find a root?
You should find LCA of the found path and go from there to a neighbour that wasn't yet visited. Then again go till you find a leaf (because what else could we do?). Draw on paper a situation after finding some new leaf. You should see that again we should choose LCA of some path and go in some particular direction. How many queries do we need to find the root?
We need queries at most, what happens if me always go from LCA to its parent and then unfortunately we start moving down. You are close to the solution now!
If our current LCA is close to the root (we know that when it's far away from leaves), instead of going blindly in some direction to get a leaf after ~6 queries, we should check only vertices close to the LCA. After going from LCA to its last unknown neighbour, we should check that neighbour's neighbours and also their neighbours (in total, checking all vertices withing distance 2). The root must be there! This approach needs 1 + 2 + 3 + 4 + 1 + 2 + 4 = 17 queries. Can you get rid of one more query in some easy way?
If you already used 16 queries, instead of asking about one more neighbour, you should say that it's the root. It's the last candidate so it must indeed be a root.
All paths consists of LCA and two sides. It's hard to iterate over LCA in this problem so try to iterate over length of sides.
It turns out that lengths of sides are enough to compute exact value of LCA. Find a formula on paper or see my code (the top of this page). Now you can subtract something from s and assume that we count paths with LCA equal to 1, still with fixed length of left and right sides. Now some observation is needed.
What is the sum of vertices on a path from 1 to x? It's almost 2·x, right?
It is 2·x - popcount(x) (maybe - 1 or + 1). Try to use it solve solve the problem of counting paths with LCA equal to 1 and some fixed length of sides.
If endpoints are a and b, the sum of vertices will be something like 2·a - popcount(a) + 2·b - popcount(b). Since popcounts are small, we can iterate over them. Then we know that 2·a - popcount(a) + 2·b - popcount(b) = something means 2·a + 2·b = something + popcount(a) + popcount(b), so we know how big a + b should be. What remains is to quickly solve the following problem: Count the number of pairs (a, b) with fixed length of binary representations, fixed sum and fixed total number of 1's in the binary representation.
Dynamic programming on bits.
For every query we must say if the top-right side is almost connected with the bottom-left side. Here, "almost connected" means that they would be connected after adding at most one more vertex (cell). With preprocessing, you should find CC's (connected components) in the dual problem. Remember that now from one cell you can go in 8 directions. Also find pairs of CC's that are almost connected.