noogler's blog

Knight's move problem
By noogler, 10 years ago, In English

Hello everybody, I have no idea to this problem, have you ?

Chess association decided to assign new phone numbers to all the members.

The new numbers should be produced with a knight's move on a phone keypad. 0 and 8 are not valid leading digits.

For instance, the number 340-49-27 matches the criteria.

7  8  9
4  5  6
1  2  3
   0

Create a program that computes the number of different phone numbers with a length N.

1 ≤ N ≤ 56'789

It is standard problem with small N, which can be solved by dynamic programming.

I tried to solve it with Matrix Exponentiation (of size 10x10). But it also TL ( O(10 ^ 3 * logn * BigInt) ), because of the multiplying very big numbers.

Tags dp
  • Vote: I like it
  • +10
  • Vote: I do not like it

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

there are exactly 2 available moves for each digit. So the answer is 8·2N - 1 = 2N + 2

Similar problem: 166E - Tetrahedron

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

    wow) good solution. thanks.

    upd. :(

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

    Your solution is not right. Because, for 6 and 4 there are 3 moves, for 5 there is no move.

    → Reply
»
10 years ago, # |
  Vote: I like it -6 Vote: I do not like it

i don't think u need BigInt here. these kind of problems with very large answers usually ask to output the answer modulo some number (mostly 10^9 + 7).

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am sure , we need BigInt. Without BigInt Matrix exponentiation will pass.

    → Reply
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

You can simply use a dp like this:

dp[i][j] = max( dp[i-1][k]/ k all possibles knights moves destination from j)

For sample 

dp[i][8]=max(dp[i-1][3],dp[i-1][1])

Then you initialise 

dp[0][j] = 1 (j != 8 && j != 0)

and the final result will be 

sum(dp[n-1][j]/ 0<=j<=9)

Complexity: O(N * 10)

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

    Why max? maybe sum ?

    This dynamic programming didn't pass, Time Limit,

    Because of the BigInt.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

facha resurrected this post. I don't know if you solved it meanwhile, but I decided to give it a shot.

Since matrix exponentiation times out, I looked for patterns by writing a brute force for small N and check the number of paths for each valid starting number [1-9] \ {8}. There are 3 sets of numbers: {2}, {4, 6} and {1, 3, 7, 9}. Numbers in each set have the same number of valid paths.

set \ N |  1  |  2  |  3  |  4  |  5  |  6  |  7
-------------------------------------------------
   2    |  1  |  2  |  4  | 10  | 20  | 52  | 104
1,3,7,9 |  1  |  2  |  5  | 10  | 26  | 52  | 136
  4,6   |  1  |  3  |  6  | 16  | 32  | 84  | 168

There are obvious patterns. If N is even,

  • ways(N+1, "1,3,7,9") = ways(N, "1,3,7,9") + ways(N, "4,6")
  • ways(N+1, "2") = 2 * ways(N, "2")
  • ways(N+1, "4,6") = 2 * ways(N, "4,6")

If N is odd,

  • ways(N+1, "1,3,7,9") = 2 * ways(N, "1,3,7,9")
  • ways(N+1, "2") = ways(N+1, "1,3,7,9")
  • ways(N+1, "4,6") = 2 * ways(N, "4,6") + ways(N, "1,3,7,9")

So we can solve this problem in O(N) * O(BigInt addition). I wrote a simple python script that solves N=56789 in 0,4s in my computer.

→ Reply