Candy Necklace

2014-1t-1-candynecklace.jpg

Two sisters Monika and Eva got a necklace of candies. The necklace contains $2n$ candies, all aligned in a row on a single string. All candies taste the same but have various integer sizes. The individual candies cannot be divided – each one has to be eaten as a whole.

Naturally, both girls have the same goal: to eat as much candy as possible. More precisely, each girl wants to eat candies of maximum total size.

The older sister Monika proposed the following game to share the sweets: Monika and Eva will take alternating turns, Eva starts. In each turn the sister whose turn it is selects one of the two ends of the necklace and eats a single candy from that end. This way each of them will end up with $n$ of the candies.

Task 1

(2 points)

Initially, Eva had a very simple strategy: Each time it was her turn, she looked at the two candies she could choose and she picked the larger one.

Show that this is not a good strategy. More precisely, show that for any $n>1$ one can find an input such that if Eva follows this strategy (and Monika is smart), Eva will eat strictly less candy than Monika.

Task 2

(4 points)

Design an algorithm that will play the game for Eva. Your algorithm must play optimally. Formally, your algorithm must maximize the total size of candies Eva gets in the worst case (i.e., if Monika plays optimally, too).

Try to design an algorithm which is as efficient as possible. (As a secondary rule, less memory is better.) Discuss (or even better, prove) that your algorithm plays optimally.

Task 3

(4 points)

Eva is not that mean to her sister. Instead of maximizing the total size of candies, she only wants to be certain that she gains at least as much candy as Monika.

Again, design an algorithm which plays for Eva. This time your algorithm does not have to be optimal. It just has to make sure that in any game (regardless of how Monika plays) the total size of candies eaten by Eva is greater than or equal to the total size of candies eaten by Monika.

Try to design an algorithm that is as efficient as possible. Can you make it more efficient than the one that solves Task 2? Discuss (or even better, prove) that your algorithm plays well enough.

Input

The first line of the input contains a single integer $n$. Then the second line contains $2n$ positive integers separated by a single space. The integers denote the sizes of the candies in the order in which they appear in the necklace.

Sample test

Input

3
1 2 3 4 5 6

This necklace is shown in the following picture.

2014-1t-1-candynecklace-example.jpg?200

Questions?

If you have any questions feel free to ask in the forum or send us an email at info[at]soi[dot]ch

Submission