Editorialist: Shubham Matta
Problem link: https://www.iarcs.org.in/inoi/2016/zio2016/zio2016-question-paper.pdf
Short Description: Count the number of Chains containing Even Red Pegs.
Question Explanation and constraints:
So we cannot go between same pegs of adjacent columns.
R in column 1, Peg 1 can form link with either G in column 2 or R in column 2.
Solution :-
1. Naive Solution -
Let N = Number of columns
Maximum number of chains formed = 3*(2\wedge(N-1))
{ Choose any Peg in first column in 3 ways and for each of next column.}
So , In this method we can Naively check all the chains and consider all those chains with Even Number of Red Pegs.
However this method is tedious and time consuming.
We can think of another method where we actually get relation of a column depending on adjacent column , so we won’t have to go through all possible combination of chains.
2. Dynamic Method
Consider a function -> f(i,j,k) taking 3 values i,j,k.
Now lets define f,
f(i,j,k) - Number of chains starting at column ‘i’, with number of Red pegs in chain equals ‘j’ and originating from Peg ‘k’.
Explanation :
So now we are interested in a method where we can calculate the chains starting column 1 with Number of Red pegs in chain = 0,2,4,6,.......
Also one thing to be kept in mind is that each Configuration is Different . Hence we calculate total Number of Red Pegs (0,1,2,3,4,5….) in all chains starting from a particular column and a particular peg .
a)
Finally answer for above table will be :
f(1,0,1) + f(1,0,2) + f(1,0,3) +
f(1,2,1) + f(1,2,2) + f(1,2,3) +
f(1,4,1) + f(1,4,2) + f(1,4,3) +
f(1,6,1) + f(1,6,2) + f(1,6,3)
Now start from last column that is 6th column go down to first column
f(6,0,1) = 1 (since only chain is “B” with 0 red pegs)
f(6,0,2) = 1 (since only chain is “G” with 0 red pegs)
f(6,0,3) = 1 (since only chain is “G” with 0 red pegs)
Now since there is no Red peg in 6th column , and total Reds in any chain starting from 6th column is 0 .
Hence,
f(6,j,k) = 0 , For all 6>=j>=1 and 3>=k>=1
Now come to previous column 5:
f(5,0,1) = f(6,0,3) + f(6,0,2)=2 (as chains formed can be “GG”, ”GG” ,
Since from 1st peg of fifth column ,
we can go to 2nd or 3rd peg of 6th column.)
f(5,0,2) = f(6,0,1) + f(6,0,3)=2 ( as chains formed can be “BB” , “BG”)
f(5,0,3) = 0 ( As there is a Red in 3rd peg of column 5 ,
hence number of chains with 0 Number of Red Pegs starting from 3rd peg = 0)
Now for any peg of column ‘i’ there are two cases:
Case 1 :
If that peg is NOT Red:
For length j ->
Then :
f(i , j , 1) = f(i+1 , j , 2 ) + f(i+1, j , 3 ) ,
f(i , j , 2) = f(i+1 , j , 3) + f(i+1 , j , 1),
f(i , j , 3) = f(i+1 , j , 1) + f(i+1 , j , 2)
Case 2:
If the Peg is Red in (i)th column ,
Now since the peg is red hence we take the Number of pegs from (i+1)th column as ‘j-1’ to get a total Number of red pegs as ‘j’.
f(i , j , 1) = f(i+1 , j-1 , 2 ) + f(i+1, j-1 , 3 ) , if 1th peg is red in column i
f(i , j , 2) = f(i+1 , j-1 , 3) + f(i+1 , j-1 , 1), if 2th peg is red in column i
f(i , j , 3) = f(i+1 , j-1 , 1) + f(i+1 , j-1 , 2) if 3th peg is red in column i
PS . Evaluate base cases ie Number of pegs = 0 , before the finding for other lengths.
Ans for above test case with 6 columns = 40
FASTER WAY: (Modification of above)
Let f(i,j,k) denote the number of chains starting from cell (i,j) with a parity k (k can be: 0 or 1). In other words, k = [ number of red pegs encountered in our chain, if we start our chain at cell (i,j)] mod 2 (i.e. the remainder when we divide this by 2).
Calculating the number of chains with parity k, for the last column is straightforward:
If this cell contains a red peg, then the number of chains starting from this cell with parity 1 = 1 and parity 0 = 0, else the number of chains starting from this cell with parity 1 = 0 and parity 0 =1.
For the other columns, for a particular row, we can look at f(i+1,j+1,k) and f(i-1,j+1,k) to determine f(i,j,0) and f(i,j,1):
If our current cell has a red peg, it will change the parity, thus:
- f(i,j,0) = f(i+1,j+1,1) + f(i-1,j+1,1) and
- f(i,j,1) = f(i+1,j+1,0) + f(i-1,j+1,0)
Else it will not affect the parity of red pegs in this chain:
- f(i,j,0) = f(i+1,j+1,0) + f(i-1,j+1,0) and
- f(i,j,1) = f(i+1,j+1,1) + f(i-1,j+1,1)
Thus, we can compute f(i,j,k) for every cell. Eventually, we want to find the number of chains that start from column 0 and have an even number of red pegs, i.e., parity 0.
This is simply f(0,0,0) + f(1,0,0) + f(2,0,0).
You can also refer to this code: gEh2SH - Online Java Compiler & Debugging Tool - Ideone.com