HCI '16 - Jumping - Olympiads Online Judge

HCI '16 - Jumping

View as PDF

Submit solution

All submissions

Best submissions

Points: 20

Time limit: 0.35s

Java 1.5s

Memory limit: 64M

Java 256M

Authors:

zj97, damian, fanpu

Problem type

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

Input

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

Each subsequent $C$ ~C~ lines of the input contains a string of $N$ ~N~ 0s and 1s. A 1 on line $i$ ~i~ (starting from 2nd line) on column $j$ ~j~ (both 0-indexed) indicates the rock $j$ ~j~ is present in column $i$ ~i~, a 0 indicates that rock $j$ ~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 \le 7$ ~1 \le N, C \le 7~

Subtask 2 [5%]

$1 \le N, C \le 100$ ~1 \le N, C \le 100~

Subtask 3 [20%]

$1 \le N, C \le 500$ ~1 \le N, C \le 500~

Subtask 4 [20%]

$1 \le N, C \le 750$ ~1 \le N, C \le 750~

Subtask 5 [45%]

$1 \le N, C \le 2\,000$ ~1 \le N, C \le 2\,000~

Subtask 6 [0%]

Sample test cases.

Sample Input 1

Sample Output 1

Explanation for Sample Output 1

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

Sample Input 2

Sample Output 2

Explanation for Sample Output 2

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

discoverMe commented on March 16, 2019, 6:44 p.m.

in sample case 2 pepe must jump diagonally. how many columns can he jump, and how does that affect the time taken?

2

Dormi commented on March 16, 2019, 6:49 p.m.

He can only move one column and one column only, meaning he can't even go down in the row on the same column.

3

Cueball1234 commented on Sept. 4, 2017, 1:31 a.m. ← edit 2 →

TLE

My solution has an execution time of $\mathcal{O}(NC \log C)$ ~\mathcal{O}(NC \log C)~, 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 $\mathcal{O}(NC \log C)$ ~\mathcal{O}(NC \log C)~ TLEd. Some suggestions on why my initial solution TLEd would be much appreciated. Thanks!

2

Xue_Alex commented on Sept. 4, 2017, 1:35 p.m. ← 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.

1

Cueball1234 commented on Sept. 4, 2017, 4:49 p.m. ← edited →

Ah yes, very true. But it is still weird, since $NC \log C$ ~NC \log C~ 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!

3
Cueball1234 commented on Aug. 31, 2017, 5:41 p.m. ← edited →
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$ ~N~?

e.g.

1 0 1 0 1 0

Is the answer 2 or 0?

Thanks!

4
Xue_Alex commented on Sept. 1, 2017, 8:52 p.m. ← edit 3 →
The input

3 2 101 010

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

3

Cueball1234 commented on Sept. 1, 2017, 9:25 p.m.

Awesome, thank you for the confirmation!

2

kobortor commented on Jan. 7, 2017, 7:03 p.m.

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

3
gloomcore commented on Jan. 7, 2017, 8:30 a.m. ← edited →
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?

4
bruce commented on Jan. 7, 2017, 2:25 p.m.
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.

4

bruce commented on Jan. 9, 2017, 11:50 p.m.

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