Editorial for TLE '16 Contest 8 P3 - Fool's Sequence

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.

Author: d

The first step to finding the desired number is to determine how long the number is. Obviously, a number with fewer digits is less than a number with more digits.

We can use dynamic programming to find the number of Fool's numbers with a certain length. Obviously, there are $0$ ~0~ Fool's numbers with length $0$ ~0~ or $1$ ~1~, and $1$ ~1~ Fool's number with length $2$ ~2~ or $3$ ~3~ each. With lengths greater than these, $count(length) = count(length-2) + count(length-3)$ , since a Fool's number can be made by taking an existing Fool's number and appending $420$ ~420~ or $69$ ~69~. It is enough to calculate up to $count(125)$ ~count(125)~.

After using dynamic programming to find how long the desired Fool's number is, we now need to find the exact number, which happens to be the $n = (N-\sum_{i=2}^{length-1} count(i))^{th}$ Fool's number with the length we found. This gets rid of the Fool's numbers which are shorter than the correct length.

Suppose that the correct Fool's number currently has a prefix $P$ ~P~; $P$ ~P~ can be empty. We note that $P420$ ~P420~ is always less than $P69$ ~P69~, if $P420$ ~P420~ is possible. If there are enough Fool's numbers starting with $P420$ ~P420~ (the exact count is $count(length-len(P)-3)$ ~count(length-len(P)-3)~ since there are $length-len(P)-3$ ~length-len(P)-3~ characters remaining), the correct prefix must also start with $P420$ ~P420~. Otherwise, the correct prefix would be $P69$ ~P69~. If this occurs, we must now remove all $P420$ ~P420~s from $n$ ~n~. Keep going until the exact Fool's number is found, that is, until $n = 0$ ~n = 0~.

Time Complexity: $\mathcal{O}(T \times |ans|)$ ~\mathcal{O}(T \times |ans|)~, where $|ans|$ ~|ans|~ is the length of the answer, which is less than $125$ ~125~.

Comments

3

septence123 commented on April 21, 2017, 9:40 p.m.

What does the variable "N" refer to in the editorial?

3

mse387 commented on April 22, 2017, 8:49 p.m. ← edited →

N refers to the Nth Fool's number. (This is the input given to you)

2

r3mark commented on April 21, 2017, 11:15 p.m.

A specific $n$ ~n~ I think.

4

septence123 commented on April 21, 2017, 11:53 p.m. ← edited →

"If this occurs, we must now remove all P420s from N." How can N be a specific n if we are subtracting its fools number from it to find the correct fools number? Can someone please help me understand this?