Rotary Laser Lock
Contest: Codeforces Raif Round 1 (Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: binary search, interactive

This is an interactive problem.

To prevent the mischievous rabbits from freely roaming around the zoo, Zookeeper has set up a special lock for the rabbit enclosure. This lock is called the Rotary Laser Lock.

The lock consists of $$$n$$$ concentric rings numbered from $$$0$$$ to $$$n-1$$$. The innermost ring is ring $$$0$$$ and the outermost ring is ring $$$n-1$$$. All rings are split equally into $$$nm$$$ sections each. Each of those rings contains a single metal arc that covers exactly $$$m$$$ contiguous sections. At the center of the ring is a core and surrounding the entire lock are $$$nm$$$ receivers aligned to the $$$nm$$$ sections.

The core has $$$nm$$$ lasers that shine outward from the center, one for each section. The lasers can be blocked by any of the arcs. A display on the outside of the lock shows how many lasers hit the outer receivers.

In the example above, there are $$$n=3$$$ rings, each covering $$$m=4$$$ sections. The arcs are colored in green (ring $$$0$$$), purple (ring $$$1$$$), and blue (ring $$$2$$$) while the lasers beams are shown in red. There are $$$nm=12$$$ sections and $$$3$$$ of the lasers are not blocked by any arc, thus the display will show $$$3$$$ in this case.

Wabbit is trying to open the lock to free the rabbits, but the lock is completely opaque, and he cannot see where any of the arcs are. Given the relative positions of the arcs, Wabbit can open the lock on his own.

To be precise, Wabbit needs $$$n-1$$$ integers $$$p_1,p_2,\ldots,p_{n-1}$$$ satisfying $$$0 \leq p_i < nm$$$ such that for each $$$i$$$ $$$(1 \leq i < n)$$$, Wabbit can rotate ring $$$0$$$ clockwise exactly $$$p_i$$$ times such that the sections that ring $$$0$$$ covers perfectly aligns with the sections that ring $$$i$$$ covers. In the example above, the relative positions are $$$p_1 = 1$$$ and $$$p_2 = 7$$$.

To operate the lock, he can pick any of the $$$n$$$ rings and rotate them by $$$1$$$ section either clockwise or anti-clockwise. You will see the number on the display after every rotation.

Because his paws are small, Wabbit has asked you to help him to find the relative positions of the arcs after all of your rotations are completed. You may perform up to $$$15000$$$ rotations before Wabbit gets impatient.

Input format:
The first line consists of 2 integers $$$n$$$ and $$$m$$$ $$$(2 \leq n \leq 100, 2 \leq m \leq 20)$$$, indicating the number of rings and the number of sections each ring covers.

Interaction format:
To perform a rotation, print on a single line "? x d" where $$$x$$$ $$$(0 \leq x < n)$$$ is the ring that you wish to rotate and $$$d$$$ $$$(d \in \{-1,1\})$$$ is the direction that you would like to rotate in. $$$d=1$$$ indicates a clockwise rotation by $$$1$$$ section while $$$d=-1$$$ indicates an anticlockwise rotation by $$$1$$$ section.

For each query, you will receive a single integer $$$a$$$: the number of lasers that are not blocked by any of the arcs after the rotation has been performed.

Once you have figured out the relative positions of the arcs, print ! followed by $$$n-1$$$ integers $$$p_1, p_2, \ldots, p_{n-1}$$$.

Do note that the positions of the rings are predetermined for each test case and won't change during the interaction process.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded verdict.

To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

Hacks:

To hack, use the following format of test:

The first line should contain two integers $$$n$$$ and $$$m$$$.

The next line of should contain $$$n-1$$$ integers $$$p_1,p_2,\ldots,p_{n-1}$$$: relative positions of rings $$$1,2,\ldots,n-1$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first test, the configuration is the same as shown on the picture from the statement.

After the first rotation (which is rotating ring $$$0$$$ clockwise by $$$1$$$ section), we obtain the following configuration:

After the second rotation (which is rotating ring $$$2$$$ counter-clockwise by $$$1$$$ section), we obtain the following configuration:

After the third rotation (which is rotating ring $$$1$$$ clockwise by $$$1$$$ section), we obtain the following configuration:

If we rotate ring $$$0$$$ clockwise once, we can see that the sections ring $$$0$$$ covers will be the same as the sections that ring $$$1$$$ covers, hence $$$p_1=1$$$.

If we rotate ring $$$0$$$ clockwise five times, the sections ring $$$0$$$ covers will be the same as the sections that ring $$$2$$$ covers, hence $$$p_2=5$$$.

Note that if we will make a different set of rotations, we can end up with different values of $$$p_1$$$ and $$$p_2$$$ at the end.

Example input:
3 4

4

4

3

Example output:
? 0 1

? 2 -1

? 1 1

! 1 5

Editorial:
Algorithm Analysis
Flatten the circle such that it becomes $$$n$$$ rows of length $$$nm$$$ with vertical sections numbered from $$$0$$$ to $$$nm-1$$$ that loops on the end. We say that the position of an arc is $$$x$$$ if the left endpoint of the arc is at section $$$x$$$. Indices are taken modulo $$$nm$$$ at all times. Moving arcs right is equivalent to rotating them clockwise, and moving arcs left is equivalent to rotating them counter-clockwise.
Notice that if we shift arc 0 right and the display increases, then the leftmost section of arc 0 had no other arcs in the same section. Thus, if we shift arc 0 right again and the display does not increase, we are certain that there was another arc at that position, so we shift arc 0 left. We now enter the detection stage to find any arc that coincides with arc 0 (of which there exists at least 1) at this position. Let's note down this positions as $$$x$$$.
Let $$$S$$$ be the set of arcs that we do not know the positions of yet (this set initially contains all arcs from 1 to $$$N-1$$$) and $$$T$$$ and $$$F$$$ be an empty sets. $$$T$$$ will be the set of all candidate arcs (those that may coincide here) and $$$F$$$ will contain all arcs that we have shifted leftwards. Take all elements in $$$S$$$ and put them in $$$T$$$, and pick half of the elements in $$$S$$$ and add them to the set $$$F$$$. We now shift all elements in $$$F$$$ left.
We move arc 0 left to check if any arc is at position $$$x-1$$$.
If there is, then we know that an arc that initially coincided at $$$x$$$ lies in $$$F$$$. In this case, we set $$$T$$$ to $$$T \cap F$$$ (elements of $$$T$$$ that are in $$$F$$$), pick half of the elements in $$$T$$$ to move right and remove those from $$$F$$$.
If no arc is at position $$$x-1$$$, then the arc we are looking for lies in $$$T \ \backslash \ F$$$ (elements in $$$T$$$ that are not in $$$F$$$). We set $$$T$$$ to be $$$T \ \backslash \ F$$$ and pick half of $$$T$$$ to move left and add those to $$$F$$$. We then shift arc 0 right and recurse.
When we have narrowed $$$T$$$ to exactly 1 arc, we know where exactly that arc is now. We shift that arc left such that its right endpoint is at $$$x-2$$$ so that it does not cover position $$$x-1$$$, which we may still need for future tests. Now we remove the arc found from $$$S$$$ and leave the detection stage and continue searching for the other arcs.
Once we have found all $$$n-1$$$ other arcs, we find the relative position to arc 0 and print them as the final output.
Query Analysis
Whenever we shift arc 0 right and are not in the detection stage, we use 1 shift. This occurs at most $$$2nm-m$$$ times because it takes up to $$$nm-m$$$ shifts right to find the first position where arc 0 coincides, and another $$$nm$$$ to traverse the entire circle again to find all of the arcs.
Whenever we enter the detection stage, we find one arc and use $$$2$$$ shifts initially when we move arc 0 right then left, yielding a total of $$$2n-2$$$ such shifts. Each binary search requires $$$2 \log |T|$$$ shifts of arc 0 (left and right), so across the $$$n-1$$$ detection stages this is at most $$$2n\log n$$$ when summed across all stages.
The way we perform the binary search is quite important here. Performing it in a naive manner (e.g. shifting half left, test and shifting them back) can use up to $$$n^2$$$ queries.
Instead, we set the number of elements that move in / out of $$$F$$$ at each iteration of the binary search to be the smaller half. This way we can guarantee that the number of shifts done by the candidate arcs is at most the total number of candidate arcs in the first place. This becomes $$$\frac{n(n-1)}{2}$$$ since we start with $$$n-1$$$ candidate arcs and reduce that number by 1 after each detection stage.
When we shift each of the arcs left by $$$m$$$ or $$$m+1$$$ (depending on whether they were in $$$F$$$ when we narrowed it down to 1 arc), we use at most $$$(n-1)(m+1) = nm+n-m-1$$$ shifts.
Thus in total, we use at most $$$2nm-m+2n-2+2n\log n + \frac{n(n-1)}{2} + nm+n-m-1$$$ shifts. For $$$n=100,m=20$$$, this is less than $$$13000$$$, which is much lower than the query limit of $$$15000$$$.
Other Comments
The limit was set higher than the provable bound to allow for other possible solutions. At least $$$1$$$ tester found a different solution that used around $$$13500$$$ queries.
Some other optimizations that empirically improve the number of queries:
• Instead of using arc $$$0$$$ as the detector, we can randomly pick one of the $$$n$$$ arcs as the detector arcs.
• At the very beginning, we perform some constant number of random shifts of the arcs (e.g. $$$300$$$ to $$$400$$$ random shifts). This helps to break up long groups of arcs that overlap, which speeds up the initial $$$nm$$$ search.
The official solution, augmented with these optimizations uses well below $$$11500$$$ queries and is very consistent for non-handcrafted test cases.