10
$\begingroup$

There's a problem from programming competition which already finished: http://codeforces.com/contest/458/problem/F

Two weeks already passed but still nobody solved it yet - in fact you can see here http://codeforces.com/problemset?order=BY_SOLVED_ASC that this is the only problem in the set of about 2000 problems that was not solved yet.

The problem itself follows.

Pieguy and Piegirl are playing a game. They have a rooted binary tree, that has a property that each node is either a leaf or has exactly two children. Each leaf has a number associated with it. On his/her turn a player can choose any two leafs that share their immediate parent, remove them, and associate either of their values with their parent, that now became a leaf (the player decides which of the two values to associate). The game ends when only one node (the one that was the root of the tree) is left. Pieguy goes first, and his goal is to maximize the value that will be associated with the root when the game ends. Piegirl wants to minimize that value. Assuming that both players are playing optimally, what number will be associated with the root when the game ends?

Can you help me how to mathematically solve this minimax problem? Do we need to use any advanced concepts from game theory to solve this problem?

Thank you for the help in advance.

$\endgroup$

closed as off-topic by Per Alexandersson, Ricardo Andrade, Stefan Kohl, Yemon Choi, Daniel Moskovich Oct 27 '14 at 22:59

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Per Alexandersson, Ricardo Andrade, Stefan Kohl, Yemon Choi, Daniel Moskovich
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ The mathematics is quite easy; this is basic min-max, if I am not mistaken. The problem is rather computational complexity and programming optimization, and thus, your question does not belong here, but rather on programmers.stackexchange $\endgroup$ – Per Alexandersson Aug 22 '14 at 22:28
  • 3
    $\begingroup$ No, it's not "basic min-max". I didn't use any programming terms and problem is formulated purely mathematically. $\endgroup$ – Igor Demidov Aug 22 '14 at 22:31
  • 3
    $\begingroup$ The operations respect collapses of the linear order, so if you can solve the problem for values in $\lbrace 0,1\rbrace$ then you can determine whether the value should be greater than $c$ or not, and use binary search to find the fair value. $\endgroup$ – Douglas Zare Aug 23 '14 at 1:02
  • 2
    $\begingroup$ Suppose you classify games with $\lbrace 0,1 \rbrace$ values by the parity of the number of moves left, who wins if Pieguy moves first, and who wins if Piegirl moves first. If you can classify the results of joining pairs of games of these types, this gives a fast recursive solution (as opposed to the naive exponential recursive algorithms). So, are any of the pairs undetermined? $\endgroup$ – Douglas Zare Aug 23 '14 at 4:59
  • 3
    $\begingroup$ According to the links this has now been solved by four people on that programming challenges website. This is a basic min-max problem which can be sped up using various well-known tricks. It is not research-level. It has been upvoted because it is a puzzle that is easy to understand, and hard to solve efficiently if you are not sophisticated with computers. Can we close this question now? $\endgroup$ – guest Oct 27 '14 at 17:27
0
$\begingroup$

It is unclear from your question what you mean by a "mathematical" solution. From my experience in programming competitions (and, having a look on the problems over at project Euler), there is usually no "nice" closed-form solution to problems of this type. Thus, don't expect a formula, a significant amount of clever dynamic programming will be required to solve hard test cases.

Since you have not provided even a brute-force algorithm, I take it that you wonder about how to even formulate a naive algorithm.

Below is a min-max approach, with bad complexity, but it is a "mathematical" solution. For me, a "mathematical" solution is something that can be solved by a specific algorithm given enough time.

(* Base case optimal value in optimal move *)
maxPossible[{l_Integer,r_Integer}]:=Max[l,r];
minPossible[{l_Integer,r_Integer}]:=Min[l,r];

(* Construct all subtrees, by applying op (Min or Max) on pairs of leaves.*)
SubTrees[tree_List,op_]:=Module[{l,r,pos},
    pos=Position[tree,{l_Integer,r_Integer}];
    Table[ReplacePart[tree,p->op@Part[tree,Sequence@@p]],{p,pos}]
];

maxPossible[tree_List]:=maxPossible[tree]=Module[{strees},
    (* All possible moves Max can do. *)
    strees = SubTrees[tree,Max];

    (* Max wants to maximize over all possible subsequent moves. *)
    Max[minPossible/@strees]
];

minPossible[tree_List]:=minPossible[tree]=Module[{strees},
    (* All possible moves. *)
    strees = SubTrees[tree,Min];

    Min[maxPossible/@strees]
];

(* Test cases, as on website *)
testTree1={5,10};
testTree2={{5,20},10};
testTree3={{1,2},{3,4}};
testTree4={{{7,8},15},{7,{9,11}}};

maxPossible[testTree1]
maxPossible[testTree2]
maxPossible[testTree3]
maxPossible[testTree4]

The output is as expected. It is easy to modify the code, so that actual gameplay can be recorded. The last game for example, gives the following sequence of moves:

--- {{{7,8},15},{7,{9,11}}}
--- {{{7,8},15},{7,11}}
--- {{{7,8},15},7}
--- {{8,15},7}
--- {8,7}
--- {8}

I think you will have better luck over at programmers.SE, since this question is similar to Project Euler questions (if you heard about it).

$\endgroup$
  • $\begingroup$ Is this just a brute force search with memoization? Whether something runs in $n \log n$ time or $2^n$ time is not just a programming problem, nor is discovering the faster algorithm. Not all families of finite problems are mathematically trivial. "PRIMES is in P" was published in the Annals of Mathematics even though testing whether any particular number is prime is a finite calculation. Figuring out a reasonably fast algorithm for playing this game is a math problem, not just a programming problem. $\endgroup$ – Douglas Zare Aug 28 '14 at 2:39
  • $\begingroup$ This is brute force. Yes, of course it is not always trivial, but since the problem is from an actual programming competition and not an unsolved problem, the question might be better asked over at programmers.SE. Same as IMO problems belong to math.SE, and not here... $\endgroup$ – Per Alexandersson Aug 28 '14 at 6:18
  • $\begingroup$ If you really think this is off-topic, you shouldn't post a supposed answer. However, there are many differences between this problem and an IMO problem. It shouldn't be dismissed as trivial and straightforward just because particular cases are finite and you see that a brute force algorithm with a horrible running time exists. $\endgroup$ – Douglas Zare Aug 28 '14 at 6:36
  • 4
    $\begingroup$ You commented that this problem is easy and straightforward, but you have only shown a brute force approach that is like trial division for factorization. That's not progress. That's not helpful. Asking for a translation of this game into known parts of combinatorial game theory is a very reasonable mathematical question. Coding up a very slow brute force search is neither an answer nor mathematics. If you can use your code to find some patterns and make some conjectures about the structure of the problem, that would be mathematics. $\endgroup$ – Douglas Zare Aug 28 '14 at 9:21
  • 1
    $\begingroup$ @DouglasZare: As expressed, I interpret the question as asking for a naive implementation (this is how I interpret "mathematical" solution). I also believe MO is not the best place to find a solution that meets the speed requirements. Both these points has been clarified in answer. $\endgroup$ – Per Alexandersson Aug 28 '14 at 15:34

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