RodionGork's blog

By RodionGork, 2 months ago, In English

The problem calls digits in integer number "special" if they are "local maximum" (2 points) or "minimum" (1 point) among neighbors. And asks to calculate points for all numbers in a given range. It won't be hard for bruteforce if ranges are not on order 10^18 :) Thus it is most probable some kind of DP but I'm completely out of ideas how exactly to approach it. If someone can give such a subtle hint as direct me without spoiling the solution, it would be great!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Digit Dp

try to calculate it for all numbers from 0 till n1 and 0 till n2 and substract them for the answer in the range

let a be the first digit , b be the second digit and c be the third digit

we will have to add 2 when a < b and b > c or we will have to add 1 when a > b and b < c in the dp try to do something with this