##### 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 -by- grid with each position (cell) containing a positive integer. The rows are numbered and the columns are numbered . We use to refer to the cell in row and column .

You start in the top-left corner at and exit from the bottom-right corner at . If you are in a cell containing the value , then you can jump to any cell satisfying . For example, if you are in a cell containing a , you can jump to cell .

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

#### Input Specification

The first line of the input will be an integer . The second line of the input will be an integer . The remaining input gives the positive integers in the cells of the room with rows and columns. It consists of lines where each line contains positive integers, each less than or equal to , separated by single spaces.

For of the available marks, and .

For an additional of the available marks, .

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

For an additional of the available marks, and .

#### Output Specification

Output `yes`

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

.

#### Sample Input

```
3
4
3 10 8 14
1 11 12 12
6 2 3 9
```

#### Output for Sample Input

`yes`

#### Explanation of Output for Sample Input

Starting in the cell at which contains a , one possibility is to jump to the cell at . This cell contains an so from it, you could jump to the cell at . This brings you to a cell containing from which you can jump to the exit at . Note that another way to escape is to jump from the starting cell to the cell at to the cell at 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 marks), then you might want to handle the specific values of the sample input as a special case.

For the final subtask (worth 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

BFS is kinda faster i think, and a hint is deque O_<

This comment is hidden due to too much negative feedback. Click here to view it.

Deleted Comment

Can someone explain to me how I can fix my code for this problem?

Can someone take a look at my code? I am getting TLE on most cases and I have no idea why.

Don't trust me on this, but to make mine not TLE I think I switched from BFS to DFS

You can solve this problem using either BFS or DFS.

This comment is hidden due to too much negative feedback. Click here to view it.

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?

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://slack.dmoj.ca

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.

Great problem. First OI problem that I solved. Really happy!!!

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?

I am kind of stuck on this problem. I know the backtracking concept, but I don't know how to set everything up without going overtime

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

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

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

I feel like this should be a 10p, considering 2018 J5 - Choose your own path was a 7p this should be worth a bit more - along with implementing a graph searching algorithm you had to efficiently compute factors, and the actual implementation was more sophisticated then simply using a standard graph adjacency representation. A fair bit of TLEing too, from what I've seen and heard.

Well, you got your wish now.

Well since knight hop is now 7 points, it would be fair for this to be worth 10 now. You might be able to get your wish.

Graph problems are quite uncommon and usually a bit more difficult to be CCC S2s, but this problem is also a J5. However, I do agree with you. (This in fact is the first graph theory S2).

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

Please read the tips page. In particular,

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

It is because your BFS function contains a

`searchm`

function which runs in every iteration, probably taking up to .TFW you spent 40 whole minutes during the CCC thinking you can only jump to adjacent cells.

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

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

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.

ok thanks

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