Editorial for Koala Ball


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Subtask 1

This subtask was intended to reward brute force solutions. For each basket, we loop over all ball types and place any number of the current ball type into the basket. After recursing through all B baskets, we check the validity of the current arrangement and increment ans.

Time Complexity: \mathcal{O}(N \cdot \prod_{i=1}^T t_i^B)

Subtask 2

For this subtask, we employ dynamic programming and Stars and Bars. Before setting up our solution, we must first precalculate factorials. Defining S as the total number of balls over all types, we can preprocess factorials in \mathcal{O}(S+B) time. This will allow us to calculate \binom{p}{q} \bmod 10^9+7 in constant time.

Now, we explain the concept behind our solution. Since all types of balls are independent and there are no limits to the size of the baskets, we can calculate the arrangements for each type of ball independently. Notice that the positions of the rule segments do not matter, and we only value the length of each of them. Noticing this, we can store the rules by their lengths and the type they apply to. Now for every ball type, we perform DP with the state as follows: dp[i][j] stores the number of ways we can split j balls into the segments indicated by the first i rules. Let us define len as length of the current rule segment. We can then implement the transition. dp[i][j] = \sum_{k=j}^{b_i} dp[i-1][j-k] \cdot \binom{k+len-1}{len-1}. Here we simulate putting j-k balls into the baskets affected by the first i-1 rules, with k balls being put into the current rule segment.

After completing the calculation of our DP table, we know the number of ways to arrange j balls into all of the baskets affected by rules. Now we must account for the number of ways we can put j balls into baskets affected by rules and the other t_i-j balls of that type into unaffected baskets. These can be calculated by looking up some values in the DP table and calculating the number of ways to put the rest of the balls into unaffected baskets using Stars and Bars. Finally, we can find our answer as the sum of the number of ways over all ball types.

Time Complexity: \mathcal{O}(\sum_{i=1}^R b_i \cdot t_{a_i} + \sum_{i=1}^T t_i + S + B)


Comments

There are no comments at the moment.