Rin and The Unknown Flower
Contest: Codeforces Round 614 (Div. 1)
Difficulty rating: 3500
Tags: constructive algorithms, greedy, interactive, math

This is an interactive problem!

On a normal day at the hidden office in A.R.C. Markland-N, Rin received an artifact, given to her by the exploration captain Sagar.

After much analysis, she now realizes that this artifact contains data about a strange flower, which has existed way before the New Age. However, the information about its chemical structure has been encrypted heavily.

The chemical structure of this flower can be represented as a string $$$p$$$. From the unencrypted papers included, Rin already knows the length $$$n$$$ of that string, and she can also conclude that the string contains at most three distinct letters: "C" (as in Carbon), "H" (as in Hydrogen), and "O" (as in Oxygen).

At each moment, Rin can input a string $$$s$$$ of an arbitrary length into the artifact's terminal, and it will return every starting position of $$$s$$$ as a substring of $$$p$$$.

However, the artifact has limited energy and cannot be recharged in any way, since the technology is way too ancient and is incompatible with any current A.R.C.'s devices. To be specific:

- The artifact only contains $$$\frac{7}{5}$$$ units of energy.
- For each time Rin inputs a string $$$s$$$ of length $$$t$$$, the artifact consumes $$$\frac{1}{t^2}$$$ units of energy.
- If the amount of energy reaches below zero, the task will be considered failed immediately, as the artifact will go black forever.

Since the artifact is so precious yet fragile, Rin is very nervous to attempt to crack the final data. Can you give her a helping hand?

Interaction format:
The interaction starts with a single integer $$$t$$$ ($$$1 \le t \le 500$$$), the number of test cases. The interaction for each testcase is described below:

First, read an integer $$$n$$$ ($$$4 \le n \le 50$$$), the length of the string $$$p$$$.

Then you can make queries of type "? s" ($$$1 \le |s| \le n$$$) to find the occurrences of $$$s$$$ as a substring of $$$p$$$.

After the query, you need to read its result as a series of integers in a line:

- The first integer $$$k$$$ denotes the number of occurrences of $$$s$$$ as a substring of $$$p$$$ ($$$-1 \le k \le n$$$). If $$$k = -1$$$, it means you have exceeded the energy limit or printed an invalid query, and you need to terminate immediately, to guarantee a "Wrong answer" verdict, otherwise you might get an arbitrary verdict because your solution will continue to read from a closed stream.
- The following $$$k$$$ integers $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \le a_1 < a_2 < \ldots < a_k \le n$$$) denote the starting positions of the substrings that match the string $$$s$$$.

When you find out the string $$$p$$$, print "! $$$p$$$" to finish a test case. This query doesn't consume any energy. The interactor will return an integer $$$1$$$ or $$$0$$$. If the interactor returns $$$1$$$, you can proceed to the next test case, or terminate the program if it was the last testcase.

If the interactor returns $$$0$$$, it means that your guess is incorrect, and you should to terminate to guarantee a "Wrong answer" verdict.

Note that in every test case the string $$$p$$$ is fixed beforehand and will not change during the queries, i.e. the interactor is not adaptive.

After printing any query do not forget to print end of line and flush the output. Otherwise, you might 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.

Hacks

For hack, use the following format. Note that you can only hack with one test case:

The first line should contain a single integer $$$t$$$ ($$$t = 1$$$).

The second line should contain an integer $$$n$$$ ($$$4 \le n \le 50$$$) — the string's size.

The third line should contain a string of size $$$n$$$, consisting of characters "C", "H" and "O" only. This is the string contestants will have to find out.

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

Note:
Note that the example interaction contains extra empty lines so that it's easier to read. The real interaction doesn't contain any empty lines and you shouldn't print any extra empty lines as well.

Example input:
1
4

2 1 2

1 2

0

1

Example output:
? C

? CH

? CCHO

! CCHH

Example input:
2
5

0

2 2 3

1
8

1 5

1 5

1 3

2 1 2

1

Example output:
? O

? HHH

! CHHHH


? COO

? COOH

? HCCOO

? HH

! HHHCCOOH

Editorial:
To be fair, this is a complicated decision tree problem. I recommend instead of heading straight to read the main solutions for this, try to spend some time and come up with at least 2 solutions for the case when the query limit is 5/3 first.
<spoilers> There are many solutions when limit = 5/3, and I'll point 2 of them out. The difference between the two solutions is how you approach the string and build a decision tree out of those queries:
1. The easiest to come up with: disclose every joint of the string (which is equivalent to find every position $$$i$$$ that S[i]==S[i+1]). All remaining letters can be filled up with the nearest disclosed letter to it. This can be done by asking 6 queries: "CH", "HC", "CO", "OC", "OH", "HO". If none of the letters is disclosed, then all of the letters are the same. You can disclose all of them by asking 2 more queries of length n and determine what letter is it.
2. The most natural solution (in my opinion): The idea of this is to disclose at least one letter of the string, to disclose the rest with at most one string of length $$$2$$$ to $$$n$$$ each. We could do this by simply asking "C". This could go either way:
• If a 'C' is disclosed at a position $$$i$$$, we can disclose the position $$$i+1$$$ with one query of length $$$2$$$, $$$i+2$$$ with one query of length $$$3$$$, ... and so on. From there, undisclose position $$$i-1$$$ with a query of length $$$n-i+1$$$, $$$i-2$$$ with a query of length $$$n-i+2$$$, ... and so on.
• If no letter is disclosed, the problem narrows down to solve with a binary string and total cost of $$$2/3$$$. There are multiple ways to tackle this so I won't spend any more time to explain this case.
The key here is to come up with a strategy that works in all branches of the decision tree. And to do that, we must find a good starting query/set of queries to begin with.
In the two strategies above, number 1 is too brutal, and number 2 is too naive. But my main solution contains the essences which can be seen in both solutions. The main idea is to find a set of queries to begin with like strat #2 but would give us more hints and cost us less when things go the other way.
We'll start by asking queries with "CH", "CO", "HC", "HO", which in total have cost of $$$1$$$. That way, the non-disclosed parts can be one of those:
• Consecutive similar characters.
• A joint starting with "O".
Supposed that after four above queries and no occurrences were found at all, the string can now be only in one of those kinds:
• An entire string constructed by a single character.
• A string of form "OO...XX", with "X" being either "C" or "H". In other words, the string is constructed by $$$n_0$$$ characters "O", followed by $$$n_1$$$ characters "X" ($$$n_0 + n_1 = n$$$).
Proof for this is trivial.
We'll find the trace of large chunks of "C" or "H" (cannot find every trace since the cost limit is very tight here, the minimum length allowed should only be $$$3$$$). To do this, we'll ask queries "CCC" and "HHH" sequentially. If any of the two queries return occurrence(s), that means all occurrences of "C" or "H" has been revealed (and also guaranteed to completely inherit the right side of the string), any undisclosed characters on the left will obviously be "O". From here, we can conclude and return the original string.
However, if both queries return nothing, this means either the string contains only "O" characters or there are at most $$$2$$$ rightmost characters being "C" or "H". Given this, we ought to find the chunk of "O" by asking query "OOO" (similar logic to the former step). If it returns occurrence(s) and there are still undisclosed characters, we'll need another query of length $$$n$$$ to finalize: replacing all of the undisclosed positions to "C" then ask a query with that string, if it returns occurrence then "C" is for the missing characters, otherwise "H" is.
This method works because there will always be one chunk with length at least $$$3$$$ (on either end of the string), except two cases: "OOCC" and "OOHH".
You will get to this if all three above queries failed to return anything. However, since this is a matter of picking one from two, a single query of either string will work: the original string is the asked string if occurrence found, otherwise the other.
This is also the worst case in this branch. Total cost would be $$$1 + 3 \cdot \frac{1}{9} + \frac{1}{16} = 1.3958(3)$$$ - very close to the limit.
Back to the case that some occurrence(s) are found when after asking the $$$4$$$ joint queries. The logic now is pretty similar to strat #2 mentioned above however due to the more varied undisclosed patterns, we'll need to take some extra caution.
First of all, we'll start at the leftmost revealed segment, and disclose any hidden characters to the left of it. It's easy to see that the leftmost revealed character can never be "O", and since the leftmost hidden segment always come in one of two forms similar to the no-occurrence case branch above, you can always reveal the nearest character by assuming it is the same as the current leftmost revealed character and use it as a query to ask. If the assumption is incorrect, then it and any remaining hidden letters to the left of it will be "O".
Now that we have a fully revealed prefix, we'll extend it by revealing letters to the right. For simplicity, let's split into two cases: one when there are revealed letter(s) not within our current prefix, one when there is none.
If such revealed letters are found, consider the one being closest to our prefix. We can see that the hidden gap between our prefix and it can only be produced by some (probably none) characters being the same as our rightmost character in the prefix, followed by some (probably none) characters being the same as our leftmost character outside of the prefix. Thus, we can simply assume the next hidden character is the same as our rightmost in-prefix character, then ask the query. If the assumption is incorrect, fill it and all the remaining hidden characters in that segment with the other one.
If there are none, then the last hidden segment is again, similar to the no-occurrence case branch. However, we have a significant clue this time: our rightmost in-prefix character. If it is not "O", we can quickly fill all the hidden positions with it, otherwise, we'll keep asking query again, assuming the next hidden character is still "O": if incorrect, take another query to ask if either it is "C" or "H", and then fill it and all the other hidden ones.
** Example interaction:
The string is "COHHHH..." ($$$n = 50$$$, in other words the string is construct by appending $$$48$$$ character "H" to the string "CO").
=> 50
(Finding joints not starting at O)
? CH => 0
? CO => 1 1
? HC => 0
? HO => 0
(Now, the string can be deduced as "CO????...")
? COO => 0 (Assuming that the third character is still "O", sadly it isn't.)
? COC => 0 (Assuming that the third character is still "C", and it isn't either.)
(By now we can deduce the string to be "COHHHH....", since the fourth character and beyond cannot be anything other than "H" (otherwise it would have raised a signal in the joints queries)).
! COHHHH... => 1
** End of example.
The maximum cost for this will be ($$$i = 3$$$ because starting from a joint means we have at least $$$2$$$ found characters, incremented by $$$1$$$ by the character we're about to guess):
$$$$$$\displaystyle \max_{4 \le n \le 50} \left( 1 + \sum_{i = 3}^{n} \frac{1}{i^2} + \frac{1}{n^2} \right)$$$$$$
With $$$n$$$ going to positive infinity, the limit of this function will be $$$\frac{2 \pi^2 - 3}{12} < 1.4$$$, therefore this solution still works.
</spoilers>
Big credits to Sooke for making this problem more interesting by pointing out a way to reduce the initial limit (5/3) and make this problem much less trivial.