PROBLEM LINK
DIFFICULTY
medium
PREREQUISITES
randomized algorithms, expected value
PROBLEM
You 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.
int minx[L + 1], maxx[L + 1];
int miny[L + 1], maxy[L + 1];
x = 0, y = 0;
for l = 0 to L:
minx[l] = min(minx[l], x);
maxx[l] = max(maxx[l], x);
miny[l] = min(miny[l], y);
maxy[l] = max(maxy[l], y);
if (l < L):
Change (x, y) according to s[l].
// is it possible to make a move of length l from cell (x, y)
def check(x, y, l):
mnx = x + minx[l];
mxx = x + maxx[l];
mny = y + miny[l];
mxy = y + maxy[l];
if any of mnx, mxx, mny, mxy is less than 1, or greater than N, then return false;
Otherwise true.
def ans(x, y):
// do a binary search over l, such that check(x, y, l) is true;
lo = 0, hi = L, ans = 0;
while (lo <= hi):
mid = (lo + hi) / 2;
if (check(x, y, mid)):
ans = mid;
lo = mid + 1;
else:
ans = mid - 1;
return ans;
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 subtask
Now, 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.