Any solutions?
https://drive.google.com/file/d/0BzVxp00eJ453dzR1UWhQT3BseDQ/view?usp=sharing
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,
- Number of piles increases by 1. When you place a child in the middle of a gap.
- Number of piles remain same. When you place a child at the edge of a gap.
- 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.
2 Likes