1

A train is given to two children as a gift. A train consists of a sequence of cars connected in a single line. There is an even number of cars, and the two children wish to divide them up. They do this by taking one car at a time from one end of the train. The older child goes first. Each car has a value to each child. and they want to maximize the value of the cars that they select. Note that the same car could be valued differently by the two children. Develop an algorithm for finding the best strategy for each child. The time complexity of your algorithm must be at most quadratic in the number of cars. If there happens to be a situation where the two choices for a child have the same value, then the child will make the choice which is best for the other child.

I am trying to figure this dynamic programming problem. I have a slight idea. I was thinking that the problem is reducible to knapsack problem but my confusion is about when the second child picks up the car.

Dave Newbury
  • 11
  • What information do they both have? – Christopher King Mar 05 '14 at 01:49
  • I didn't get you there. What Information are you talking about ? – Dave Newbury Mar 05 '14 at 01:53
  • Perhaps it means, does each child know in advance what cars the other child prefers. I suspect that you have in mind the "value" of a train car is a positive number, and that all else being equal, each child seeks to maximize the total value of their half of the cars. – hardmath Mar 05 '14 at 01:57
  • Are the children cooperating to maximize the total sum of the values? Or you are asking who would win if they both play optimally? – dani_s Mar 05 '14 at 02:01
  • I think both children need to maximize the values of the cars and from the question since each child picks up a car from one end. they are trying to maximize the values for half of the total cars. – Dave Newbury Mar 05 '14 at 02:09
  • So each child is picking cars trying to maximize the total values of his own cars, knowing that the other child is doing the same – dani_s Mar 05 '14 at 02:18
  • Yes thats what it means. – Dave Newbury Mar 05 '14 at 02:29

0 Answers0