The Riddle of the Sphinx
Contest: Good Bye 2020
Difficulty rating: 3400
Tags: binary search, data structures, data structures, interactive

This is an interactive problem. This problem doesn't support hacks.

Sphinx's duty is to guard the city of Thebes by making sure that no unworthy traveler crosses its gates. Only the ones who answer her riddle timely and correctly (or get an acc for short) are allowed to pass. As of those who fail, no one heard of them ever again...

So you don't have a choice but to solve the riddle. Sphinx has an array $$$a_1, a_2, \ldots, a_n$$$ of nonnegative integers strictly smaller than $$$2^b$$$ and asked you to find the maximum value among its elements. Of course, she will not show you the array, but she will give you $$$n$$$ and $$$b$$$. As it is impossible to answer this riddle blindly, you can ask her some questions. For given $$$i, y$$$, she'll answer you whether $$$a_i$$$ is bigger than $$$y$$$. As sphinxes are not very patient, you can ask at most $$$3 \cdot (n + b) $$$ such questions.

Although cunning, sphinxes are honest. Even though the array can change between your queries, answers to the previously asked questions will remain valid.

Input format:
The first line contains two integers $$$n$$$ and $$$b$$$ ($$$1 \leq n, b \leq 200$$$). The remaining parts of the input will be given throughout the interaction process.

Interaction format:
In each round your program must output a single line with an integer $$$i$$$ ($$$0 \leq i \leq n$$$) and a binary string of length exactly $$$b$$$ denoting the binary representation of $$$y$$$ (most significant bit first).

If $$$i > 0$$$, this line encodes the question: Is $$$a_i$$$ bigger than $$$y$$$?. There should be at most $$$3 \cdot (n+b)$$$ such lines; after each of them, the interactor will print yes or no in a single line.

If $$$i = 0$$$, this is the last round of interaction, after which your program should terminate, and $$$y$$$ should be the maximal value among the elements of Sphinx's array. Note that this round does not count to the query limit.

Note that the interactor is adaptive.

After printing a query, do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. 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 the documentation for other languages.

If your solution does not correctly follow the interaction guideline above, it may receive an arbitrary verdict. Otherwise, your program will receive the Wrong Answer judgment if it reports the wrong maximum.

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

Note:
In all examples, the sequence is fixed beforehand.

In the first example, the sequence is $$$2, 1, 4, 0, 6$$$.

In the second example, the sequence is $$$0, 0, 0, 0$$$.

In the third example, the sequence is $$$0$$$.

Note that if the interactor was adaptive, then the interaction in the first and the third example would not be sufficient to return the correct value of maximum.

Example input:
5 3

yes

no

no

no

no

yes

Example output:
5 101

5 110

4 100

3 101

2 001

1 000

0 110

Example input:
4 3

no

no

no

no

Example output:
1 000

2 000

3 000

4 000

0 000

Editorial:
First, we start with a slightly suboptimal solution using $$$5 \cdot (n + b)$$$ queries. We investigate the elements in order from $$$1$$$ to $$$n$$$. While doing so, we will keep the stack with some of these elements. Moreover, we will keep a prefix of the maximum we found till now. We keep the following conditions:
• The prefix of the maximum will have precisely the same length as the number of the elements on the stack
• $$$k$$$-th element on the stack (counting from the lowest element) will match at exactly $$$k$$$ bits with the current prefix.
Now, we describe how to add an element while keeping previous conditions. Assume that number of elements on the stack is $$$m < b$$$. If the current element is:
• smaller on the first $$$m$$$ bits than the current prefix, then delete it and proceed to the next element
• equal on the first $$$m$$$ bits to the current prefix, then find the value of $$$m + 1$$$ bit using the current number and add this element to the top of the stack
• larger on the first $$$m$$$ bits than the current prefix, then remove the last element of the stack and last bit of the prefix and try again to add the current element to the stack
Queries on the first $$$m$$$ bits can be done by filling the number with $$$0$$$s or $$$1$$$s on the remaining positions (depending on the type of query).
After we finish analyzing the sequence, we have $$$m$$$ elements on the stack and prefix of length $$$m$$$, a candidate for maximum. Now we want to find out if this is truly the prefix of the maximum, or maybe there is an element with a larger prefix.
To do this, we analyze the stack from its top. We take the top element, check if this larger on the first $$$m$$$ bits than the maximum, and if not, we remove it and proceed. Otherwise, if it is a $$$k$$$-th element on the stack, then we know it matches the current prefix on the first $$$k$$$ bits, so we keep only these first $$$k$$$ bits of the current prefix.
At the very end, we are left with some prefix of the maximum. If this prefix has length $$$b$$$, then the task is solved. Otherwise, we find all elements with the same prefix and recursively solve the task for smaller $$$b$$$ and $$$n$$$.
We quickly analyze the outlined solution. In the first phase, we ask at most $$$3$$$ queries per element when we add it and precisely one when we remove it. In the second phase, we ask as many queries as the stack's size (we can say that this is the query for removal). In the third phase, we use precisely $$$n$$$ queries, so in summary, we use $$$5 \cdot n$$$ queries. It can be proven that if we achieve the prefix of $$$k < b$$$ elements, then there are at most $$$k$$$ elements with such prefix. Using some potential, we can easily prove that the sum of the number of queries used in the algorithm is at most $$$5 \cdot (n + b)$$$.
Unfortunately, this is not enough. We optimize two parts of the solution. It is easy to observe that we can skip the third phase – if we get the prefix of length $$$k$$$, only the lowest $$$k$$$ elements from the stack can have this prefix. Some of them might be smaller on these bits, but this does not matter, as if we ever query them later, we will receive no as an answer. This is enough to achieve $$$4 \cdot (n + b)$$$ solution.
The second optimization is that we do not need elements on the stack to match the appropriate prefix exactly. It is enough to fulfill the following conditions instead:
• $$$k$$$-th element on the stack cannot be larger than the first $$$k$$$ bits of the prefix
• There is an element on the stack, which is at least as large as the current prefix.
This observation allows us to drop one query we used previously to determine if an element is smaller than the current prefix. This way, we achieve the demanded number of queries equal to $$$3 \cdot (n + b)$$$.