DWhat I do not understand about this task:
The test example is:
4
10 20 1 5
So if Jack chooses first, from the left or the right side, he will choose 10. Then John must choose 5. Jack will choose 20 and John 1. That is 30. Why is the result 25 ?
Slow down,... and read again carefully... It says that both players play optimal. So for the sample test:
4
10 20 1 5
If first player takes 10 then the other guy can chose one number from 20 1 5. So he can chose 20 or 5 and he can take 20, then the first one will chose from 1 5 and it's better to take 5 so the first one would have 15 and the second one 21. That is not the best solution for the first player. Lets see another case, what if the first player takes 5 instead of 10...
10 20 1 5
First player takes 5.
10 20 1
The second player can chose any of the numbers (10 or 1) and the first player will take number 20 in any case.
So the second player takes 10
20 1
The first player takes 20.
1
The second player takes 1.
So the first player has got 25
and the second has got 11.
P. S. The first player can't get 30, cuz:
4
10 20 1 5
If the first player takes 10 then the second one will take 20, and that is not the best solution for the first player...
I hope this will help you understand the task better.
Thank you very much for the help. Now I understand. Should I use dynamic programming?
nikola, can you look at my code and tell me what's wrong ?
@Diabolic
Yeah, you should use DP.
@gigac
Ill look at your code but later, cuz friends are waiting for me to play basketball, so i'll be back in few hours...
oh crap... okay.. when you'll be back. see what's the matter with it
I can tell you what's wrong right now, cuz your code is short... As I see in your code you are checking if a[i] + a[j-1] > a[j] + a[i+1] then the player will take the number a[i] otherwise he'd take number a[j]. You see, that's the mistake. It doesn't have to be that way. What if you have a test:
6
100 200 100000 1 99900 99800
Your program will do the next:
First take 99800. Sum = 99800
100 200 100000 1 99900
now the second player takes 99900
100 200 100000 1
Now the frist player tekes 100. Sum = 99900
200 100000 1
Now the second player takes 200.
And the first one takes 100000. Sum = 199900.
And the correct solution:
6
100 200 100000 1 99900 99800
First player takes 100. Sum=100
200 100000 1 99900 99800
The second one takes one of the numbers 200 or 99800.
2nd player takes 99800
200 100000 1 99900
The first player will take now 99900 so he will be able to take 100000 later and his sum will be 200 000.
As you see, the better solution for the first player is to take 200 000 than 199900. I hope you see what's your mistake....
Gotta go now... I hope this will help you a little if it won't then ask for help...
I still can't get it.
I don't know what is a optional game :S
Sry for late answer,...
Well optional move is the point of the task... Maybe you need to practice DP more before solving this task...
Optional move in this task is the move that alllows you take the bigest possible sum...
Dunno how to explain better :S
Yeah... I know that Optional move allows you to take the biggest sum :)
I should practice DP more and more :)
DP is very difficult to understand. Can somebody please help with the code?
Thanks in advance.
what's ur gmail or ym or sth I can tell u more detail...
hendrik write me on:
s.martinovski@gmail.com
Thank you.
what should be the idea used here
again me :D
well you should do DP ...
where you can see DP ???
try to calculate dp[i][j], where that represent optimal game if you have elements just from i-th to j-th, using dp[i+1][j] and dp[i][j-1] ...
ok will try:D
thanks demjan:))
