Editorialist : Sudheera Y S
Problem Link : ZIO 2008 Problem 3
Prerequisites : combinatorics , stars and bars , dp
Problem statement :
There are K boards to be hung on ‘N’ poles . Each board can be of length 1 or 2 and no two boards can share a common pole. Find the number of ways of doing so.
METHOD 1 : COMBINATORICS →
Subtask A :
N = 8 , K = 2
Let’s assume that the lengths of the two boards are L1 and L2
The first board is after X1 poles
The number of poles between both the boards is Y
There are X2 poles after the second pole
How many places are there to fill ?
A board takes the gap between two poles and not the poles , therefore we need to count the number of gaps between two consecutive poles and not the number of poles
The number of gaps between consecutive poles where the N is the number of poles is N-1
Therefore we have N-1 places to fill the boards and not N
Here is how it would look :
X1 L1 Y L2 X2 = 8-1 = 7
X1 + L1 + Y + L2 + X2 = 7
where
X1 , X2 >= 0
Y >= 1 : Because any pole cant have 2 boards
So now there is a problem as Y should be greater than 1 , so to make it 0 , we subtract 1 from both the sides and let our new variable Y’ be Y-1 and our new equation would be :
X1 + L1 + Y’ + L2 + X2 = 7-1 = 6
Now here , X1 , Y’ , X2 >= 0 , therefore we can apply the formula
We know that L1 , L2 should be 1 or 2
So let us take those cases and find out answers for each of them and we will add the answers for all the cases cases and we would get our answer 
Case 1 : L1 = 1 , L2 = 1 :
X1 + L1 + Y’ + L2 + X2 = 7-1 = 6
X1 + 1 + Y’ + 1 + X2 = 6
X1 + Y’ + X2 = 4
Formula for this is (3+4-1)C(3-1) = 6C2 = 15
Case 2 : L1 = 2 , L2 = 1 :
X1 + L1 + Y’ + L2 + X2 = 7-1 = 6
X1 + 2 + Y’ + 1 + X2 = 6
X1 + Y’ + X2 = 3
Formula for this is (3+3-1)C(3-1) = 5C2 = 10
Case 3 : L1 = 1, L2 = 2 :
X1 + L1 + Y’ + L2 + X2 = 7-1 = 6
X1 + 1 + Y’ + 2 + X2 = 6
X1 + Y’ + X2 = 3
Formula for this is (3+3-1)C(3-1) = 5C2 = 10
Case 4 : L1 = 2 , L2 = 2 :
X1 + L1 + Y’ + L2 + X2 = 7-1 = 6
X1 + 2 + Y’ + 2 + X2 = 6
X1 + Y’ + X2 = 2
Formula for this is (3+2-1)C(3-1) = 4C2 = 6
15 + 20 + 6 = 41
OBSERVATION : Here we observe that the answer for both case 2 and case 3 is the same because only the values of L1 and L2 are changing and it doesn’t matter. Instead of doing case 3 we could have just done 2* 5C2 = 20 = Case 2 + Case 3
Answer : 41
Subtask B :
N = 9 , K = 3
Number of places to fill - 8
Number of places before board 1 - X1
Number of places between board 1 and board 2 - Y1
Number of places between board 2 and board 3 - Y2
Number of places after board 3 - X2
Lengths of boards - L1 , L2 , L3
X1 L1 Y1 L2 Y2 L3 X2
Equation : X1 + L1 + Y1 + L2 + Y2 + L3 + X2 = 8
Y1 , Y2 >= 1 , subtracting 1 both sides two times ( one time for Y1 and another time for Y2 )
New equation : X1 + L1 + Y’1 + L2 + Y’2 + L3 + X2 = 8-1-1 = 6
Case 1 : L1 = L2 = L3 = 1 :
X1 + L1 + Y’1 + L2 + Y’2 + L3 + X2 = 6
X1 + 1 + Y’1 + 1 + Y’2 + 1 + X2 = 6
X1 + Y’1 + Y’2 + X2 = 3
Number of ways to do this : ( 3+4-1)C(4-1) = 6C3 = 20
Case 2 : L1 or L2 or L3 = 2 , other two 1 :
X1 + L1 + Y’1 + L2 + Y’2 + L3 + X2 = 6
X1 + 2 + Y’1 + 1 + Y’2 + 1 + X2 = 6
X1 + Y’1 + Y’2 + X2 = 2
Number of ways we can choose L1 or L2 or L3 = 2 → 3C1 = 3
Number of ways to do the above equation : (2+4-1)C(4-1) = 5C3 = 10
Total number of ways → 3*10 = 30
Case 3 : Any two of L1 , L2 , L3 = 2 , the other one is 1 :
X1 + L1 + Y’1 + L2 + Y’2 + L3 + X2 = 6
X1 + 2 + Y’1 + 2 + Y’2 + 1 + X2 = 6
X1 + Y’1 + Y’2 + X2 = 1
Number of ways we can choose two boards to have length 2 → 3C2 = 3
Number of ways to do the above equation : (1+4-1)C(4-1) = 4C3 = 4
Total number of ways → 3*4 = 12
Case 4 : All of them L1 , L2 , L3 = 2 :
X1 + L1 + Y’1 + L2 + Y’2 + L3 + X2 = 6
X1 + 2 + Y’1 + 2 + Y’2 + 2 + X2 = 6
X1 + Y’1 + Y’2 + X2 = 0
Number of ways to do the above equation : (0+4-1)C(4-1) = 3C3 = 1
20 + 30 + 12 + 1 = 63
Answer : 63
Now let us do Subtask D as K = 3 →
Subtask D :
N = 11 , K = 3
Number of places to fill - 10
Number of places before board 1 - X1
Number of places between board 1 and board 2 - Y1
Number of places between board 2 and board 3 - Y2
Number of places after board 3 - X2
Lengths of boards - L1 , L2 , L3
X1 L1 Y1 L2 Y2 L3 X2
Equation : X1 + L1 + Y1 + L2 + Y2 + L3 + X2 = 10
Y1 , Y2 >= 1 , subtracting 1 both sides two times ( one time for Y1 and another time for Y2 )
New equation : X1 + L1 + Y’1 + L2 + Y’2 + L3 + X2 = 10-1-1 = 8
Case 1 : L1 = L2 = L3 = 1 :
X1 + L1 + Y’1 + L2 + Y’2 + L3 + X2 = 8
X1 + 1 + Y’1 + 1 + Y’2 + 1 + X2 = 8
X1 + Y’1 + Y’2 + X2 = 5
Number of ways to do this : ( 5+4-1)C(4-1) = 8C3 = 56
Case 2 : L1 or L2 or L3 = 2 , other two 1 :
X1 + L1 + Y’1 + L2 + Y’2 + L3 + X2 = 8
X1 + 2 + Y’1 + 1 + Y’2 + 1 + X2 = 8
X1 + Y’1 + Y’2 + X2 = 4
Number of ways we can choose L1 or L2 or L3 = 2 → 3C1 = 3
Number of ways to do the above equation : (4+4-1)C(4-1) = 7C3 = 35
Total number of ways → 3*35 = 105
Case 3 : Any two of L1 , L2 , L3 = 2 , the other one is 1 :
X1 + L1 + Y’1 + L2 + Y’2 + L3 + X2 = 8
X1 + 2 + Y’1 + 2 + Y’2 + 1 + X2 = 8
X1 + Y’1 + Y’2 + X2 = 3
Number of ways we can choose two boards to have length 2 → 3C2 = 3
Number of ways to do the above equation : (3+4-1)C(4-1) = 6C3 = 20
Total number of ways → 3*20 = 60
Case 4 : All of them L1 , L2 , L3 = 2 :
X1 + L1 + Y’1 + L2 + Y’2 + L3 + X2 = 8
X1 + 2 + Y’1 + 2 + Y’2 + 2 + X2 = 8
X1 + Y’1 + Y’2 + X2 = 2
Number of ways to do the above equation : (2+4-1)C(4-1) = 5C3 = 10
56 + 105 + 60 + 10 = 231
Answer : 231
Subtask C :
N = 10 , K = 4
Number of places to fill - 9
Number of places before board 1 - X1
Number of places between board 1 and board 2 - Y1
Number of places between board 2 and board 3 - Y2
Number of places between board 3 and board 4 - Y3
Number of places after board 4 - X2
Lengths of boards - L1 , L2 , L3, L4
X1 L1 Y1 L2 Y2 L3 Y3 L4 X2
Equation : X1 + L1 + Y1 + L2 + Y2 + L3 + Y3 + L4 + X2 = 9
Y1 , Y2 , Y3 >= 1 , subtracting 1 both sides three times ( one time for Y1 and another time for Y2 and another time for Y3 )
New equation : X1 + L1 + Y’1 + L2 + Y’2 + L3 + Y’3 + L4 + X2 = 9-1-1-1 = 6
Case 1 : L1 = L2 = L3 = L4 = 1 :
X1 + L1 + Y’1 + L2 + Y’2 + L3 + Y’3 + L4 + X2 = 6
X1 + 1 + Y’1 + 1 + Y’2 + 1 + Y’3 + 1 + X2 = 6
X1 + Y’1 + Y’2 + Y’3 + X2 = 2
Number of ways to do this : ( 2+5-1)C(5-1) = 6C4 = 15
Case 2 : L1 or L2 or L3 or L4 = 2 , other three 1 :
X1 + L1 + Y’1 + L2 + Y’2 + L3 + Y’3 + L4 + X2 = 6
X1 + 2 + Y’1 + 1 + Y’2 + 1 + Y’3 + 1 + X2 = 6
X1 + Y’1 + Y’2 + Y’3 +X2 = 1
Number of ways we can choose L1 or L2 or L3 or L4 = 2 → 4C1 = 4
Number of ways to do the above equation : (1+5-1)C(5-1) = 5C4 = 5
Total number of ways → 4*5 = 20
Case 3 : Any two of L1 , L2 , L3, L4 = 2 , the other two is 1 :
X1 + L1 + Y’1 + L2 + Y’2 + L3 + Y’3 + L4 + X2 = 6
X1 + 2 + Y’1 + 2 + Y’2 + 1 + Y’3 + 1 + X2 = 6
X1 + Y’1 + Y’2 + Y’3 + X2 = 0
Number of ways we can choose two boards to have length 2 → 4C2 = 6
Number of ways to do the above equation : (0+5-1)C(5-1) = 4C4 = 1
Total number of ways → 6*1 = 6
Now , if we continue like this in the next step , our RHS would become negative 
which we can do in 0 ways , so we can skip this and directly find our answer
15 + 20 + 6 = 41
Answer : 41
METHOD 2 : DYNAMIC PROGRAMMING ( DP ) →
Let us define our dp table as follows :
Dp[ i ][ j ] = number of ways to arrange i signs between j poles
And our answer would be stored in dp[ K ][ N ]
Base case :
As we see , to hang i boards , we need at least 2i places
Therefore dp[ i ][ 2i ] = 1 and dp[ i ][ x ] = 0 where x < 2i
Dp[ 1 ][ 3 ] = ( j - 1) + ( j - 2) = 2 + 1 = 3
Dp[ 1 ][ j ] = (j-1) + ( j-2 ) = 2*j - 3 →
Because there is only one board and there are j places so we can put it in j-1 ways and if the length is 2 then we can put it in j-2 places .
Now is the recursion :
CASE 1 : Either we consider the jth pole :
Case 1 : The current length of the board we are considering right now is 1 :
We can do it just by adding the current board to the end , So we have i-1 boards ( -1 because of excluding current board ) and in j-2 places ( -2 because the length of the board is 1 )
Therefore the answer to this is dp[ i-1 ][ j - 2 ]
Case 2 : The current length of the board we are considering right now is 2 :
We can do it just by adding the current board to the end , So we have i-1 boards ( -1 because of excluding current board ) and in j-3 places ( -3 because the length of the board is 2 )
Therefore the answer to this is dp[ i-1 ][ j - 3 ]
CASE 2 : If we don’t consider the jth pole :
Then the answer is simply dp[ i ][ j-1]
Therefore , dp[ i ][ j ] = dp[ i ][ j-1 ] + dp[ i-1 ][ j-2 ] + dp[ i-1 ][ j-3 ]
Now , let us start filling the dp table :
Here we also note that the same dp table will be the same for all the testcases , so we can only maintain only one dp table . The maximum value of k is 4 and that of N is 11 . So we will do dp table of size 11*4
Rows are K and the columns are N
Here is how the dp table would look after doing the base case :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | |||||||||
| 2 | 0 | 0 | 0 | 1 | |||||||
| 3 | 0 | 0 | 0 | 0 | 0 | 1 | |||||
| 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Dp[ 1 ][ 3 ] = 2*3 - 3 = 3
Dp[ 1 ][ 4 ] = 2*4 - 3 = 5
Dp[ 1 ][ 5 ] = 2*5 - 3 = 7
Dp[ 1 ][ 6 ] = 2*6 - 3 = 9
Dp[ 1 ][ 7 ] = 2*7 - 3 = 11
Dp[ 1 ][ 8 ] = 2*8 - 3 = 13
Dp[ 1 ][ 9 ] = 2*9 - 3 = 15
Dp[ 1 ][ 10 ] = 2*10 - 3 = 17
Dp[ 1 ][ 11 ] = 2*11 - 3 = 19
And our dp table will be :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 |
| 2 | 0 | 0 | 0 | 1 | |||||||
| 3 | 0 | 0 | 0 | 0 | 0 | 1 | |||||
| 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Now k = 2
Dp[ 2 ][ 5 ] = dp[ 2 ][ 4 ] + dp[ 1 ][ 2 ] + dp[ 1 ][ 3 ] = 1 + 1 + 3 = 5
Dp[ 2 ][ 6 ] = dp[ 2 ][ 5 ] + dp[ 1 ][ 3 ] + dp[ 1 ][ 4 ] = 5 + 3 + 5 = 13
Dp[ 2 ][ 7 ] = dp[ 2 ][ 6 ] + dp[ 1 ][ 4 ] + dp[ 1 ][ 5 ] = 13 + 5 + 7 = 25
Dp[ 2 ][ 8 ] = dp[ 2 ][ 7 ] + dp[ 1 ][ 5 ] + dp[ 1 ][ 6 ] = 25 + 7 + 9 = 41 ( SUBTASK A )
Dp[ 2 ][ 9 ] = dp[ 2 ][ 8 ] + dp[ 1 ][ 6 ] + dp[ 1 ][ 7 ] = 41 + 9 + 11 = 61
Dp[ 2 ][ 10 ] = dp[ 2 ][ 9 ] + dp[ 1 ][ 7 ] + dp[ 1 ][ 8 ] = 61 + 11 + 13 = 85
Dp[ 2 ][ 11 ] = dp[ 2 ][ 10 ] + dp[ 1 ][ 8 ] + dp[ 1 ][ 9 ] = 85 + 13 + 15 = 113
Now the dp table would be like this :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 |
| 2 | 0 | 0 | 0 | 1 | 5 | 13 | 25 | 41 | 61 | 85 | 113 |
| 3 | 0 | 0 | 0 | 0 | 0 | 1 | |||||
| 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Now k = 3 :
Dp[ 3 ][ 7 ] = dp[ 3 ][ 6 ] + dp[ 2 ][ 4 ] + dp[ 2 ][ 5 ] = 1 + 1 + 5 = 7
Dp[ 3 ][ 8 ] = dp[ 3 ][ 7 ] + dp[ 2 ][ 5 ] + dp[ 2 ][ 6 ] = 7 + 5 + 13 = 25
Dp[ 3 ][ 9 ] = dp[ 3 ][ 8 ] + dp[ 2 ][ 6 ] + dp[ 2 ][ 7 ] = 25 + 13 + 25 = 63 ( SUBTASK B )
Dp[ 3 ][ 10 ] = dp[ 3 ][ 9 ] + dp[ 2 ][ 7 ] + dp[ 2 ][ 9 ] = 63 + 25 + 41 = 129
Dp[ 3 ][ 11 ] = dp[ 3 ][ 10 ] + dp[ 2 ][ 8 ] + dp[ 2 ][ 10 ] = 129 + 41 + 65 = 231 ( SUBTASK D )
Now our dp table would be like this :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 |
| 2 | 0 | 0 | 0 | 1 | 5 | 13 | 25 | 41 | 61 | 85 | 113 |
| 3 | 0 | 0 | 0 | 0 | 0 | 1 | 7 | 25 | 63 | 129 | 231 |
| 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Now k = 4 :
Dp[ 4 ][ 9 ] = dp[ 4 ][ 8 ] + dp[ 3 ][ 6 ] + dp[ 3 ][ 7 ] = 1 + 1 + 7 = 9
Dp[ 4 ][ 10 ] = dp[ 4 ][ 9 ] + dp[ 3 ][ 7 ] + dp[ 3 ][ 8 ] = 9 + 7 + 25 = 41 ( SUBTASK C )
Dp[ 4 ][ 11 ] = dp[ 4 ][ 10 ] + dp[ 3 ][ 8 ] + dp[ 3 ][ 9 ] = 41 + 25 + 63 = 129
Now our dp table would look like this :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 |
| 2 | 0 | 0 | 0 | 1 | 5 | 13 | 25 | 41 | 61 | 85 | 113 |
| 3 | 0 | 0 | 0 | 0 | 0 | 1 | 7 | 25 | 63 | 129 | 231 |
| 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 9 | 41 | 129 |
Answers :
Subtask A : 41
Subtask B : 63
Subtask C : 41
Subtask D : 231
Hope you understood both the methods
Special thanks to my mentor of ICPC for schools , @sarthakmanna sir and @avijit_agarwal sir for teaching me stars and bars method !