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 intra-side 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 :
Remove vertex v from the graph and check if the size of the maximum matching
in this graph is same as that of original graph. v is a winning first move iff
sizes are same.
This approach is fairly simple and time taken by this approach is O(N *
maxflow) where maxFlow denotes the time taken by your favorite max flow
algorithm. As you might’ve guessed, this is too slow for the given time limit.
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 (maxFlow-X).
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 Ford-fullkerson 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:
-
Note that to check if there is an edge between two numbers u and v, we’d need
to see if v | u and (u / v) is prime or not (assuming u > v).
(u/v) can
potentially be a very large number ( of the order 1018) and so primality
testing has be a fast algorithm. You could use a fast probabilistic algorithm
like Miller rabin. Note that multiplication of two numbers of the order 1018 is also not trivial. You can read about this and other implementation details on this very informative Topcoder tutorial. -
One doesn’t need to factorise the numbers and decide the bi-partition in
terms of number of prime factors. Once we KNOW that graph is bipartite, we could
as well use a bicoloring algorithm like dfs / bfs.
SETTER’S SOLUTION:
Can be found here.
TESTER’S SOLUTION:
Can be found here.
