## DMOPC '20 Contest 5 P3 - Bottom Row

View as PDF

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 grid with blocked cells and the others open. The cells are indexed with as the bottom-left cell, and 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 and will not be blocked. There is currently a robot at cell , and you want to get it to cell . The robot reads a string of characters inputted by the user to determine its movements.

For a string of characters , the robot will read the characters from left to right. If the character is:

• D, the robot will move from cell to cell .
• U, the robot will move from cell to cell .
• L, the robot will move from cell to cell .
• R, the robot will move from cell to cell .

Your string should only contain the 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 which moves the robot from to , or determine that no such string exists. If multiple shortest strings exist, print the lexicographically smallest one. A string is lexicographically smaller than a string of the same length if for some , for all , and .

#### Input Specification

The first line contains integers and , as described in the problem statement.

The next lines each contain integers and , representing that cell 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 and will not be blocked.

#### Output Specification

If no string can move the robot from to , output IMPOSSIBLE.

Otherwise output a string , 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 to , 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 to .

• commented on April 29, 2021, 10:13 a.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>.

• commented on April 29, 2021, 11:11 a.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.

• commented on April 29, 2021, 11:07 a.m. edited

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

https://discord.com/invite/EgJVpxz

• commented on April 29, 2021, 10:55 a.m.