Editorial for Koala Ball
Submitting an official solution before solving the problem yourself is a bannable offence.
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 baskets, we check the validity of the current arrangement and increment .
For this subtask, we employ dynamic programming and Stars and Bars. Before setting up our solution, we must first precalculate factorials. Defining as the total number of balls over all types, we can preprocess factorials in time. This will allow us to calculate 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: stores the number of ways we can split balls into the segments indicated by the first rules. Let us define as length of the current rule segment. We can then implement the transition. . Here we simulate putting balls into the baskets affected by the first rules, with balls being put into the current rule segment.
After completing the calculation of our DP table, we know the number of ways to arrange balls into all of the baskets affected by rules. Now we must account for the number of ways we can put balls into baskets affected by rules and the other 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.