Apple eating problem

Player A and Player B play a game. On the middle of the table there is a pot full of N apples of different weights. Player A starts first and choose an apple and start eating it. Losing no time player B do the same. When a player eats the whole apple, without losing time repeat the same procedure. In case both player have eaten the apple at the same time, Player A still have the advantage of choosing first. Note that both players eat with same speed

What apple should the Player A choose at first to ensure that with right tactics he’ll eat as much as grams of apples possible if the player B plays optimally?

I thought that choosing the smallest or the biggest apple should do the job, but there are specific cases when this doesn’t work.

This is C++ contest problem, so there should be a nice solution to this. I think that brute force maybe provide a solution, but this will require much time, because the number of apples is up to 10000.

I would rather like some hint on how to approach this question, how to find the optimal tactic or intuition rather than a code.

A non-recursive answer: divide the apples into two piles, so they are as close as possible equal. Then, eat the smallest apple in the largest pile.

Halving the pile is left to the reader, but remember that the difference in pile size can be no larger than the smallest apple in the largest pile; if it is any larger, then moving that apple to the other pile will give you a closer answer. It can also not be larger than the difference between an apple in the larger pile, and the next smaller apple in the smaller pile – if the larger pile contains a 600 gramme apple, and the smaller pile contains a 500 gramme apple, and the difference between the two piles is more than 100 grammes, then you could swap those two apples and get closer.

For example, if you have 300+400+500 gramme, you should divide them into two piles, each being as close as possible to (300+400+500)/2=600 gramme. This comes out as one being 500 gramme, the other being 300+400=700 gramme. Eat the smallest apple from the largest (700 gramme) pile – i.e. the 300 gramme apple.

In the case of 100+200+300+900, the closest you can get to two piles of 750 grammes each is one pile of 900, the other of 600, eat the largest (and only) apple from the largest (900 gramme) pile.

As it was said it can be solved via backtracking. The important thing to note is that the weight of the apples eaten is proportional to the time spent eating. That means that maximizing the weight is the same as maximizing the time spent eating.

Another observation is that it is never beneficial to pause in eating. That means that pauses can be ignored.

So the algorithm i propose:

define state as:

amount eaten by A
amount eaten by B
list of apples left

Now in each step of backtracking you receive this state. The person on turn to choose another apple is the one with the lesser amount eaten (because it has eaten faster). Now it is easy to generate another state for the backtracking algorithm.

example

suppose you have received state:

eaten by A = 600
eaten by B = 400
apples left = 300, 400

From this you can generate states:

eaten by A = 600
eaten by B = 700
apples left = 400

and

eaten by A = 600
eaten by B = 800
apples left = 300

end of example

The algorithm ends when there are no apples left in the list. It will be probably necessary to think about some heuristics (the order in which the apples are picked). You can also prune the search space greatly if you also keep the sum of the apples left and end when its clear that you can’t be better that some solution you have found earlier. I am sure there are more similar possibilities how to speed it up.

I don’t know much about “nodes” and “graphs”, and besides, I prefer a practical approach….

This is what I decided; it’s a brute force approach, and is a trade-off between CPU time and programmer time (CPU time is cheaper). It works well with a small number of apples; 9 apples takes 3.5 seconds to run, 10 apples takes about 40 seconds; more than 12 would probably want a different approach.

Write a function that takes (time so far for player 1, time so far for player 2, the next apple, and the remaining apples). It returns, for the optimum play for both player 1 and player 2: the amount of apple eaten by player 1, the amount of apple eaten by player 2, and, in order, the apples eaten.

The code for this function is as follows:

The “next apple” is eaten (added to player 1’s time, or player 2’s time, according to who is next due to eat an apple).

If there are no (more) apples, this function is now trivial – return the times for player 1 and player 2 (which you have already calculated), and the list of apples eaten (which consists of the “next apple to be eaten”).

Otherwise, go through each apple on your list one by one (hereafter the new “next apple”), doing the following: call this same function, with the updated times, the new “next apple”, and the list of remaining apples. Get the result of each, and find the one either with the lowest time for player 1, or the lowest time for player 2, depending on who is choosing this apple. Since the returned time for player 1+player 2 must be the same as the list of apples, the lowest time for player 1 = the highest time for player 2, so you can easily sort the list by duration for player 1, and then take either the first, or last entry in the list of results. Whichever entry is selected, add your “next apple” to the start of the “apple-eaten-order list” (the third item of the result), and return the result.

Note that there may be multiple “best” results. When you are actually calling this function for real, set the “time so far” for player 1 & 2 to 0, and set the first “next apple” to 0 – an imaginary apple, so we don’t have to know in advance which apple to eat first.

Filed under: softwareengineering - @ 10:44

Thẻ: algorithms, c++

Apple eating problem

What apple should the Player A choose at first to ensure that with right tactics he’ll eat as much as grams of apples possible if the player B plays optimally?

I thought that choosing the smallest or the biggest apple should do the job, but there are specific cases when this doesn’t work.

I would rather like some hint on how to approach this question, how to find the optimal tactic or intuition rather than a code.

A non-recursive answer: divide the apples into two piles, so they are as close as possible equal. Then, eat the smallest apple in the largest pile.

In the case of 100+200+300+900, the closest you can get to two piles of 750 grammes each is one pile of 900, the other of 600, eat the largest (and only) apple from the largest (900 gramme) pile.

Another observation is that it is never beneficial to pause in eating. That means that pauses can be ignored.

So the algorithm i propose:

define state as:

amount eaten by A
amount eaten by B
list of apples left

example

suppose you have received state:

eaten by A = 600
eaten by B = 400
apples left = 300, 400

From this you can generate states:

eaten by A = 600
eaten by B = 700
apples left = 400

and

eaten by A = 600
eaten by B = 800
apples left = 300

end of example

I don’t know much about “nodes” and “graphs”, and besides, I prefer a practical approach….

The code for this function is as follows:

The “next apple” is eaten (added to player 1’s time, or player 2’s time, according to who is next due to eat an apple).

Filed under: softwareengineering - @ 10:44

Thẻ: algorithms, c++

Thiết kế website giá rẻ

Danh mục

Apple eating problem

Apple eating problem