PROBLEM LINK:
Author: Pavel Sheftelevich
Tester: Roman Rubanenko
Editorialist: Paweł Kacprzak
DIFFICULTY:
Medium Hard
PREREQUISITES:
Math, [Fenwick tree][11111], Segment tree, Ad-hoc
PROBLEM:
There are initially N families of people of a different given size. You have to be able to handle 3 types of queries on the set of these families:
- Add one family of size X to the set
- Remove one family of size X from the set
- You will give Y bananas to every family in the set in such a way that for any particular family, all member of it will receive the same number of bananas and this number will be maximum possible i.e if a family has M members then every member will receive Y / M bananas and there will be Y % M bananas left. Your tast is to count the number of all bananas left in this process.
QUICK EXPLANATION:
Use the fact that x % y = x - (x / y) * y, where x / y is an integer division, so in order to calculate the number of bananas left you can avoid calculating modulo. To handle queries of the first and the second type you can use a [Fenwick tree][11111] or a Segment tree, which can answer two queries: how many total people are currently in families for which Y / M is equal and how many families are there for which Y / M is equal, where M denotes the number of people in one such family. If you are able to answer this question, in order to answer a query of the third type, you can iterate over all possible values of Y / M and accumulate the results.
EXPLANATION:
There are multiple very good approaches for this problem and almost all of them depends on the facts given above. I will sketch 3 of them:
SOLUTIONS BASED ON SEGMENT-TYPE-LIKE DATA STRUCTURE
As mentioned in quick explanation, you can use a data structure which can handle queries about segments, where a segment [L, R] corrensponds to all families with sizes in a range [L, R]. If you are able to keep track of these ranges, you can easily handle queries of first two types. In order to handle the third query, notice that there are many families of different sizes for which Y / M is equal, where M denotes a size of a family. Based on this fact, and the fact that Y % M = Y - (Y / M) * M, you can avoid calculating modulo on every such family and you can calculate a result for all such familis at once by querying the data structure about the number of people in families in a range [L, R] in which Y / M is equal for every family and querying it also about the number of families in the same range. Based on this two subresults, you can compute the number of bananas left in the process for each of family in [L, R]. If you sum these results over all possible values of Y / M you will get the result for the third query.
The complexity of these solutions are about O(log N * M * sqrt(max(Y)))
SOLUTIONS BASED ON BLOCKS
Rather than using a segment-based data structure, you can divide the range of possible family sizes in contant size blocks. You can use similar facts as in the above solution to get the results, but rather than querying for a particular range [L, R] you will divide it into two calculations of result for a range [1, L - 1] and [1, R] and you will subtract first from the second. In order to calculate the result for a given range [1, R] you will sum results for all full blocks which fit into the range and possibly one chunk at the end of the range for which you can calculate the result iterating over all its elements.
Let B be the number of used blocks and S be the size of one such block.
The complexity of these type solutions are about O(M * sqrt(max(Y)) + N * (B + S)) which can be an upgrade over the segment-tree-like data structure.
AD HOC SOLUTIONS
You can also keep it really simple and get away with using advanced data structures or blocks. A quick overview is that you can compute the results for families given initially in some way, then handle a portion of up to Q queries (Q is choosen arbitrary to fit the time limits, we saw contestants using Q = 200) by using previously computed results and bruteforcing over previous updates in current portion of queries. After you handle Q queries, you can rebuilt your current results and start with another Q queries.
The complexity of these type solutions depends on the implementation, but if done right with appropriate constants, they can be really fast for this problem.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
… my segment tree solution did not work and i had to change to B.I.T and even in my solution i had to change some of my variables from long long int to int :\ … isnt this too much… altough i m quiet new to the programming environment yet i feel that the tie limit was quiet strict…or was there something wrong with my implementation… admin i would like your comments on the same