7

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.

  • 5
    Is the speed of eating based upon the number of apples (apples per minute), or by weight (grams per minute)? If it's apples per minute, sort the list by weight descending, and always eat the largest available. If it's done by weight, then the order in which you eat apples does not matter. – Matthew Feb 24 '14 at 0:54
  • 1
    @Matthew I forgot to mention that it's done by weight per interval. Actually the order matter, because if we have apple weighing 300,400 and 500 grams. The only time when the player A eats more grams than player B is when he first eats the 300 grams apple. – Stefan4024 Feb 24 '14 at 1:02
  • @euphio Check the case when apples weigh 100,200,300 and 900 grams. – Stefan4024 Feb 24 '14 at 1:44
  • 1
    If players A and B can eat the same weight of apple per unit time and have zero interval between apples, then surely the weight of a specific apple is irrelevant and it's only the total mass of all the apples which counts? – Phoshi Feb 24 '14 at 9:19
  • 2
    @Phoshi: It's only the total weight that counts, but the weight has to be combination of weights of the individual apples and the player who gets better combination wins. – Jan Hudec Feb 24 '14 at 11:02
3

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.

  • This seems simular like the Subset sum problem, which is widely know that is NP-Complete, i.e. not solvable in polynomial time. – Stefan4024 Feb 25 '14 at 11:38
  • This seems like a solution (or at least good enough for most cases). Could you explain or proof why it is working? – Codism Feb 25 '14 at 16:29
  • If there are 10,000 apples, their weight (grammes) is an integer (<= assumption), and they weigh less than 10kg, then there must be many, many instances of weights that differ by one gramme. This would make halving the pile fairly trivial; just do it roughly (perhaps from the largest down?), and then swap apples with a difference of 1 gramme from pile to pile (unless the pile has been specifically made to block this). The difference in weight between the two piles should then be 1 gramme. – AMADANON Inc. Feb 25 '14 at 20:42
  • Codism: I'm still working on that. I worked it out by observation of solutions generated by my recursive code (see my other answer). – AMADANON Inc. Feb 25 '14 at 21:01
  • Problem is the rules allow player B to take an apple from player A's pile..... – mattnz Mar 4 '14 at 8:16
0

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.

0

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.

  • I saw too late that this is for 1000 apples. This algorithm may, however, still be used to provide some insight. Also, if there are a limited number of discrete weights, this may allow some optimization (i.e. if you have 3 apples of 243 grams left to eat, each one is identical to the other 2). – AMADANON Inc. Feb 25 '14 at 10:05
  • Some other random observations: The winner can not win by more than the weight of the heaviest apple. If there is a way of dividing the apples into exactly half, then the optimum strategy will (I think) result in that result. I think (but cannot prove) that the result will be as close as possible to dividing the apples exactly in half, with the first player getting the larger half. – AMADANON Inc. Feb 25 '14 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.