OJ Board

You can look at the sample solution at the Waterloo site (google for it). It is a quadratic time complexity solution. They missed a crucial observation to make it linear, but it is not very hard to find.

Can you give me the address of the website? There's so much websites called "Waterloo ...

Could somebody tell me how to use DP in this problem?
To sunny: I wouldn't call it 'greedy', I think technically it is still DP, but with a 'zero-dimensional DP-array'. Unless you have a different solution, of course.
My solution isn't based on DP. It works in O(n) and also can be modified to ...

Heh, got AC

jurajz wrote:Hello!

Your input is very huge. I tried paste here output, but then it happened something like in the last post in this thread:

Hope it helps

Thanks a lot, my output the same, but I still get WA. Is there any tricky cases? Also, can you post a code that prints output?

Hello all. Give me please output for this input:

See post below.

thanks a lot, got AC

Hello. Give please output for this test cases.

50
42 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36 91 4 2 53 92 82 21 16 18 95 47 26 71 38 69 12 67 99 35 94 3 11 22
34 73 64 41 11 53 68 47 44 62 57 37 59 23 41 29 78 16 35 90 42 88 6 40 42 64 48 46 5 90 29 70 50 6 1
94 48 29 23 84 54 56 40 ...

For N == 1 your output is wrong

Cho wrote:If you start at station 4, you have to go back to station 4 to finish the lap.

Thanks, I have understood.

I don't understand one thing.
First example:

5
1 1 1 1 1
1 1 2 1 1

Why I cannot finish lap from station 4? I can get 1 gallon of petrol at station 4. It's enough to go to station 5. At station 5 I can get 1 gallon of petrol and finish lap.

but.. how do you get it pass through memory limitations? an array of 1024*10000 is too much!
You can do memorization using STL's map.
I do memoization by the next way:
Cache _Cache[13 /* number of remaining digits */][10000 /* remainder */];


struct Task
{
DigitsToUse digitsToUse;/* struct ...

Can anyone give me problems that use dynamic programming, I need to practice:)

Thanks in advance
http://acm.uva.es/p/v110/11003.html
http://acm.uva.es/p/v110/11008.html
http://acm.uva.es/p/v110/11022.html
http://acm.uva.es/p/v110/11069.html
http://acm.uva.es/p/v110/11081.html

Also look at http ...

Vexorian wrote:If I am not mistaken, for the case:
1
aaa e e

The output should be 1, right?

my solution outputs 1.

Ecou wrote:You have a double point (2,2) in the first testcases for set1. if i remove
that i get the exact same output. Got any more?

no

Input:
10
0 0
4 0
0 4
4 4
1 1
2 2
2 2
3 2
2 3
3 3
25
0 0
0 1
0 2
0 3
0 4
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4
3 0
3 1
3 2
3 3
3 4
4 0
4 1
4 2
4 3
4 4

10
0 0
4 0
0 4
4 4
1 1
2 2
2 2
3 2
2 3
3 3
22
-1 -1
-1 0
-1 1
-1 2
-1 3
-1 4
-1 5
-1 1
5 1
-1 2
5 2
-1 3
5 3
-1 4
5 4
-1 5
0 5
1 5
2 5
3 5
4 5
5 ...