## Editorial for DMOPC '21 Contest 2 P3 - Divisions

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

It helps to think about this problem in binary. Then, division by 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 and . So, we should keep the longest common prefix (LCP) of and in binary in order to minimize the number of operations to make . Thus, the answer to the problem Alice solved is just , where and are the binary lengths of and respectively, and is the length of the longest common prefix of and in binary. Using this information, we know that we can deduce if we know the answer to the problem and both of and .

First of all, let's make a query with , which will tell us . Then, we will work our way from the most significant bit in (which we know from the query) to the least significant bit. For each bit , let's query as the currently known prefix of (all bits before bit ) with bit equal to . If after working out we find that it is greater than our current LCP length, we know that bit is . If it remains the same length, then bit must be . With this strategy, we can work out one bit of information per query which gives around queries per number, enough to pass the first subtask.

Let's try and extend our solution from the first subtask. If bit is indeed , then can't we also get information about bit ? 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 ? Let's calculate this by estimating the expected match length. By probability, we have a chance of matching the -th bit, chance of matching the -th, chance of matching the -th, and so on. Therefore, the expected match length is . We can figure out the incorrectly matched bit on top of this, so we actually get around bits of new information per query! This puts us at around 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.

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.