PROBLEM LINK:DIFFICULTY:Hard PREREQUISITES:Graph theory, Maximum matching, Max flow PROBLEM:Best explained at the problem page only. DETAILED EXPLANATION:Consider a graph G where all numbers are vertices. There is an edge between two numbers if their prime factorisations differ by exactly 1 prime. Further assume for now that counts of all numbers are 1. The game is as follows : first player chooses some vertex and from then on current player tries to extend the path drawn so far. No vertex is to be visited twice. Claim 1: If the graph G admits a perfect matching, game is in losing position. Proof : Let M be any perfect matching on G. Second player chooses following strategy  whenever first player chooses some vertex v, second player chooses M(v) the vertex matched to v in M. This move is always valid and so second player can't run out of moves before first player. As G is finite, some player would run out of moves at some time and that'd be the first player. So first player would lose. Hence Proved. Claim 2 : If graph G doesn't have perfect matching, first player has a winning move. Proof : Let M be some maximum matching in G. As G doesn't have perfect matching, there is some vertex v that is not covered by M. I claim v is a winning move for first player. Reason is second player is constrained to move to only matched vertices of M (else he'd have found a path from unmatched vertex to another unmatched vertex which would've been an augmenting path countering the fact that M was maximum matching). Whenever second player chooses some matched vertex of M, first player chooses vertex matched to this vertex. So second player stops before first player does and so first player is in a winning position. Hence proved Note it also implies that if some maximum matching M doesn't cover a vertex v, v is a winning move. We need to prove that there are no other winning first moves. Claim 3 : If v is a winning first move, there is some maximum matching M
which doesn't cover v. Proof : We'd prove it be contradiction. Assume v is a part of all maximum matchings. Let M be such a matching. If v is winning move, by definition no matter what strategy second player chooses, first player has to win. So let us say second player chooses following strategy : moving along edges of M whenever first player chooses a matched vertex. First player must win even here and so at some stage he must reach an unmatched vertex. We can flip all the edges chosen to get an alternate maximum matching where v was unmatched to get another maximum matching which doesn't cover v. Hence proved. Hence a number A is winning first move iff there is some maximum matching M in which it is not matched. Now let's impose the constraints of different numbers having different counts as well. First observation to make here is that graph G is bipartite. Numbers having odd number of prime factors is one side and the numbers having even number of prime factors is another side. There are no intraside edges. Now when the graph G is bipartite, we can convert a maximum matching problem to a max flow problem very naturally. Introduce a new sink and source. Create an edge from source to left side vertices with capacity equal to count of that vertex, similarly from right side vertices to sink. Create edges between left side and right side based on the adjacency condition given with a capacity of infinity. G with multiple copies of numbers had a perfect matching iff this biparite graph has perfect flow (i.e no edge from source to left side is unsaturated) Now how can we find the smallest number which is a winning move? There are multiple solutions : Approach 1 : Approach 2: Let's ask the question which is the smallest number in the left side which is a winning move. If we can answer this question efficiently, we could flip left and right sides to find the smallest winning move from right side as well and finally min of these two would be our answer. So how do we find the smallest number of left side which is a winning move? Let's sort the left side vertices in decreasing order. Now let's try to find out the value of X where smallest X vertices of left side are always included in any maximum matching. We can do a binary search over X. Once we fix X, we need to check if the size of maximum matching on remaining vertices is (maxFlowX). This same solution can be adapted to the case where counts of vertices are > 1 by changing matching to max flow. This approach takes time O( log N * maxFlow) and is sufficiently fast to get accepted. Look at setter's solution for an implementation of this scheme. Approach 3: We can actually do much better. Let's try to find out the smallest winning move in left side, as before. Let's sort the vertices in decreasing order, run a maximum matching algorithm on it. Now start moving from bottom to top and the first vertex which is not matched is our answer. In case of counts > 1, same changes to flow and we check if a given vertex is fully saturated or not. This works as long as left hand side vertices are added one by one. Beware usual Dinic's or Fordfullkerson with scaling don't add vertices one by one. What one can do is add vertices one by one and not reset the whole graph using any flow algorithm. Refer to tester's solution for an implementation of this approach. Approach 4: There is one more solution that we din't think about while preparing this problem. Let's focus our attention on approach 1 once again. Each of these N times, much of our network is same as original network, do we really need to compute the whole flow again? Well not really. When we're trying to see if vertex v is a winning move or not, all we have to do is reduce the capacity of one edge by 1 unit and see if the max flow is maintained or not. Now this can be done using a single augment (or unpush operation as in code of several contestants). Once this is done, we can increase the capacity again by 1 unit which can be done using a single augment. So instead of O(N) whole max flow algorithms, we just need to do O(N) augments. This approach is also fast enough and would fit in time very comfortably. Several contestants have used this idea, I'd advise to go through every accepted solution. Approach 5: We can find all the losing positions in O(N) time using following approach pointed out by @thocevar in editorial comments : Find all unmatched vertices and build trees of alternating paths starting from those unmatched vertices. Every second vertex in a tree is winning because you can augment the path towards the root  the vertex becomes unmatched and the size of matching doesn't change. All other vertices are losing, because the first player to move can always move along a matched edge (which goes away from the root of the tree) so he will never be stuck in an unmatched vertex. This is only O(N). Notes on implementation:
SETTER'S SOLUTION:Can be found here. TESTER'S SOLUTION:Can be found here.
This question is marked "community wiki".
asked 12 Aug '12, 00:04

Could you please explain in more detail how to multiply modulus numbers up to 10^18. I used something similar to fast exponentation ( multiplication took log(v) time, log base 10 ) and it was slow with 4 iterations of RabinMiller test. For me limiting to one iteration was giving WA. answered 12 Aug '12, 21:54

Answer is hidden as author is suspended. Click here to view.
answered 20 Feb, 11:58
