Editorial for Mock CCC '19 Contest 1 S4 - Pusheen Plays Neko Atsume


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.

This problem is a homage to CCC 2018 S4, which tripped up competitors who needed to constant optimize dynamic programming algorithms.

For the first subtask, the answer was guaranteed to be a power of two, as the recurrence collapses into being the product of two and an earlier term in the recurrence. This means that the query can be answered in \mathcal O(\log 10^9) by seeing how many steps it takes to get to a term of 1 in the recurrence.

For the second subtask, one could simply precompute all 10^5 answers directly.

The second subtask gives a hint as to how to solve the problem in its entirety. If we precompute only the first B entries in the recurrence, then we can answer a query in \mathcal O\left(\frac{X}{B} \right). This gives a runtime bound of \mathcal O\left(B + \frac{QX}{B}\right), so by AM-GM we want to set B = \sqrt{QX} \approx 10^7. In practice, this algorithm then runs in \mathcal O(10^7 + 100Q).

As a final implementation detail, an array of ints is much faster than a map or dict.


Comments

There are no comments at the moment.