Jumping

View as PDF

Submit solution


Points:17
Time limit:0.6s
Memory limit:64M
Authors:

Problem type

Allowed languages
C, C++

Pepe the frog needs to jump across a river while only stepping on some stones! He needs to jump from column 1 to column N (left to right in the input). Rock i means the rock on row i. However, jumping from row i to j takes (i-j)^2 time.

Input

The first line of the input contains two integers, N and C, the number of columns and the number of positions of rocks.

Each subsequent C lines of the input contains of a string of N 0s and 1s. A 1 on line i (starting from 2nd line) on column j (both 0-indexed) indicates the rock j is present in column i, a 0 indicates that rock j is not present.

Output

Output the minimum amount of time taken to jump to the end.

You are guaranteed there is at least one possible way to jump to the end.

Constraints

Subtask 1 (10%) 1\le N,C\le7

Subtask 2 (5%) 1\le N,C\le100

Subtask 3 (20%) 1\le N,C\le500

Subtask 4 (20%) 1\le N,C\le750

Subtask 5 (45%) 1\le N,C\le2000

Sample Input 1

5 3
11100
00011
11111

Sample Output 1

0

Sample Input 1 Explanation

You don't need to jump, just use rock 3 throughout.

Sample Input 2

5 5
10000
01000
00100
00010
00001

Sample Output 2

4

Sample Input 2 Explanation

Start from rock 0, change to rock 1, change to rock 2, etc. Each of them takes 1 time because they are adjacent.


Comments


  • 0
    Cueball1234
     commented on Sept. 3, 2017 edited

    TLE

    My solution has an execution time of O(NClogC), which should be fast enough. However, I am TLEing. Is there maybe a reason for this occurring? Thank you!

    Edit: I changed a couple parts to reduce the execution time and it worked, but it is still really weird why my initial O(NClogC) TLEd. Some suggestions on why my initial solution TLEd would be much appreciated. Thanks!


    • 1
      Xue_Alex
       commented on Sept. 4, 2017 edited

      With a sub 1 second time limit on the problem, it's a possibility that you got a slow judge on some submissions and a fast judge on other submissions. Normally that wouldn't be the difference between an AC and TLE, the tight time limit probably caused that, even though there was nothing wrong with your code.


      • 0
        Cueball1234
         commented on Sept. 4, 2017

        Ah yes, very true. But it is still weird, since NClogC is on the order of magnitude of 40 million operations. I am not too sure about this, but can't a computer do about 1 billion operations in a second? Thank you!


  • 1
    Cueball1234
     commented on Aug. 31, 2017

    Sorry, just to clarify, does the frog have to visit every column or is the frog technically allowed to jump from a rock in column 1 directly to a rock in column N?

    e.g.

    1 0 1
    0 1 0

    Is the answer 2 or 0?

    Thanks!


    • 1
      Xue_Alex
       commented on Sept. 1, 2017 edited

      The input

      3 2

      101

      010

      Gave me 2, so I think the frog does need to visit each column.

      Edit: format


      • 1
        Cueball1234
         commented on Sept. 1, 2017

        Awesome, thank you for the confirmation!


  • 0
    kobortor
     commented on Jan. 7, 2017
    Time limit

    The time constraint for this question is quite strict. It is not guaranteed to be solvable by languages other than C++. Even then you will need quite a bit of constant optimization to pass (assuming you have the optimal time complexity).


  • 0
    gloomcore
     commented on Jan. 7, 2017 edited
    Some clarification will be helpful

    Can frog jump back or just forward? And can frog move between different stones within the same column?

        11100
        00100
        00111

    Is answer for this test is 2?


    • 0
      bruce
       commented on Jan. 7, 2017

      Based on my submission, the frog can only jump forward. The case you provided is the same as

      11000
      00100
      00011

      and the answer is 2.


      • 0
        gloomcore
         commented on Jan. 9, 2017 edited

        Thanks, a lot Bruce, it will help me clarify task. I wanted to check if frog can jump between diffrent rows on the same column. I mean, that if frog can jump between different rows on the same colum, then as for test:

        1110000
        0001000
        0001000
        0001000
        0001000
        0001000
        0000111

        the answer is 6, when frog will jump between different rows in the same column.

        In other case, if frog should always move one column forward and cannot make jumps within the same column, then the best answer in this case is 18. (Jump from row 1 to row 4 and from row 4 to row 7).

        Can you help, which way is correct?


        • 0
          bruce
           commented on Jan. 9, 2017

          The frog cannot jump between different rows in the same column. Agree with ZQFMGB12. 18 is the best answer for your case.


        • 0
          ZQFMGB12
           commented on Jan. 9, 2017

          The latter is correct.