ZIO14003 - Editorial

editorial
, , , ,
1

PROBLEM LINK: ZIO 2014 Problem 3

Editorialist: Rohit Mazumder

PROBLEM:

Find the number of valid sequences of given length starting with a given digit from a 3x3 keypad. A sequence is considered to be valid if and only if every two consecutive digits in that sequence are adjacent in the keypad.

EXPLANATION:

Let f(x,y,z) be the number of valid codes of length z starting with the digit x and ending with the digit y, ( 1 <= x,y <= 9 ) and Sy be the set of the possible digits that can be there before y.

Present Digit(y) Previous Digit can be one of these (Sy)
1 2, 4
2 1, 3, 5
3 2, 6
4 1, 5, 7
5 2, 4, 6, 8
6 3, 5, 9
7 4 ,8
8 5, 7, 6
9 6, 8

Table 1 : Summarises the set of possible digits there can be before a given digit

Note that, f(x, y, z) = \sum_{s_i belongs\ to\ S_y} f(x, {s_i}, z-1)…(1)

And, answer to our subtasks are = ( \sum_{y=1}^9 f(x,y,z) )modulo 100…(2)

Let’s take the example in the question, to understand the above expressions clearly.

Say that I want to calculate the value of f(4,1,3). We know from table 1 that the digit 1 can only be placed after the digits {2,4}. So on appending a 1 at the end of all the sequences of length 2 ending in a 2 or a 4, we can get all the sequences of length 3 ending in a 1, i.e, f(4,1,3) = f(4,2,2) + f(4,2,4).

Again, the value of f(1,9,2)=0, since it is impossible for a sequence of length 2 to start with the digit 1 and end with the digit 9!

To find out all the sequences of length 3, starting with the digit 4, we have to calculate f(4,1,3) + f(4,2,3) + f(4,3,3) +…+f(4,9,3) = sum{f(4,3,y), 1<=y<=9}

Solving the subtasks:

Recurrences:

f(x, y, z) = \sum_{s_i belongs\ to\ S_y} f(x, {s_i}, z-1) …(1)

And, required answer = ( \sum_{y=1}^9 f(x,y,z) )modulo 100 …(2)

Where, x = Starting Digit of the sequence

y = Ending digit of the sequences

z = Length of sequence

Sy = Set of all possible digits that can occur before y .

Base Cases:

f(x, y, 1) = 1 ; when x=y (Since for length of sequence = 1, the starting and the ending digit must be the same.

In other words, the number of sequences of length 1, where the starting and ending digits are same is 1)

f(x, y, 1) = 0 ; when x not equals y( It’s impossible to have a sequence of length 1, where the starting and the ending digits are different. Hence the answer is 0)

We construct a 2D-DP table of (y * z) to compute the values of recurrence (1) and then add them up to calculate the answer according to relation (2).

Subtask 1:

x =2, z = 8

Step 1: Fill in the base case

f(x,y,1) = x ; when x=y

f(x,y,1) = 0 ; when x not equals y

1 2 3 4 5 6 7 8
1 0
2 1
3 0
4 0
5 0
6 0
7 0
8 0
9 0

Step 2: Fill in the rest of the table according to recurrence (1).

Note that we are required to calculate the answer modulo 100, hence we only need the last two digits of the answer. So to ease our calculation we fill in the table with only the last two digits of the values obtained.

For e.g: f(2,2,7) = f(2,1,6) + f(2,3,6) + f(2,5,6) = 34 + 34 + 64 = 132. Instead of filling the cell with 132, we’ve directly filled it with 32, to ease further calculations!

1 2 3 4 5 6 7 8
1 0 1 0 5 0 34 0 60
2 1 0 3 0 18 0 32 0
3 0 1 0 5 0 34 0 60
4 0 0 2 0 16 0 28 0
5 0 1 0 8 0 64 0 12
6 0 0 2 0 16 0 28 0
7 0 0 0 3 0 30 0 52
8 0 0 1 0 14 0 24 0
9 0 0 0 3 0 30 0 52

Step 3: Sum up the last column and take modulo 100

Answer = (60+60+12+12+52) mod 100 = 36

Subtask 2:

1 2 3 4 5 6 7 8 9 10
1 0 0 2 0 16 0 28 0 24 0
2 0 1 0 8 0 64 0 12 0 96
3 0 0 2 0 16 0 28 0 24 0
4 0 1 0 8 0 64 0 12 0 96
5 1 0 4 0 32 0 56 0 48 0
6 0 1 0 8 0 64 0 12 0 96
7 0 0 2 0 16 0 28 0 24 0
8 0 1 0 8 0 64 0 12 0 96
9 0 0 2 0 16 0 28 0 24 0

Answer = (96 + 96 + 96 + 96) mod 100 = 84

Subtask 3:

1 2 3 4 5 6 7 8 9 10 11 12 13
1 0 0 0 0 6 0 60 0 4 0 80 0 36
2 0 0 0 3 0 30 0 52 0 40 0 68 0
3 0 0 1 0 8 0 64 0 12 0 96 0 68
4 0 0 0 3 0 30 0 52 0 40 0 68 0
5 0 0 2 0 16 0 28 0 24 0 92 0 36
6 0 1 0 5 0 34 0 60 0 56 0 0 0
7 0 0 1 0 8 0 64 0 12 0 96 0 68
8 0 1 0 5 0 34 0 60 0 56 0 0 0
9 1 0 2 0 10 0 68 0 20 0 12 0 0

Answer = (36 + 68 + 36 + 68) mod 100 = 08

6 Likes
2

Someone told me about this problem; I don’t think the editorial method is very good.

This way is time-consuming, annoying, and difficult to check. Instead of storing “previous digit” vector, just repeat the process on 3x3 grids (i.e., for last subtask, draw 13 3x3 grids, the k-th with the dp values for the k-th iteration). It’s also time-consuming and annoying, but still better, because it’s much more intuitive. It’s quite difficult to draw this method on laptop editorial, in truth, but it should at least be mentioned…

2 Likes
3

I have another more efficient method for this problem, which apparently gives Wrong Answer on Subtask 3. Can anyone please help me to figure out what is wrong? Thanks.

Note that the number of sequences starting with a 1, is the same as the number of sequences starting with a 3, which is the same as the number of sequences starting with a 7, which is the same as the number of sequences starting with a 9. (This is true by symmetry) Similarly, the number of sequences starting with a 2, is the same as the number of sequences starting with a 4, which is the same as the number of sequences starting with a 6, which is the same as the number of sequences starting with a 8. So, let the number of sequences starting with a 1 of length n be f_1(n), let the number of sequences starting with a 2 of length n be f_2(n) and let the number of sequences starting with a 5 of length n be f_3(n). Note that we have the following recurrences according to adjacencies on the grid.

f_1(n) = 2f_2(n - 1)
f_2(n) = 2f_1(n - 1) + f_3(n - 1)
f_3(n) = 4f_2(n - 1)

From these recurrences, it is easy to get that f_2(n) = 8f_2(n -2), f_1(n) = 8f_1(n - 2), f_3(n) = 8f_3(n - 2). By these, we get correct answers for first and second subtasks, but wrong answers for third subtask, so I don’t know what’s wrong in my method. I would really appreciate it if someone helped. Thanks. :slight_smile: