Editorial for TLE '17 Contest 3 P6 - Donut Coupons - Olympiads Online Judge

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)$ $O (N Q)$

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]$ $[l, r]$ , 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)$ $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)$ $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)$ $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)$ $O (Q K \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.