DMOPC '20 Contest 5 P3 - Bottom Row - DMOJ: Modern Online Judge

DMOPC '20 Contest 5 P3 - Bottom Row

Points: 15 (partial)

Time limit: 2.0s

Memory limit: 256M

Python 512M

Author:

Problem types

After typing continuously for three days and four nights, you've managed to increase your typing speed to a sizeable 35 WPM. However, you've gotten quite bored of transforming strings, so a quick scroll through the internet has led you to another typing game for a quick breather. In this game, you are given an $N \times N$ ~N \times N~ grid with $K$ ~K~ blocked cells and the others open. The cells are indexed with $(1, 1)$ ~(1, 1)~ as the bottom-left cell, and $(N, N)$ ~(N, N)~ as the top-right cell. All cases will satisfy the constraint that no two blocked cells are on the same row or column, and the cells $(1, 1)$ ~(1, 1)~ and $(N, N)$ ~(N, N)~ will not be blocked. There is currently a robot at cell $(1, 1)$ ~(1, 1)~, and you want to get it to cell $(N, N)$ ~(N, N)~. The robot reads a string of characters inputted by the user to determine its movements.

For a string of characters $S$ ~S~, the robot will read the characters from left to right. If the $i^\text{th}$ ~i^\text{th}~ character is:

D, the robot will move from cell $(r, c)$ ~(r, c)~ to cell $(r-1, c)$ ~(r-1, c)~.
U, the robot will move from cell $(r, c)$ ~(r, c)~ to cell $(r+1, c)$ ~(r+1, c)~.
L, the robot will move from cell $(r, c)$ ~(r, c)~ to cell $(r, c-1)$ ~(r, c-1)~.
R, the robot will move from cell $(r, c)$ ~(r, c)~ to cell $(r, c+1)$ ~(r, c+1)~.

Your string should only contain the $4$ ~4~ characters listed above, and the robot should never attempt to move outside the grid or move into a blocked cell. As fast and efficient as ever, your goal is to find the shortest string of characters $S$ ~S~ which moves the robot from $(1, 1)$ ~(1, 1)~ to $(N, N)$ ~(N, N)~, or determine that no such string exists. If multiple shortest strings exist, print the lexicographically smallest one. A string $x$ ~x~ is lexicographically smaller than a string $y$ ~y~ of the same length if for some $j$ ~j~, $x_i = y_i$ ~x_i = y_i~ for all $i < j$ ~i < j~, and $x_j < y_j$ ~x_j < y_j~.

Constraints

$2 \le N \le 10^6$ ~2 \le N \le 10^6~

$0 \le K \le N$ ~0 \le K \le N~

$1 \le r_i, c_i \le N$ ~1 \le r_i, c_i \le N~

Subtask 1 [30%]

$2 \le N \le 2 \times 10^3$ ~2 \le N \le 2 \times 10^3~

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains $2$ ~2~ integers $N$ ~N~ and $K$ ~K~, as described in the problem statement.

The next $K$ ~K~ lines each contain $2$ ~2~ integers $r_i$ ~r_i~ and $c_i$ ~c_i~, representing that cell $(r_i, c_i)$ ~(r_i, c_i)~ is blocked. These cells will all be distinct and heed the constraints given in the statement. Specifically, no two blocked cells are on the same row or column, and the cells $(1, 1)$ ~(1, 1)~ and $(N, N)$ ~(N, N)~ will not be blocked.

Output Specification

If no string can move the robot from $(1, 1)$ ~(1, 1)~ to $(N, N)$ ~(N, N)~, output IMPOSSIBLE.

Otherwise output a string $S$ ~S~, as described in the problem statement.

Sample Input 1

3 2
3 1
2 3

Sample Output 1

RUUR

Explanation for Sample 1

The following diagram depicts the given grid, with # denoting blocked cells and . denoting the rest.

#..
..#
...

It can be proven that RUUR is the shortest string that moves the robot from $(1, 1)$ ~(1, 1)~ to $(3, 3)$ ~(3, 3)~, and it is also the lexicographically smallest string among all shortest strings which achieve the same goal.

Sample Input 2

2 2
1 2
2 1

Sample Output 2

IMPOSSIBLE

Explanation for Sample 2

The following diagram depicts the given grid, with # denoting blocked cells and . denoting the rest.

#.
.#

It can be proven that no string can move the robot from $(1, 1)$ ~(1, 1)~ to $(2, 2)$ ~(2, 2)~.

Comments

4

suguruchhaya commented on April 29, 2021, 2:13 p.m. ← edited →

Riolku (hope you are getting pinged for this.) I am struggling so much with this problem. I have been debugging/optimizing for more than 5 hours (just look at my Python3/PyPi submission history) but I just don't seem to be able to pass the second test case. I have came to the point where I cannot back down and I just have to pass that damn test case. I looked at all submissions and your have an accepted PyPy solution. Can you share it with me? It would be great if you can reply to this comment or send it to me at <email removed>.

6

sushi commented on April 29, 2021, 3:11 p.m. ← edit 3 →

He is not getting pinged for this, and I highly recommend you to join the dmoj discord so you may ask for help in the help channel. However, I ask you to be careful about pinging people (especially admins) as some of them do not wish to get pinged for things such as this. Alternatively, you can read the editorial that is present for this problem as suggested by noYou, which explains the solution(s) to this problem.

3

noYou commented on April 29, 2021, 3:07 p.m. ← edited →

Also he is not getting pinged, join the dmoj discord to ping him :blobbusiness:

https://discord.com/invite/EgJVpxz

5

noYou commented on April 29, 2021, 2:55 p.m.

Did you read the editorial?

4

suguruchhaya commented on April 29, 2021, 7:55 p.m. ← edit 2 →

I read the editorials. I see you are trying it right now. Can you send me your discord? Your discord on your profile page isn't working... My discord is Suguru Chhaya#8465

6

DM__Oscar commented on April 29, 2021, 5:04 p.m.

I read the editorial and still struggled :( :monkey: :wheelchair:

I had to ask edward for help :edwardweary: