H  Secret Lilies and Roses

If you are nowhere to the solution, take this hint: “What if you already know how many roses there are?” If you cannot go further, this is another hint: “Once you know how many roses there are, you do not need to make any query again!”

Indeed, if there are \(k\) roses, then the answer is simply “answer \(k\)”. The proof is simple. If there are \(l_k\) lilies among the leftmost \(k\) flowers, that means there are \(k - l_k\) roses among them. Therefore, the number of roses among the other flowers (a.k.a. \(r_k\)) will be \(k - (k - l_k) = l_k\). This also proves that the answer actually always exists for any configuration of the flowers.

So now we have reduced this problem into finding the number of roses among the \(n\) flowers. At a glance, this might be easily solved with a binary search by finding the smallest \(j\) such that the “multi \(j\)” is a non-zero value. However, this strategy will not work as we can have the following flower configurations (with \(R\)‘s denoting roses and \(L\)‘s denoting lilies):

Particularly, the result of making a multiply query on the first block of roses or the last block of lilies is always \(0\). Only if we make a multiply query on the “middle” block part will result a non-zero response, and note that this part could be very narrow.

One possible solution is to use a binary search with the type query instead: We go to the right if it is rose, and left if it is lily. Assuming that there is a “dummy” rose flower as flower \(0\) and a “dummy” lily flower as flower \(n + 1\), this binary search allows us to find any position \(x\) separating a rose and then a lily (i.e. flower \(x\) is rose and flower \(x + 1\) is lily).

Finally, we first make “multi \(x\)” query to get \(l_x \times r_x\). And then, we may make “multi \(x-1\)” and “multi \(x+1\)” queries, as the first will definitely increase the number of the roses on the right (i.e. \(l_{x-1} \times r_{x-1} = l_x \times (r_x + 1)\)) and the second will definitely increase the number of the lilies on the left (i.e. \(l_{x+1} \times r_{x+1} = (l_x + 1) \times r_x\)). With these three equations, it is not hard to find both values of \(l_x\) and \(r_x\) even if any of them is \(0\), and finally know the number of roses among the \(n\) flowers. But actually, asking two of these three equations is already enough to determine the two variables.

Query complexity: \(\lceil \log_2 n \rceil + 2\)