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$ ~\le 20\,000~ operators using $\le 1400$ ~\le 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$
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$ ~\bmod 10^9+7~) we have a lookup table.
If not, repeat with a new random query.

Comments

There are no comments at the moment.