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 = 4 N$

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 = 2 N + 1$ or $2N$ $2 N$

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 + X B + s + X X + s + X Y$ .
- 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 \leq N + 10$ , you can get nearly full points according to $Q$ $Q$ .

Comments

There are no comments at the moment.