Editorial for ICPC BAPC 2021 G - Gyrating Glyphs - Olympiads Online Judge

Editorial for ICPC BAPC 2021 G - Gyrating Glyphs

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.

Problem: Reverse engineer the $\le 20\,000$ $\leq 20 000$ operators using $\le 1400$ $\leq 1400$ queries: $\displaystyle f_n(a_0, \dots, a_n) := (\dots (((a_0\ op_1\ a_1)\ op_2\ a_2)\ op_3\ a_3) \dots op_n\ a_n) \bmod 10^9+7$ $f_{n} (a_{0}, \dots, a_{n}) := (\dots (((a_{0} o p_{1} a_{1}) o p_{2} a_{2}) o p_{3} a_{3}) \dots o p_{n} a_{n}) mod 10^{9} + 7$
First, solve the problem for $15$ $15$ operators with a single query $0, q_1, \dots, q_{15}$ $0, q_{1}, \dots, q_{15}$ .
Use this to find all operators in $20\,000/15 < 1400$ $20 000 / 15 < 1400$ queries.
Example with $30$ $30$ operators:

We consider the case with $15$ $15$ operators.
Let $0, q_1, \dots, q_{15}$ $0, q_{1}, \dots, q_{15}$ where $q_i$ $q_{i}$ is random in $\{1, \dots, 10^9+6\}$ ${1, \dots, 10^{9} + 6}$ .
For all $2^{15}$ $2^{15}$ possibilities for the $15$ $15$ operators, compute the query outcome.
If all outcomes are distinct ( $\bmod 10^9+7$ $mod 10^{9} + 7$ ) we have a lookup table.
If not, repeat with a new random query.

Comments

There are no comments at the moment.