Sane's Monthly Algorithms Challenge: October 2008

Jumpscotch (Senior Level)

Hopscotch is a simple game which can be played with a group or family or individually. Diana has been playing the game for years and is easily the best Hopsscotch player on the playground. Her friends have decided to challenge her title by inventing a complicated version of Hopscotch called "Jumpscotch."

In Jumpscotch, a single row of squares is drawn along the ground and a positive integer is drawn inside each square. Starting on the first square, Diana must jump from square to square and finish on the last square. Afterwards, her 'score' is the sum of all numbers which she has touched. The objective of Jumpscotch is to get a lower score than your opponent.

Diana knows that she is only strong enough to hop a certain distance (d). She is also smart enough to know that with this limitation, the best 'path' is not always obvious. Diana wants your help in determining the best path, given each square's value and her maximum hopping distance.

Input

On the first line, the integers n (1 ≤ n ≤ 1,000,000) and d (1 ≤ d ≤ 10).
There will be one test case where Diana has super human strength and d = 5,000 while n = 1,000,000.

The next n lines that follow have positive integers ≤ 1000, representing the number drawn inside each square. These lines are listed, in order, from start to finish.

Output

On a single line, output the smallest possible score that Diana can obtain.

Sample Input

12 3

1

4

2

6

5

1

1

8

7

3

1

2

Sample Output

10

All Submissions
Best Solutions

Point Value: 17 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: Oct 20, 2008
Author: DrSane

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I think I have a O(nlogd) solution. But sometimes it responds with something like :
Test case #1:  OK [0.080s, 2.6M] (10/10)
Test case #2: OK [0.130s, 2.6M] (10/10)
Test case #3: OK [4.460s, 2.6M] (10/10)
Test case #4: OK [0.090s, 2.6M] (10/10)
Test case #5: OK [0.130s, 2.6M] (10/10)
Test case #6: OK [0.120s, 2.6M] (10/10)
Test case #7: OK [0.210s, 2.6M] (10/10)
Test case #8: OK [9.680s, 2.6M] (10/10)
Test case #9: OK [164.370s, 2.6M] (10/10)
Test case #10: Wrong Answer [70.690s, 2.6M] (0/10) (Details)

I don't think it ran for that long. Could someone help me with last test case ?

Haha, don't worry about it - the Judge is having a weird issue with sometimes reporting the wrong runtime. It doesn't affect your result, and will be fixed soon.

It appears that this is due to some undocumented bug in either the hypervisor, or the kernel, or both, and doesn't occur for C and C++ programs because those will always only use one core at a time unless specifically written multi-threaded, whereas it occurs for Java programs because the JVM always launches about a dozen threads. After disabling SMP support on the kernel: CPU time usage reported is now "reasonable" in all cases, although sometimes it's still greater than the time limit, and I don't know why.

These issues may be permanently fixed if we can move to a fully virtualized platform or a dedicated server. However, that is not likely to happen soon, because we are poor students.

Meanwhile, if your program is being "Killed" near 2 s, it probably means TLE.

Sorry guys for the delayed response(I had exams). Thanks for the corrections, bbi5291. But could someone please tell me whether my implementation in O(nlogd) ?( or is it O(n^2) in worst case ? ). Or a hint ?

If you're using the "expected" priority queue solution, it should be O(n log d), which I would expect to be too slow for the last test case.

Like, you mean I must write my own Priority Queue.

I wouldn't recommend it. There is a solution with asymptotically better running time.

My exams are still not over, but I can't get this question out of my head, can I ask for a more elaborate hint ? Do you mean there is a O(n) solution ?

Pretty much, yeah. It's generally pretty hard to find problems with solutions slower than O(n) but faster than O(n log something). Unless they involve disjoint sets. Or are extremely interesting, like [url=http://wcipeg.com/problem/ioi0423]this one[/url].