CCC '20 S2 - Escape Room - Olympiads Online Judge

CCC '20 S2 - Escape Room

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 2.0s

Memory limit: 512M

Problem type

Canadian Computing Competition: 2020 Stage 1, Junior #5, Senior #2

You have to determine if it is possible to escape from a room. The room is an $M$ ~M~-by- $N$ ~N~ grid with each position (cell) containing a positive integer. The rows are numbered $1, 2, \dots, M$ ~1, 2, \dots, M~ and the columns are numbered $1, 2, \dots, N$ ~1, 2, \dots, N~. We use $(r,c)$ ~(r,c)~ to refer to the cell in row $r$ ~r~ and column $c$ ~c~.

You start in the top-left corner at $(1,1)$ ~(1,1)~ and exit from the bottom-right corner at $(M,N)$ ~(M,N)~. If you are in a cell containing the value $x$ ~x~, then you can jump to any cell $(a,b)$ ~(a,b)~ satisfying $a \times b = x$ ~a \times b = x~. For example, if you are in a cell containing a $6$ ~6~, you can jump to cell $(2,3)$ ~(2,3)~.

Note that from a cell containing a $6$ ~6~, there are up to four cells you can jump to: $(2,3)$ ~(2,3)~, $(3,2)$ ~(3,2)~, $(1,6)$ ~(1,6)~, or $(6,1)$ ~(6,1)~. If the room is a $5$ ~5~-by- $6$ ~6~ grid, there isn't a row $6$ ~6~ so only the first three jumps would be possible.

Input Specification

The first line of the input will be an integer $M$ ~M~ $(1 \le M \le 1\,000)$ ~(1 \le M \le 1\,000)~. The second line of the input will be an integer $N$ ~N~ $(1 \le N \le 1\,000)$ ~(1 \le N \le 1\,000)~. The remaining input gives the positive integers in the cells of the room with $M$ ~M~ rows and $N$ ~N~ columns. It consists of $M$ ~M~ lines where each line contains $N$ ~N~ positive integers, each less than or equal to $1\,000\,000$ ~1\,000\,000~, separated by single spaces.

For $1$ ~1~ of the $15$ ~15~ available marks, $M = 2$ ~M = 2~ and $N = 2$ ~N = 2~.

For an additional $2$ ~2~ of the $15$ ~15~ available marks, $M = 1$ ~M = 1~.

For an additional $4$ ~4~ of the $15$ ~15~ available marks, all of the integers in the cells will be unique.

For an additional $4$ ~4~ of the $15$ ~15~ available marks, $M \le 200$ ~M \le 200~ and $N \le 200$ ~N \le 200~.

Output Specification

Output yes if it is possible to escape from the room. Otherwise, output no.

Sample Input

Output for Sample Input

yes

Explanation of Output for Sample Input

Starting in the cell at $(1,1)$ ~(1,1)~ which contains a $3$ ~3~, one possibility is to jump to the cell at $(1,3)$ ~(1,3)~. This cell contains an $8$ ~8~ so from it, you could jump to the cell at $(2,4)$ ~(2,4)~. This brings you to a cell containing $12$ ~12~ from which you can jump to the exit at $(3,4)$ ~(3,4)~. Note that another way to escape is to jump from the starting cell to the cell at $(3,1)$ ~(3,1)~ to the cell at $(2,3)$ ~(2,3)~ to the exit.

Notes

The online grader begins by testing submissions using the sample input. All other tests are skipped if the sample test is not passed. If you are only attempting the first three subtasks (the first $7$ ~7~ marks), then you might want to handle the specific values of the sample input as a special case.
For the final subtask (worth $2$ ~2~ marks), if you are using Java, then Scanner will probably take too long to read in the large amount of data. A much faster alternative is BufferedReader.

Comments

-3

maranto6 commented on Dec. 31, 2023, 12:40 a.m.

DFS didn't work

DFS gave me TLE on the last two batches, no matter how many other optimizations I used. On the other hand, I managed to get 100% by using BFS with brute-force divisors search with some memo-izing. Either I did something wrong, or BFS is the only way to go. ( I used C++20 ) If anyone got full percentage with DFS, please reply.

0

PeterKolokolkin commented on Oct. 25, 2024, 9:36 p.m.

DFS is possible if you use an iterative DFS with Stack (Java) instead of using recursion. Recursion is slower because recursive depth issues. And then some optimizations include using a HashMap for the factors which you compute while reading the input (value as the key and coordinates as the factors).

0

franklincool commented on Oct. 15, 2023, 5:28 a.m. ← edit 7 →

Deques are faster than other containers when implementing queues. Also, certain approaches can get stuck in loops

0

BT commented on Jan. 12, 2023, 9:36 p.m. ← edit 2 →

Can anyone tell me why I am getting tles? https://dmoj.ca/src/5210417

15

thomas_li commented on Jan. 13, 2023, 4:37 a.m.

Your code is getting TLE because it's too slow.

0

FallenAngel commented on Nov. 16, 2021, 1:30 a.m.

I wrote "import NumPy as np" but DMOJ says I IRed... Does anyone know what's wrong? Help will be greatly appreciated!

14

Badmode commented on Nov. 16, 2021, 3:36 a.m.

Numpy is disallowed on DMOJ

10

JohnstonLiu commented on Jan. 4, 2021, 1:41 a.m. ← edit 2 →

Consider a solution starting from the bottom right to the top left if you are using BFS. Also consider an efficient way to obtain a path without factoring.

0

exoceus commented on Dec. 28, 2020, 11:16 p.m. ← edited →

Case #5 in the last batch seems to be wrong. I get correct in the CCC grader but wrong in the DMOJ grader. Or am I doing something wrong?

6

c commented on Dec. 29, 2020, 1:43 a.m. ← edited →

You invoke undefined behavior on line 25. When declaring arrays inside a function, C++ does not guarantee that the array will be filled with zeros, you should declare this array outside of main().

In addition on line 27, you should add one to your array length (and also make sure you fill that with -1) because you may access pathways[rs], which in this case would be undefined.

If you need any extra help, you can ask on https://discord.com/invite/EgJVpxz

6

lemondeath commented on Oct. 11, 2020, 5:30 p.m.

Heads up: if you have the correct algorithm on Java, you should consider running with Java 8 instead of Java 11 to get the final two points. Idk why this is the case.

37

goatMan commented on July 7, 2020, 1:55 a.m. ← edited →

Wrote CCC Jr. this year, my first CCC, and I was relatively new to competitive programming before the contest. First 4 were pretty straight forward, and then this problem stumped me with 0.5 hours remaining. Here I am today, I have a solution using backtracking, but still get TLE (Java 11). Any suggestions on how to improve the algorithm (input reading isn't an issue)?

EDIT: I rewrote my program from recursive BFS search (which I thought was just backtracking) to dynamic BFS search using a while loop and got AC on the CCC Grader, but still TLE on the last 3 subtests on DMOJ. Any tips on how to get AC here?

30

4fecta commented on July 7, 2020, 2:18 a.m. ← edited →

Cool story. If you need any help, please ask on Discord instead of in the comments.

27

goatMan commented on July 7, 2020, 5:55 a.m.

Oh, didn't know that, sorry :) Thank you for letting me know!!

-7

nope commented on April 29, 2020, 2:05 p.m.

Is it even possible to solve this without TLE in Python 3? the fastest submission has an execution time of ~8 seconds

This comment is hidden due to too much negative feedback. Show it anyway.

1

RIPRoyale commented on March 26, 2020, 7:47 p.m.

My code gives a NameError on the first case? It woks fine on the CCC Grader.

6

Xyene commented on March 26, 2020, 7:52 p.m.

Please read the tips page. In particular,

Using site functions (like exit)

The DMOJ denies access to the site module, so functions that are injected into the builtin namespace — like exit — are disallowed.

-5

devnarula commented on March 26, 2020, 3:24 a.m.

Can anyone explain why I am getting TLE at the end of Batch 6 even though I am just implementing BFS on my program (c++)

This comment is hidden due to too much negative feedback. Show it anyway.

8

Dingledooper commented on March 26, 2020, 3:42 a.m. ← edited →

It is because your BFS function contains a searchm function which runs in $\mathcal{O}(NM)$ ~\mathcal{O}(NM)~ every iteration, probably taking up to $\mathcal{O}(N^2M^2)$ ~\mathcal{O}(N^2M^2)~.

9

Ibby commented on March 26, 2020, 2:26 a.m.

TFW you spent 40 whole minutes during the CCC thinking you can only jump to adjacent cells.

-2

pblpbl commented on March 25, 2020, 10:21 p.m.

Any tips on how to not TLE even with C++?

1

askren commented on April 18, 2021, 11:29 p.m.

Hint: represent the adjacency list in the following format: vector<pair<int, int>> room[N * N];

1

ross_cleary commented on March 25, 2020, 10:31 p.m.

Having a loop to find all the factors of the number in the current cell is too slow. Try to find an approach that avoids this.

0

pblpbl commented on March 25, 2020, 11:46 p.m.

ok thanks

5

alihu264 commented on March 28, 2020, 9:21 p.m.

You could do it relatively fast if you just precompute the factors when you're taking input