Editorial for TLE '17 Contest 3 P6 - Donut Coupons

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.

Author: kobortor

To solve for the first subtask, it is sufficient to simply loop through each restaurant to add the coupons, then loop through to query them.

Complexity: $\mathcal{O}(NQ)$ ~\mathcal{O}(NQ)~

To solve for the second subtask, we would use a data structure called the Binary Indexed Tree (BIT) to quickly update and query sums. Have 2 BITs, called $A$ ~A~ and $B$ ~B~. To update the range $\left[l,r\right]$ ~\left[l,r\right]~, we do the following.

Add $1$ ~1~ to $B[l]$ ~B[l]~
Add $-(l-1)$ ~-(l-1)~ to $A[l]$ ~A[l]~
Add $-1$ ~-1~ to $B[r+1]$ ~B[r+1]~
Add $(r-l+1)+(l-1)=r$ ~(r-l+1)+(l-1)=r~ to $A[r+1]$ ~A[r+1]~

To query the sum from $1$ ~1~ to $n$ ~n~, we get the value of $n B[n] + A[n]$ ~n B[n] + A[n]~. To find the sum of a range, simply subtract the unwanted range (i.e. $1$ ~1~ to $l-1$ ~l-1~).

This works because in the range $l \dots r$ ~l \dots r~, our query sum would be increased by 1 for each step we take to the right. This is represented by the multiplication of the $B[n]$ ~B[n]~ array.

Complexity: $\mathcal{O}(Q \log N)$ ~\mathcal{O}(Q \log N)~

To solve for the third subtask, we can use the same data structure. Note that the sum of $1+2+\dots+n = \frac{n(n+1)}{2} = \frac{1}{2}(n^2+n)$ . Since the summation formula here is quadratic, we need a third array to store our values. Create $C$ ~C~, and let our at $n$ ~n~ now be $n^2 C[n] + n B[n] + A[n]$ ~n^2 C[n] + n B[n] + A[n]~. However, since we don't want to run into fractional numbers, it is best to store the sums as a multiple of $2$ ~2~ and divide afterward.

An implementation of the data structure can be found here.

Complexity: $\mathcal{O}(Q \log N)$ ~\mathcal{O}(Q \log N)~

To solve the final subtask, we simply need to extend what we did in subtask 3. That is, find the summation formulas for $1^K+2^K+\dots+N^K$ ~1^K+2^K+\dots+N^K~. Note that this can either be generated from polynomial differences or found by searching wolfram alpha. After we find the formulas, which will be of degree $K+1$ ~K+1~, we simply need to store the summations times $(K+1)!$ ~(K+1)!~ inside $K+1$ ~K+1~ different BITs. Afterwards, query the sums as we did before and divide the value by $(K+1)!$ ~(K+1)!~ to get our real answer.

Complexity: $\mathcal{O}(QK \log N)$ ~\mathcal{O}(QK \log N)~

Note that the summation formulas change depending on your starting point, so for each update at $l+1$ ~l+1~, we are really looking to find the summation formula for the sequence $(x-l)^K, (x+1-l)^K, (x+2-l)^K, \dots$ ~(x-l)^K, (x+1-l)^K, (x+2-l)^K, \dots~

Comments

There are no comments at the moment.