SPOJ - Flower Growing

Recently solved problem #4477 - FLOWGROW.

If you want to solve the problem yourself - stop reading now.

Solution - Combinatorics

The hard part is to calculate the number of possibilities to fill one row of flowers; to obtain the final answer, raise this number to the number of rows.

Let S(c,n) be the number of ways to fill n columns with exactly c colours, when only c colours are available:

S(1,n) = 1

S(2,n) = 2ⁿ-2xS(1,n)

S(3,n) = 3ⁿ-3xS(2,n)-3xS(1,n)

S(4,n) = 4ⁿ-4xS(3,n)-6xS(2,n)-4xS(1,n)

S(5,n) = 5ⁿ-5xS(4,n)-10xS(3,n)-10xS(2,n)-5xS(1,n)

S(6,n) = 6ⁿ-6xS(5,n)-15xS(4,n)-20xS(3,n)-15xS(2,n)-6xS(1,n)

S(7,n) = 7ⁿ-7xS(6,n)-21xS(5,n)-35xS(4,n)-35xS(3,n)-21xS(2,n)-7xS(1,n)

The factors being numbers from Pascal's triangle.

To calculate T(c,n), the number of ways to fill n columns with at least c colours from all 7 available colours:

T(7,n) = S(7,n)

T(6,n) = T(7,n)+7xS(6,n)

T(5,n) = T(6,n)+21xS(5,n)

T(4,n) = T(5,n)+35xS(4,n)

T(3,n) = T(4,n)+35xS(3,n)

T(2,n) = T(3,n)+21xS(2,n)

T(1,n) = T(2,n)+7xS(1,n)

The factors being numbers from the seventh row of Pascal's triangle.

When there are less than 7 columns, some of the calculations are skipped; the second part is only carried on as far as needed.

Faster optimizations are possible.
Note, "Time limit: 0.100s - 1.5s".

My SPOJ account

Woohoo! 60 problems!