LCH15JGH - Editorial

PROBLEM LINK:

Practice
Contest

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:

  1. Add one family of size X to the set
  2. Remove one family of size X from the set
  3. 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.

RELATED PROBLEMS:

2 Likes

Is there a problem if we use unordered_map to store the number of families with a particular size and iterate over it to answer the queries?
I thought of the above idea while implementing my code. Sadly, it seemed to give me a WA for the first sub-task.
Since the problem statement is clear enough I am unable to find where I went wrong.

Code here

@ankitdhall Yes, it will be a problem. You have to deal with up to 10^5 queries and imagine that you have 10^5 different families. If you try to iterate over all of them for each query, it will result in TLE easily.

You need to output 0 if there are no families, not the original number of bananas.

I think there is a small typo. It is written as *Y M = Y - Y / M * Y** but it should be **Y M = Y - Y / M M

2 Likes

@noob333 Thanks a lot, it’s corrected now

The third approach can also be called a sqrt-optimisation/blocks method, but instead of dividing the array into blocks we divide the queries.
I’ve written it because someone might consider explanation in the editorial as some magic rather than a common approach.

1 Like

Could you please explain the calc() function from author’s solution more clearly? I understood the approach but but I don’t understand what the variables ‘minst’, ‘fin’ and ‘st’ mean.
Thanks!

Please format a bit better, initially I was wondering how Y % M = Y - Y/(M^2).

M*(Y/M) is a lot clearer.

Never mind, I saw another solution and understood the flow :slight_smile:

@superty, good point, it’s fixed now

I have a doubt regarding the time limit… it is too strict :frowning: … 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

My segment tree solution is also giving TLE for the second division. Here is the link- http://ideone.com/JxDfUG . What can I improve to make it faster?