TopCoder problem "UnfairDivision" used in SRM 305 (Division I Level One , Division II Level Two)

Problem Statement


For years, Albert has picked on his sisters Betty and Carla, and now he is about to pay the price. The siblings' parents--firm believers in the "I cut, you choose" method of division--have died and have left instructions in their will about how their assets are to be divided. The assets have been written down in a single long list. Albert has been given scissors and must carefully cut between two entries to divide the list into two non-empty sublists. Betty will then be given the scissors and will do the same to one of the sublists, leaving a total of three sublists. Carla will then choose one of the sublists and will receive all the assests in that sublist. Next, Betty will choose between the two remaining sublists and will receive those assets. Finally, Albert will receive the assets on the last remaining sublist.

Naturally, each person wants to maximize their own share, but, because of certain regrettable childhood incidents, Betty and Carla will each try to punish Albert, as long as they can do so at no cost to themselves. For example, if Betty has two options that will both net her $1000, then she will always choose the option that will give Carla more money and Albert less money. On the other hand, if Betty has two options that will give her different amounts of money, then she will always choose the option that will give herself the most money.

As Albert raises the scissors to make the first cut, he wonders how much he is going to end up with. Given a int[] assets, representing the values of the assets in the list, in the same order as the list, calculate the total value of Albert's share, assuming that all parties have full knowledge of each other's strategies and make their decisions optimally.



Method signature:int albertsShare(int[] assets)
(be sure your method is public)


-assets will contain between 3 and 50 elements, inclusive.
-Each element in assets will be betwen 1 and 1000, inclusive.


{ 50, 90, 10, 100 }
Returns: 50
If Albert cuts between the value 90 asset and the value 10 asset, or between the value 10 asset and the value 100 asset, then he will end up with nothing but the value 10 asset. By cutting between the value 50 asset and the value 90 asset, he will end up with the value 50 asset, while his sisters get a total value of 100 each (one gets the value 100 asset and the other gets the value 90 asset and the value 10 asset).
{ 5, 5, 5 }
Returns: 5
With only two possible cuts, Betty can't find a way to punish Albert.
{ 1, 1, 1, 1, 1, 1, 1, 1, 1 }
Returns: 2
If Albert tries to get 3, he will only get 1, so he must settle for 2.
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }
Returns: 10

Problem url:

Problem stats url:




PabloGilberto , Olexiy , lovro , Andrew_Lazarev

Problem categories:

Brute Force