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.

13

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.

8

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.

2

Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa Dịch vụ tổ chức sự kiện 5 sao Thông tin về chúng tôi Dịch vụ sinh nhật bé trai Dịch vụ sinh nhật bé gái Sự kiện trọn gói Các tiết mục giải trí Dịch vụ bổ trợ Tiệc cưới sang trọng Dịch vụ khai trương Tư vấn tổ chức sự kiện Hình ảnh sự kiện Cập nhật tin tức Liên hệ ngay Thuê chú hề chuyên nghiệp Tiệc tất niên cho công ty Trang trí tiệc cuối năm Tiệc tất niên độc đáo Sinh nhật bé Hải Đăng Sinh nhật đáng yêu bé Khánh Vân Sinh nhật sang trọng Bích Ngân Tiệc sinh nhật bé Thanh Trang Dịch vụ ông già Noel Xiếc thú vui nhộn Biểu diễn xiếc quay đĩa Dịch vụ tổ chức tiệc uy tín Khám phá dịch vụ của chúng tôi Tiệc sinh nhật cho bé trai Trang trí tiệc cho bé gái Gói sự kiện chuyên nghiệp Chương trình giải trí hấp dẫn Dịch vụ hỗ trợ sự kiện Trang trí tiệc cưới đẹp Khởi đầu thành công với khai trương Chuyên gia tư vấn sự kiện Xem ảnh các sự kiện đẹp Tin mới về sự kiện Kết nối với đội ngũ chuyên gia Chú hề vui nhộn cho tiệc sinh nhật Ý tưởng tiệc cuối năm Tất niên độc đáo Trang trí tiệc hiện đại Tổ chức sinh nhật cho Hải Đăng Sinh nhật độc quyền Khánh Vân Phong cách tiệc Bích Ngân Trang trí tiệc bé Thanh Trang Thuê dịch vụ ông già Noel chuyên nghiệp Xem xiếc khỉ đặc sắc Xiếc quay đĩa thú vị
Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa

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.

13

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.

8

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.

2

Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa Dịch vụ tổ chức sự kiện 5 sao Thông tin về chúng tôi Dịch vụ sinh nhật bé trai Dịch vụ sinh nhật bé gái Sự kiện trọn gói Các tiết mục giải trí Dịch vụ bổ trợ Tiệc cưới sang trọng Dịch vụ khai trương Tư vấn tổ chức sự kiện Hình ảnh sự kiện Cập nhật tin tức Liên hệ ngay Thuê chú hề chuyên nghiệp Tiệc tất niên cho công ty Trang trí tiệc cuối năm Tiệc tất niên độc đáo Sinh nhật bé Hải Đăng Sinh nhật đáng yêu bé Khánh Vân Sinh nhật sang trọng Bích Ngân Tiệc sinh nhật bé Thanh Trang Dịch vụ ông già Noel Xiếc thú vui nhộn Biểu diễn xiếc quay đĩa Dịch vụ tổ chức tiệc uy tín Khám phá dịch vụ của chúng tôi Tiệc sinh nhật cho bé trai Trang trí tiệc cho bé gái Gói sự kiện chuyên nghiệp Chương trình giải trí hấp dẫn Dịch vụ hỗ trợ sự kiện Trang trí tiệc cưới đẹp Khởi đầu thành công với khai trương Chuyên gia tư vấn sự kiện Xem ảnh các sự kiện đẹp Tin mới về sự kiện Kết nối với đội ngũ chuyên gia Chú hề vui nhộn cho tiệc sinh nhật Ý tưởng tiệc cuối năm Tất niên độc đáo Trang trí tiệc hiện đại Tổ chức sinh nhật cho Hải Đăng Sinh nhật độc quyền Khánh Vân Phong cách tiệc Bích Ngân Trang trí tiệc bé Thanh Trang Thuê dịch vụ ông già Noel chuyên nghiệp Xem xiếc khỉ đặc sắc Xiếc quay đĩa thú vị
Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa
Thiết kế website Thiết kế website Thiết kế website Cách kháng tài khoản quảng cáo Mua bán Fanpage Facebook Dịch vụ SEO Tổ chức sinh nhật