Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author: 4fecta
Subtask 1
It helps to think about this problem in binary. Then, division by 
~2~ is equivalent to simply truncating the last digit of the number. This also means that the string of bits we may keep after any number of operations will be some prefix of the original numbers 
~X~ and 
~Y~. So, we should keep the longest common prefix (LCP) of ~X~ and ~Y~ in binary in order to minimize the number of operations to make 
~X = Y~. Thus, the answer to the problem Alice solved is just 
~|X| + |Y| - 2 \cdot \text{LCP}(X, Y)~, where 
~|X|~ and 
~|Y|~ are the binary lengths of ~X~ and ~Y~ respectively, and 
~\text{LCP}(X, Y)~ is the length of the longest common prefix of ~X~ and ~Y~ in binary. Using this information, we know that we can deduce ~\text{LCP}(X, Y)~ if we know the answer to the problem and both of ~|X|~ and ~|Y|~.
First of all, let's make a query with 
~G = 0~, which will tell us 
~|F_i|~. Then, we will work our way from the most significant bit in 
~F_i~ (which we know from the ~G = 0~ query) to the least significant bit. For each bit 
~j~, let's query 
~G~ as the currently known prefix of ~F_i~ (all bits before bit ~j~) with bit ~j~ equal to 
~0~. If after working out 
~\text{LCP}(F_i, G)~ we find that it is greater than our current LCP length, we know that bit ~j~ is ~0~. If it remains the same length, then bit ~j~ must be 
~1~. With this strategy, we can work out one bit of information per query which gives around 
~61~ queries per number, enough to pass the first subtask.
Subtask 2
Let's try and extend our solution from the first subtask. If bit ~j~ is indeed ~0~, then can't we also get information about bit 
~j-1~? In fact, yes we can! We can figure out all of the bits until the first bit which does not match with our guess, and we know how much we matched based on how much the LCP length changes. Now, how many new bits of information can we get if we completely randomize the unknown suffix of ~F_i~? Let's calculate this by estimating the expected match length. By probability, we have a 
~\frac 1 2~ chance of matching the ~j~-th bit, 
~\frac 1 4~ chance of matching the 
~(j-1)~-th, 
~\frac 1 8~ chance of matching the 
~(j-2)~-th, and so on. Therefore, the expected match length is 
~\frac 1 2 + \frac 1 4 + \frac 1 8 + \dots \approx 1~. We can figure out the incorrectly matched bit on top of this, so we actually get around ~2~ bits of new information per query! This puts us at around 
~31~ expected queries per number, which is enough for full marks.
P.S. The author would like to note the similarity between this solution and a particular game featured in Squid Game, which is actually completely coincidental. In any case, it may help you really visualize what's going on here.
Comments
Wait I am mad confused how is the second solution getting 2 bits of information per query? Like if we see it as a graph were the root is labelled 1 and the child is just adding 1 or 0 behind that number in binary. The operation is the distance between the nodes x and y which is basically what subtask one is about. correct me if my understanding is wrong.
Your understanding is wrong. Yes, you could think of
as an operation on the graph you described. However, what subtask 2 does is make a random guess for the number, and it turns out that we get one extra bit of information per guess as outlined in the solution.
Can't wait for season two of squid game