Editorial for Art Academy VII: A Mysterious Object

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: astrocat879

For the $10\%$ ~10\%~ subtask, looping from $0$ ~0~ to $K$ ~K~ and checking if the number contains $10$ ~10~ as a subsequence passes. Make sure the number doesn't contain $100$ ~100~ as a subsequence.

For the remaining $90\%$ ~90\%~, we use dynamic programming.

The dp state should be $dp[index][state][less]$ ~dp[index][state][less]~.

$index$ ~index~ is between $0$ ~0~ and the number of digits in $K$ ~K~. It represents which digit you are at in $K$ ~K~.
$state$ ~state~ is either $0$ ~0~, $1$ ~1~, or $2$ ~2~. It represents zero previous occurrences of $1$ ~1~, a previous occurrence of $1$ ~1~, and a previous occurrence of a $1$ ~1~ and a $0$ ~0~, respectively.
$less$ ~less~ is either $0$ ~0~ or $1$ ~1~. It represents if the number being considered is currently less than $K$ ~K~.

The transition is left as an exercise to the reader.

Comments

There are no comments at the moment.