RNDGRID - Editorial

PROBLEM LINK

Practice
Contest

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.

SETTER’S SOLUTION

Setter

TESTER’S SOLUTION

Tester2

4 Likes

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

1 Like

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.

The problem is not visible in the practice section. Would be grateful if it is made visible as soon as possible. Thank you.

1 Like

Links to setter’s solution and tester’s solution are not working, please fix this.

1 Like

@admin Please add problem to practice section.

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).

3 Likes

I had a different solution that worked fine for all subtasks and is easy to understand imho:

  1. Preprocess the moves string to directly skip over moves where we visit cells we have already visited before. This reduces the number of cells we have to check significantly as the randomly generated movement tends to often revisit the same cells. (A 5000 random moves string visits around 1600 different cells.)
  2. Preprocess the grid to generate a second grid where each cell indicates if there is any blocked cell within a window of 11x11 cells.
  3. If we know that within a 11x11 window no cell is blocked, we can often quickly skip over many moves. If many cells are blocked, this will rarely happen, however, in that case we will quickly bump into a blocked cell anyway. We can add this information to our preprocessed moves list. If no cells within a 11x11 area is blocked, skip over the next few moves that are guaranteed to be valid.

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

2 Likes

According to the editorial each subtask needs to be handled separately.Ain’t there any general solution for solving all the subtasks at once?

1 Like

exactly my solution

@admin ???

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 RNDGRID with the problem code for the problem whose solution you wish to submit.

1 Like