PROBLEM LINKDIFFICULTYmedium PREREQUISITESrandomized algorithms, expected value PROBLEMYou are given a $N * N$ grid, which each cell contains either '.' (denoting empty cell) or '#' (denoting blocked cell). You are given a string $s$ of length $L$ consisting of characters 'L', 'R', 'U', 'D'. Let us define $ans[i][j]$ as follows. We start from the cell $(i, j)$, and apply the instructions to move from string $s$ one by one from left to right. If at some point, we end up at a blocked cell or outside of the grid, we will stop. $ans[i][j]$ will be the number of moves that we applied of the string $s$. You have to find bitwise xor of all $ans[i][j]$ for each cell $(i, j)$ of the grid. The grid is generated as follows. We choose a real number $P$, where $0 \leq P < 1$. Each cell of the grid will be blocked with probability. Also, each charater of $s$ is choosen uniformly randomly from the characters 'L', 'R', 'U', 'D'. Subtask 1$N$ is at max 10 in the subtase. We can directly apply the string at each cell $(i, j)$ to find the values of $ans[i][j]$ for all cells $(i, j)$ in at max $L$ operations. So, overall time complexity of this approach will be $\mathcal{O}(N^2 * L)$ which will be around $10^2 * 5000 = 5 * 10^5$ opeartion per test case. Subtask 2$P = 0$. It means that all the cells in the grid are empty. For each cell $(i, j)$, we can use binary search to find $ans[i][j]$. We binary search over length $l$ (i.e. $0 \leq l \leq L$), and check if we apply the first $l$ characters of $s$, are we still inside the grid? You can check it in $\mathcal{O}(1)$ after having a preprocessing step of $\mathcal{O}(L)$. We compute the the minimum and maximum $x$ and $y$ coordinates that one will go if one starts from a cell $(0, 0)$ in an infinite grid for each $l$.
Time complexity of this algorithm is $\mathcal{O}(L + N^2 \log{N})$. Subtask 3$P > 0.1$, i.e. around 10% of the cells of the grid are blocked. There are around $N^2 = (10^3)^2 = 10^6$ cells, out of which $10^5$ will be blocked. What's the expected value of $ans[i][j]$ for a cell $(i, j)$. For now let us assume that the grid is infinite. We want to check what should be the expected length of move from a cell (say $(0, 0)$) before encountering a blocked cell. You can see that expected length will be around $\frac{L}{10}$. We use the direct bruteforce approach used in subtask 1 to solve this subtask too. Let us estimate the time complexity of it. We can see that expected value of $ans[i][j]$ is around $\frac{L}{10} = 500$. So, the overall time complexity will be $\mathcal{O}(N^2 * 500) = 5 * 10^8$. The actual number of moves will be lesser than this because of restriction of not being able to due to moving out of the grid. Full subtaskNow, only case that's left to handle $P < 0.1$. It means that there are a few blocked cells. For each blocked cell we want to mark empty cells that starting from them would result in a crash in this blocked cell (assuming for a moment that there is no other blocked cells). From this cell, we apply the mirror of the string $s$. If the character in $s$ is 'L', then the mirror string will have 'R', and vice versa. Similarly for the characters 'U' and 'D'. We mark the empty cells that we can visit from this cell in the grid by applying the opposite of string $s$. This way we can find the empty cell from which if we apply some $x \leq L$ move of the string, we reach to the blocked cell. For example, if the string $s = RRU$, then we apply the mirror string $LLD$. Let the blocked cell be $(10, 10)$, we move to $(10, 9)$ to $(10, 8)$ and $(11, 8)$ by applying the string LLD. We see that starting from cell $(10, 9)$ we encounter a blocked cell after 1 move by making a move R. Similarly, from cell $(10, 8)$ in two moves RR, we will reach the blocked cell $(10, 10)$. Time complexity of this algorithm will be number of blocked cells multiplied by $\mathcal{O}(L)$. We can see that number of blocked cells can be at max $\mathcal{O}(\frac{N^2}{10})$ in this case. So overall time complexity is $\mathcal{O}(\frac{N^2}{10} \cdot L)$ = $\mathcal{O}(10^5 * 5000) = 5 \cdot 10^8$. SETTER'S SOLUTIONTESTER'S SOLUTION
This question is marked "community wiki".
asked 16 Apr '17, 09:20

I solved this in a simple way. I didn't need to use different techinques to different subtastks. Maybe it is worth mention and someone will find it useful. Anyway here is the solution: 1) for each cell we compute the manhattan distance to the nearest wall (one simple BFS) 2) for each cell we use bruteforce + "shortcuts". Which means: if the nearest wall is for example 10 cells away then we can do 9 steps safely. So we do 9 steps at once. (Doing many steps at once can be implemented using prefix sums). answered 18 Apr '17, 01:23

I had a different solution that worked fine for all subtasks and is easy to understand imho:
Optimal window size depends on number of blocked cells, but 11x11 seems to work well for all choices. This could also further be optimized by using more than a single window size. We could also use similar techniques to do a quick prescan of the grid first and find the minimum number of moves that are possible for a whole block of cells. I didn't implement this and it wasn't required for AC, but it should have provided a nice additional speedup. Link to solution: https://www.codechef.com/viewsolution/13256961 answered 18 Apr '17, 01:51

When i implemented a solution for the problem in a straight forward manner.. I passed subtask 1. For subtask 2, given the string, i will try to find the maximum region, ie, minx, miny, maxx and maxy.. for each cell i,j if i+minx >= 0 and i+maxx < n and j+miny >= 0 and j+maxy < n then answer is XORed with length of the string.. this easily passes subtask 2.. Then I tried to use the same technique for subtask 3.. ie, if in the if there is any '#' in the region use brute force else just XOR steing length with answer.. with this improvement passed subtask 3 but not subtask 4.. For subtask 4, i used sqrt decomposition technique.. string is broken into sqrt(l) strings maximum region for each string is obtained.. and implemented as before.. Success!! $${Time\ Complexity : O(n^2sqrt(l)) = 10^6*70}$$ $${Space\ Complexity : O(n^2sqrt(l)) = 10^6*70 = 285.5M}$$ refer to my solution here. https://www.codechef.com/viewsolution/13338447 answered 17 Apr '17, 16:14

Links to setter's solution and tester's solution are not working, please fix this. answered 17 Apr '17, 21:19

According to the editorial each subtask needs to be handled separately.Ain't there any general solution for solving all the subtasks at once? answered 19 Apr '17, 01:38

All those who are not able to access the problems in the practice section, can still submit solutions and get them judged. You can read the problem at the contest link. To submit, go to https://codechef.com/submit/RNDGRID. Replace answered 20 Apr '17, 19:23

In the 3rd subtask is the expected calculation considering that we will visit each state(i,j) only once?Isn't it possible we are going over same state multiple times which isn't blocked. answered 17 Apr '17, 17:36
