PROBLEM LINK:
Author: Gerald Agapov
Tester: Shiplu Hawlader and Mahbubul Hasan
Editorialist: Lalit Kundu
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Blue-Red Hackenbush
DFS, Graphs
PROBLEM:
Given a rooted tree of N<=105 nodes where each edge is either black or white and two players play optimally using these rules, find who will win:
* The players make moves in the game alternately.
* On his move Chef deletes a single undeleted black edge. On her move Ksen deletes a single undeleted white edge.
* When some edge has been deleted, all the edges that now aren’t connected (directly or indirectly) to the root will be deleted too.
*One who cannot move lose the game.
EXPLANATION:
Red Green Hackenbush is a standard game and very good research has already been done on it. Here is a very good paper which explains pretty well about the optimal strategy to win. If you don’t have much time, read page 9 of this pdf.
We evaluate a function F(node),
if F(root)==0, print “Ksen Chef”
else if F(root)>0: print “Chef Chef”
else: print “Ksen Ksen”
For each node, we calculate F recursively:
def F(n):
ret=0
for each vertex v which is child of n:
ret1=dfs(v)
if edge connecting u and v is 0:
find smallest p such that ret1+p > 1
ret += (ret1+p)/(1<<(p-1))
else:
find smallest p such that ret1-p < -1
ret += (ret1-p)/(1<<(p-1))
return ret
Of course our problem is much harder, because the large constraints do not allow to use double or long double. Also unclever calculations using BigInteger or BigRational should not pass.
So, we have to use some optimisations. One of them could be that, since we know our answer is always of form a/2k we can store [a,k] and make intelligent calculations.
Addition of [a1,k1] and [a2,k2] is simple. Let k1<k2, we get [a1*2k2-k1+a2,k2].
Coming to finding smallest p such that [a,k] + p > 1.
If a is positive, we have to add just 1. ie. a ← a + 2k and k remains same.
If a is negative and abs(a)<2k, then we have to just add 2 ie. a<-2k+1+a and k remains same.
If a is negative and abs(a)≥2k, we add 2 to [abs(a)%2k,k]. We can quickly find abs(a)%2k by using the fact a % 2k = a & (2k - 1)
Similarily we can find smallest p such that ret1-p < -1.
AUTHOR’S AND TESTER’S SOLUTIONS:
To be updated soon.