Can anyone discuss this problem as the editorial is long due and this problem is not discussed in any forum. I feel this relates to find sort of Euler tour on the conditions, but could not come up with any conclusive algorithm.
1 Like
I have an idea, but it’s probably an overkill for this problem. Also, I didn’t submit my solution, so I am not sure if it’s correct. I am writing it for a discussion. My idea involves 2-SAT.
Observation 1
The problem can be broken down into smaller parts, where we consider only 1 prime factor at a time. If it is given GCD(X,Y) = 6 and GCD(Y,Z) = 10, then, we solve it for 2, 3 and 5. For prime “2”, the queries becomes, GCD(X,Y) = 2 and GCD(Y,Z) = 2. For prime “3”, GCD(X,Y) = 3 and GCD(Y,Z) = 1. If solution exists for all smaller parts, then solution exists for the big part.
From now on, I will consider solving for prime “2”.
Observation 2
If it is given, GCD(X,Y) = 2^3, then we can immediately assign 2^3 to both X and Y. Cause we know for sure that X and Y has at least 2^3 in them. We will use this assignment to find conflict with LCM in observation 3.
Observation 3
If it is given LCM(X,Y) = 2^5, then we know for sure that at least one of {X,Y} has 2^5 in them and both of them at most has 2^5 in them. If we find that we have assigned any one of them higher than 2^5 for any GCD query then there is conflict. Otherwise a solution may exist.
Observation 4
Given LCM(X,Y) = 2^5 and we know there is no conflict with GCD(), what can we say for sure? We can say for sure that one of them has 2^5 in them. Who has it, we can’t be sure. So we can imply the following:
- If X doesn’t have 2^5 in it, then Y must have it.
- If Y doesn’t have 2^5 in it, then X must have it.
This seems like 2-SAT to me. But what are going to be the nodes? Simply saying !X->Y won’t work, as we might have another query like LCM(X,Z) = 2^3. We can’t write now !X->Z. That’s ambiguous.
Observation 6:
We split every number into how many 2’s it can have in it. 2^14 >= 10000. So numbers cannot have possibly have more than 2^14 in them. So we split every number into 14 nodes. X becomes, X1,X2,X3…X14. Where, Xn being true means X has 2^n in it. Now, for LCM(X,Y) = 2^5, we can write, !X5->Y5 and !Y5->X5.
Observation 7:
Can both X1 and X3 be true? No. X cannot have 2^1 and 2^3 in it at the same time. That is, out of the 14 {X1,X2…X14}, only one can be true. Therefore, we add few more edges in our implicit graph.
- X1->!X2, X1->!X3…X1->!X14
- X2->!X1, X2->!X3…
Conclusion
Now, we have an implicit graph. A solution exists, if we can satisfy all these conditions, for every prime <= 10000. Otherwise it doesn’t. We use 2-SAT algorithm to find if it is possible to find a solution.
Like I said before, it is an overkill. I bet there some easier solution. I happened to learn 2-SAT algorithm recently, so that’s why this popped in my mind. There is saying right, if all you got is a hammer, then everything looks like nails. But I am surprised that I managed to turn this into a 2-SAT.
I was thinking like for every pair of conditions (x,y) we’ll find the condition for both of them to hold true. If there is any intersection of elements among those two conditions, then we need to take care for the value of that variable so that the two conditions hold true.
After these if we try to connect the conditions i.e connect x1 with x2 on say condition A. Now if we can connect either x1 to x3 or x2 to x3 and condition becomes AUB (B is the constraint so that x1 and x3 or x2 and x3 hold true.) In this way if we can traverse the total graph. But Could not do much progress from this.
The editorial
http://apps.topcoder.com/wiki/display/tc/SRM+633
The solution there is based on dfs+exhaustive search.