Editorial for COCI '15 Contest 1 #5 Relativnost

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.

Let us first solve the task for the case when there are no changes in requirements and we solve it under a constant number of requested colored paintings $a_i$ ~a_i~ and black and white paintings $b_i$ ~b_i~. We need to determine how many ways there are to choose different configurations of selling the paintings with the requirement that at least $C$ ~C~ paintings are colored. The initial problem when there are no changes in requirements is solved using dynamic programming. Let $dp_{i,j}$ ~dp_{i,j}~ denote the number of ways to choose the initial $i$ ~i~ transactions so that exactly $j$ ~j~ requirements are satisfied with colored paintings. The relation used to calculate $dp_{i,j}$ ~dp_{i,j}~ is:

$\displaystyle dp_{i,j} = dp_{i-1,j} \times b_i + dp_{i-1,j-1} \times a_i$

In the end, the solution is the sum of all $dp_{n,i}$ ~dp_{n,i}~ for each $i$ ~i~ greater than or equal to $C$ ~C~. The calculation can be simplified even more if we define $dp_{i,K}$ ~dp_{i,K}~ as the number of ways for not exactly $K$ ~K~ colored paintings, but at least $K$ ~K~ colored paintings. The solution that calculated this relation every time the requirements change has the complexity $\mathcal O(NC)$ ~\mathcal O(NC)~ and was good enough for $30\%$ ~30\%~ of total points.

In order to get all the points, you needed to find a way to efficiently maintain the relation value after changes have been made. The inspiration comes from the tournament tree. If you are not familiar with this structure, be sure to read the tutorial at https://wiki.xfer.hr/tournament/. (DMOJ curator's note: Good luck with this tutorial.) Under the assumption that now you know how tournament tree works, we continue solving the task.

The solution will be maintained in a way that every node of the tournament tree is used to store the number of ways to choose the paintings in that subtree for each number of chosen colored paintings from $0$ ~0~ to $K$ ~K~.

We are left with maintaining that relation after we change the requirements of one person. It is evident that it is fairly simple to calculate the change in result for each node in the tournament tree. The question is how to join two nodes.

Here we can notice that the number of ways of choosing the transaction over the entire subtree (consisting of the left - $L$ ~L~ and right child - $R$ ~R~) with at least $i$ ~i~ purchases of colored paintings is $T_s = \sum_{i=0}^s L_i \times R_{s-i}$ ~T_s = \sum_{i=0}^s L_i \times R_{s-i}~.

The total time complexity is $\mathcal O(K^2 (N+Q) \log N)$ ~\mathcal O(K^2 (N+Q) \log N)~.

Comments

There are no comments at the moment.