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] and count it if it has D consecutive digits.

Time Complexity: \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 consecutive digits,
  • whether there has been a digit besides 0,
  • whether the current number is equal to R so far,
  • the count of consecutive digits,
  • and the current digit.

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


Comments

There are no comments at the moment.