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

**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 by seeing how many steps it takes to get to a term of in the recurrence.

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

The second subtask gives a hint as to how to solve the problem in its entirety. If we precompute only the first entries in the recurrence, then we can answer a query in . This gives a runtime bound of , so by AM-GM we want to set . In practice, this algorithm then runs in .

As a final implementation detail, an array of `int`

s is much faster than
a `map`

or `dict`

.

## Comments