igor.pisarev's blog

SPOJ — Saving BOB
By igor.pisarev, 10 years ago, translation, In English

I'm trying to solve this problem but got stuck.

Briefly, we are asked to count N-digit numbers such that the absolute difference in the adjacent digits is greater than or equal to K.
Constraints: 2 ≤ N ≤ 109, 0 ≤ K ≤ 9. Answer should be calculated modulo 109 + 7.

I tried to derive some recurrence relations for the number of possible combinations of i digits, and then calculate the answer by matrix binary exponentiation technique.

Some first formulas are:
K = 9: Fi = Fi – 1 = 1 (no leading zeroes so the only option is 90909...)
K = 8: Fi = Fi – 1 + Fi – 2 (as Fibonacci but with different base values, which can be found using brute-force, for instance)
K = 7: Fi = 2·Fi – 1 + Fi – 2 – Fi – 3
K = 6: Fi = 2·Fi – 1 + 3·Fi – 2 – Fi – 3 – Fi – 4
K = 5: Fi = 3·Fi – 1 + 3·Fi – 2 – 4·Fi – 3 – Fi – 4 – Fi – 5

But then it becomes more complicated. For example, when K = 4 and current digit is 5, you can continue with 0, 1 и 9, so it isn't clear to me how the number of combinations changes now.

If there exists a simplier solution, please share it or just give a hint.

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
10 years ago, # |
← Rev. 8   Vote: I like it +3 Vote: I do not like it

For k = 4, {3, 8, -6, -6} which mean

Fn = 3Fn - 1 + 8Fn - 2 - 6Fn - 3 - 6Fn - 4

For k = 3, {3, 15, 2, -1}

For k = 2, {4, 22, 11, -14, -3}

For k = 1, I am getting lazy now. But it is look like $F_n = 9 * F_{n - 1}$

k = 0, Fn = Fn - 1 = 9 of course.

P/S: Please help me check my result, my pencil and paper skill may contain bugs.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Naive program for checking all untested formulas above.

    Happy Programmers' day, I have a party with some (github) friend now, I will check above solution later.

    Update 0: tested, look correct from here.

    → Reply