CCC '20 S2 - Escape Room

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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-by-N grid with each position (cell) containing a positive integer. The rows are numbered 1,2,\dots,M and the columns are numbered 1,2,\dots,N. We use (r,c) to refer to the cell in row r and column c.

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

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

Input Specification

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

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

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

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

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

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 (1,1) which contains a 3, one possibility is to jump to the cell at (1,3). This cell contains an 8 so from it, you could jump to the cell at (2,4). This brings you to a cell containing 12 from which you can jump to the exit at (3,4). Note that another way to escape is to jump from the starting cell to the cell at (3,1) to the cell at (2,3) to the exit.

Notes

  1. 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 marks), then you might want to handle the specific values of the sample input as a special case.

  2. For the final subtask (worth 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
    goatMan  commented on July 6, 2020, 9:55 p.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?


    • 9
      4fecta  commented on July 6, 2020, 10:18 p.m.

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


      • 4
        goatMan  commented on July 7, 2020, 1:55 a.m.

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


  • -5
    jerryzhou196  commented on May 22, 2020, 1:01 a.m. ← edited

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


  • -7
    linyirun  commented on May 17, 2020, 5:40 p.m. ← edited

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


  • -2
    wanghaochen0519  commented on May 13, 2020, 1:14 a.m. ← edited

    Can someone look through my code, I keep getting TLE on the last batch.

    I have used a BufferedReader, so I am not sure what the problem actually is!

    Thank you very much!

    Edit: Nvm I found the problem.


  • -2
    p2  commented on May 10, 2020, 9:13 a.m. ← edited

    Someone help pls, what is wrong with my code?

    EDIT: NEVERMIND


  • -1
    boolean  commented on May 1, 2020, 7:31 p.m. ← edit 4

    My code outputs "yes" when I run the sample input on my IDE but it WA's and prints "no" to the same sample input when I submit it. Any suggestions?

    https://dmoj.ca/submission/2064841

    EDIT: Solved. It was a simple variable error.


    • -6
      KatuRaki  commented on May 1, 2020, 8:18 p.m.

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


  • -5
    nope  commented on April 29, 2020, 10:05 a.m.

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


  • 29
    Kevy3030  commented on April 4, 2020, 2:41 p.m. ← edit 3

    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.


    • 10
      Togohogo1  commented on May 7, 2020, 12:31 p.m. ← edit 2

      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.


    • 9
      Togohogo1  commented on April 5, 2020, 10:05 a.m.

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


  • -3
    kevze  commented on March 28, 2020, 5:18 p.m.

    I'm having trouble staying below the memory limit. Can someone give me a hint?


  • -3
    detas  commented on March 27, 2020, 11:07 p.m.

    how to not tle on batch 7?


    • 0
      Ibby  commented on March 28, 2020, 8:29 p.m.

      Your getPairs function looks through 1 to N for every space added to the queue which is too slow. Try finding a faster way to look for factors.


  • 1
    RIPRoyale  commented on March 26, 2020, 3:47 p.m.

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


    • 4
      Xyene  commented on March 26, 2020, 3: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.


  • -2
    devnarula  commented on March 25, 2020, 11:24 p.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++)


    • 5
      Dingledooper  commented on March 25, 2020, 11:42 p.m.

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


  • -1
    Ibby  commented on March 25, 2020, 10:26 p.m.

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


  • -5
    thomas_li  commented on March 25, 2020, 7:01 p.m. ← edit 2

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


  • 2
    harry7557558  commented on March 25, 2020, 6:49 p.m.

    AC in CCC and TLE on DMOJ. (finally solved it)


  • 0
    pblpbl  commented on March 25, 2020, 6:21 p.m.

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


    • 1
      ross_cleary  commented on March 25, 2020, 6: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.


      • 1
        pblpbl  commented on March 25, 2020, 7:46 p.m.

        ok thanks


        • 2
          alihu264  commented on March 28, 2020, 5:21 p.m.

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