Editorial for TLE '17 Contest 3 P6 - Donut Coupons
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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:
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 and
. To update the range
, we do the following.
- Add
to
- Add
to
- Add
to
- Add
to
To query the sum from to
, we get the value of
. To find the sum of a range, simply subtract the unwanted range (i.e.
to
).
This works because in the range , our query sum would be increased by 1 for each step we take to the right. This is represented by the multiplication of the
array.
Complexity:
To solve for the third subtask, we can use the same data structure. Note that the sum of . Since the summation formula here is quadratic, we need a third array to store our values. Create
, and let our at
now be
. However, since we don't want to run into fractional numbers, it is best to store the sums as a multiple of
and divide afterward.
An implementation of the data structure can be found here.
Complexity:
To solve the final subtask, we simply need to extend what we did in subtask 3. That is, find the summation formulas for . 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
, we simply need to store the summations times
inside
different BITs. Afterwards, query the sums as we did before and divide the value by
to get our real answer.
Complexity:
Note that the summation formulas change depending on your starting point, so for each update at , we are really looking to find the summation formula for the sequence
Comments