A Game

There are a bunch of coins on a table, laid out in a straight line.
Each coin has a (positive) value from 1 to 1000. Now, you're going to play a game with a friend.

At every turn, you must remove a coin from one end of the line.
Turns alternate, so your friend goes immediately after you're done.
The game ends when there are no coins remaining.

An example game:
The coins start like this:
4 4 9 4
You always go first, so you take the 4 from the left side:
4 9 4
Your friend takes any of the 4s (it doesn't matter)
9 4
Now you can take the 9, and your friend takes the remaining 4.

Your score, in this case, is 4+9 = 13.
(In this case you can always beat your friend.)
Find the maximum possible score you can achieve.

Input

N <= 1000, the number of coins.
N lines, each with the value of a coin.

Output

Your maximum possible score, provided that you go first and your friend plays perfectly.

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 27, 2013

Problem Types: [Show]

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

Comments (Search)

What does it mean to play perfectly?
Is it like the game of nim where your friend is thinking ahead all the way to the end?

Lets say if there is a move that will lead to a guaranteed win, they will make that move

According to the data size, BFS may solve the problem.

Nope. This problem gets an MLE using BFS. :(

Experimenting with this is not worth my time (nor yours), since a BFS isn't the intended solution and I'm sure it'd just choke (no matter how good the implementation).

That being said, you are making a mistake in your BFS that will come back to bite you in other problems. Specifically, you are storing far, far more state than necessary in your queue. You can in fact store the problem state in two integers, whereas your code is storing as many as 1003 integers plus the overhead of a linked list.

If you can figure out how to store the state more compactly, it might push you towards a more sane solution.

True, and that was a nice way to think when you do the problems. I should learn how to estimate the time and the space complexity before trying to do the problem.

Thanks. :D

Is N guaranteed to be even so that each player picks up an equal number of coins?

Nope, N can be odd or even