3
$\begingroup$

I'm currently struggling with an algorithmic problem and I can't help but think this can be done with some mathematical trick I'm missing.

Knowing that a digit is considered 'pretty' in a number only if it's strictly greater than its adjacent digits and 'ugly' if it's strictly less than it's adjacent digits, we assign to each number a certain score defined as $\text{score} = |\text{ugly digits}| + \text{|pretty digits|}$.

Note that marginal (i.e. first and last) digits in a number can't be ugly or pretty since they have only one neighbor.

We are asked to do the following :

Find the sum total of the scores of each number in a particular interval, provided its endpoints.

Example:

Given the interval $[101, 105]$, we compute the score for each value in this interval and get the sum. So :

$score(101) = |\text{ugly digits(101)}| + \text{|pretty digits(101)|} = 1 + 0 = 1. $

$score(102) = |\text{ugly digits(105)}| + \text{|pretty digits(105)|} = 1 + 0 = 1.$

$$.....$$

$score(105) = |\text{ugly digits(102)}| + \text{|pretty digits(103)|} = 1 + 0 = 1.$

Hence, the sum total would be $5$ for the given interval. But the interval can get extremely large, with its right endpoint reaching up to $10^{12}$ and the left one going down to $1$.

I've looked for patterns in the binary representations and that didn't work. Then I thought there might be some combinatorial approach if we try to look at each possible digit and put it in every place it could be in the given range and count the cases when it's pretty or ugly, but I couldn't get anywhere with this either.

Any ideas would be welcome.

$\endgroup$

1 Answer 1

0
$\begingroup$

` 1. Let interval is [L, R] if L>1 F(L, R) = F(1, R) - F(1, L-1)

  1. Split F(1, X) to F(1, 9) + F(10, 99) ... + F(10^k, X)

To calculate F in such intervals, use dynamical programming. Point in space is the length of number prefix and two last digits of the prefix

`

$\endgroup$
1
  • $\begingroup$ Сonst * K for the F(10^k, X) You can precalculate F(1,9), F(10, 99), ... $\endgroup$
    – kotomord
    Oct 29, 2016 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.