HopScotch II

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 2.0s

Java 3.0s

PyPy 2 4.0s

PyPy 3 4.0s

Python 2 12.0s

Python 3 12.0s

Memory limit: 280M

Java 512M

Python 1G

Authors:

Ninjaclasher, insignificant

Problem types

bruce developed a new hopscotch. In this game, a row of stones conveniently numbered $1$ ~1~ to $N$ ~N~ (inclusive) are set in a pool of lava. As can be expected, the stones are very hot. In fact, they can be hotter than the surface of the sun! bruce must jump from the start ( $i = 0$ ~i = 0~) to the other side ( $i > N$ ~i > N~), but he can only jump at most $K$ ~K~ stones forward at a time. Fortunately, bruce has a pair of cooling boots that can cool any stone to $0$ ~0~ degrees. However, the boots require one unit of power per degree cooled, and power is very expensive! Can you help bruce find the minimum units of power required to jump to the other side of the lava pool?

bruce can only walk on stones that are $0$ ~0~ degrees.

bruce can only hop forwards to stone $j$ ~j~ ( $i < j \le i+K$ ~i < j \le i+K~) from stone $i$ ~i~.

Since bruce starts from $i = 0$ ~i = 0~, he can hop to $j$ ~j~ ( $0 < j \le K$ ~0 < j \le K~) on his first hop.

Input Specification

The first line will contain $N$ ~N~ and $K$ ~K~, separated by a space.

The second line will contain all $n_i$ ~n_i~ ( $1 \le i \le N$ ~1 \le i \le N~) separated by spaces.

There is a trailing newline (ASCII code 10) at the end of input.

Output Specification

Output the minimum power cost to hop from $0$ ~0~ to $i$ ~i~ ( $i > N$ ~i > N~) on the first line.

Output the indices of the stones bruce must hop on to use the minimum amount of power on the second line, separated by spaces and in ascending order.

If there are multiple ways to achieve the minimum power, output the lexicographically most sequence of the indices.

Constraints

For all subtasks:

$0 \le n_i < 2^{63}$ ~0 \le n_i < 2^{63}~

$0 \le \sum_{i=1}^N n_i < 2^{63}$ ~0 \le \sum_{i=1}^N n_i < 2^{63}~

$1 \le N \le 2^{23}$ ~1 \le N \le 2^{23}~

$1 \le K \le N$ ~1 \le K \le N~

Subtask 1 [1/15]

$K = N$ ~K = N~

Subtask 2 [1/15]

$K = 1$ ~K = 1~

Subtask 3 [3/15]

$K = \sqrt{N}$ ~K = \sqrt{N}~

Subtask 4 [10/15]

No additional constraints.

Sample Input 1

16 4
4 5 3 12 2 6 3 6 5 5 16 1 10 9 13 12

Sample Output 1

20
3 5 9 12 14

Sample Input 2

16 2
4 13 6 6 4 1 7 1 0 15 3 0 8 11 5 8

Sample Output 2

32
1 3 5 6 8 9 11 12 13 15

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation.

Comments

0

canhnam357 commented on April 28, 2024, 9:53 a.m.

waste time with "the lexicographically most sequence of the indices", if define it according to my AC submission, it mean "the largest lexicographically of reverse sequence" , example [1, 3, 4] less than [1, 2, 5] because [4, 3, 1] less than [5, 2, 1]

0

zhenga1 commented on Aug. 13, 2021, 8:03 a.m. ← edit 2 →

I keep TLE on case #7 of final batch, how can I optimise my code

I am using monoqueue + a queue that keeps track of indexes of values in the monoqueue. It is an $\mathcal{O}(N)$ ~\mathcal{O}(N)~ solution

2

Nils_Emmenegger commented on Aug. 14, 2021, 4:17 p.m. ← edited →

For some mysterious reason, putting all of my code inside a solve() function significantly increased the speed of my solution. I would recommend that you, and others who are having trouble passing this question in python, try the same.

Edit: I should note that I saw this speedup only when using cpython, not pypy.

1

zhenga1 commented on Aug. 16, 2021, 6:51 a.m.

Thank you! My code was indeed sped up, but case 7 still does not pass.

7

let987let987 commented on Feb. 15, 2020, 2:21 a.m. ← edit 2 →

What does lexicographically most sequence mean?

Edit: e.g. for the first sample, wouldn't 3 7 10 14 be bigger lexicographically?

1

pblpbl commented on July 27, 2020, 11:02 p.m.

3 7 10 14 would be bigger lexicographically but the total cost would be 3 + 3 + 5 + 10 which is 21 so it isn't the minimum cost

6

madhur4127 commented on Feb. 22, 2020, 5:53 p.m.

Why is this downvoted? Assuming "lexicographically most sequence" means "lexicographically largest sequence" the point holds.

2

Evan_Yu123 commented on Jan. 9, 2018, 3:13 a.m. ← edit 3 →

My $\mathcal{O}(N)$ ~\mathcal{O}(N)~ solution that uses a monoqueue and a hashmap TLEs and occasionally RTEs (WA aside), why is this solution suboptimal? Can someone give me a hint on how to optimize this?

4

insignificant commented on March 29, 2018, 1:20 a.m.

No hashmap is needed.