ZIO08003 - Editorial

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 :slight_smile:

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 :frowning: 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 :slight_smile:

Special thanks to my mentor of ICPC for schools , @sarthakmanna sir and @avijit_agarwal sir for teaching me stars and bars method !

1 Like