Editorial for IOI '18 P1 - Combo - DMOJ: Modern Online Judge

Editorial for IOI '18 P1 - Combo

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.

Let $Q$ ~Q~ be the number of asks.

$N = 3$ ~N = 3~

Ask all possible strings until $N$ ~N~ is returned.

$Q = 4N$ ~Q = 4N~

Determine the characters of $S$ ~S~ from the beginning one by one.
For each position, try all four characters one by one.

$Q = 2N+1$ ~Q = 2N+1~ or $2N$ ~2N~

Determine the characters of $S$ ~S~ from the beginning one by one.
For the first position, determine the character by three asks. For each position except the first one, considering the constraint of $S$ ~S~, determine the character by two asks.
Or for each position, using conditional branches, determine the character by two asks.

$Q = N+2$ ~Q = N+2~

Determine the characters of $S$ ~S~ from the beginning one by one.
Except for the first or last position, determine the character by one ask as follows.
- Assume that the first character of $S$ ~S~ is, for example, A.
- Let $s$ ~s~ be the prefix of $S$ ~S~ already known.
- Ask $s+B+s+XB+s+XX+s+XY$ ~s+B+s+XB+s+XX+s+XY~.
- If the next character is B, then $|s|+1$ ~|s|+1~ is returned. If it is X, then $|s|+2$ ~|s|+2~ is returned. If it is Y, then $|s|$ ~|s|~ is returned.
Note that if $Q \le N+10$ ~Q \le N+10~, you can get nearly full points according to $Q$ ~Q~.

Comments

There are no comments at the moment.