Editorial for Max's Anger Contest Series 2 P4 - Number Anger - Olympiads Online Judge

Editorial for Max's Anger Contest Series 2 P4 - Number Anger

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

Subtask 1

Brute force each number in $[1, R]$ ~[1, R]~ and count it if it has $D$ ~D~ consecutive digits.

Time Complexity: $\mathcal{O}(R \log_{10}(R))$ ~\mathcal{O}(R \log_{10}(R))~

Subtask 2

Realize that this is a digit dynamic programming problem and can have a memoized state based on the index and other properties.

Many states can capture all the required information, but the reference solution used

the current index,
whether there have been $D$ ~D~ consecutive digits,
whether there has been a digit besides $0$ ~0~,
whether the current number is equal to $R$ ~R~ so far,
the count of consecutive digits,
and the current digit.

Time Complexity: $\mathcal{O}(\log_{10}(R)D)$ ~\mathcal{O}(\log_{10}(R)D)~

Comments

There are no comments at the moment.