IOI TC' KinderGarten

Any solutions?

This question can be related to partitions of an integer (say n), which is explained here. You can also see this as a partition of n coins into piles.

You can write a dp code to calculate the number of ways to partition n coins into any number of piles. For example there are four ways to partition 4 coins = (1+1+1+1), (1+1+2), (1+3), (4). For n = 30, the number of ways is 5604, which is pretty less.

In this question, see the contiguous empty gaps between children as piles of coins. If x children are already seated, then sum of coins in all piles should be equal to n-x and the number of toys which are required is equal to number of piles.

For example let us say there are 15 chairs and 3 people are already seated in the following order

0 0 0 0 0 1 0 0 2 0 0 0 0 0 3

(0 means empty chair)

here the gap between children 1 and 2 = 2, between 2 and 3 = 5, and between 3 and 1 = 5.

So this can be seen as 3 piles of coins of the form (2, 5, 5)

Now when you insert a child there are two possible outcomes,

  1. Number of piles increases by 1. When you place a child in the middle of a gap.
  2. Number of piles remain same. When you place a child at the edge of a gap.
  3. Number of piles decreases by 1, if you place a child in a gap if size 1.

You can write a recursive solution for this storing the state as sorted array of piles. In this question the condition of not using more than K toys can be met by traversing through only the states which contain less than or equal to K piles.