You are not logged in. Please login at www.codechef.com to post your questions!

×

GTHRONES - Editorial

3
1

PROBLEM LINK:

Practice
Contest

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:

  1. 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.

  2. 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.

This question is marked "community wiki".

asked 12 Aug '12, 00:04

yellow_agony's gravatar image

4★yellow_agony ♦♦
1243837
accept rate: 0%

edited 12 Aug '12, 21:49


I think that primality testing deserves a bit more attention. Fast multiplication and exponentiation with numbers up to 10^18 are quite tricky. I ended up with a sieve for small numbers, testing divisibility by some small primes and using just 1 iteration of Miller-Rabin because anything more timed out. Surprisingly, it didn't give WA. Setter's and tester's solutions are pretty much the same code with different comments and their function ullMultipleMod is by no means trivial but it is crucial for fast primality testing.

Approach 5:

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).

link

answered 12 Aug '12, 17:03

thocevar's gravatar image

6★thocevar
22626
accept rate: 0%

1

Thanks for pointing out that setter and tester solution are same. This is a mistake from our side and we'd be correcting the links shortly. Apologies for inconvenience.

I've added a link to Topcoder tutorial on primality testing which includes pretty much everything one needs to know to write robust Miller Rabin primality test for large numbers.

And I've included your alternative approach in the editorial itself. Thanks a lot :)

(12 Aug '12, 21:47) yellow_agony ♦♦4★

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 Rabin-Miller test. For me limiting to one iteration was giving WA.

link

answered 12 Aug '12, 21:54

v_haralampiev's gravatar image

6★v_haralampiev
21
accept rate: 0%

How graph G could be bipartite? Assume that numbers are: 6 (2 * 3), 15 (3 * 5) and 70 (2 * 5 * 7). In this situation every vertex is connected to every other vertex, so we have circle with odd length (clique with size 3).

link

answered 14 Aug '12, 16:37

ksh78's gravatar image

5★ksh78
11
accept rate: 0%

2

In your example there are no edges at all. Please reread the notes in the problem statement. (For example, 6 is not connected to 15 as neither 6 is divisible by 15 nor 15 is divisible by 6, leave the second condition aside.)

(14 Aug '12, 16:41) gennady_adm0★
Answer is hidden as author is suspended. Click here to view.

answered 20 Feb, 11:58

deepakkuamre's gravatar image

0★deepakkuamre
(suspended)
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×10,871
×757
×72
×15
×1

question asked: 12 Aug '12, 00:04

question was seen: 4,479 times

last updated: 20 Feb, 11:58