Sweets All Around - Need help

general
,
1

I was trying this problem and got an approach using segment tree lazy as:
Add 1 in range [x,y] for each n
Query to find maximum element

However, due to x,y being upto 10^9 I am unable to implement it. I think there’s a way of doing this which I am unaware of. It would be of great use if anyone can suggest me how to do this.
Here’s the question link: Sweets All Around

Thanks :slight_smile:

2

Hi @dishant_18 ! Actually u don’t need to use lazy propagation ! It can be done using Merge Sort Tree ! What we actually need is an integer value which completely lies with the given ranges (considering each input as a range) and also that integer value should be as minimum as possible and the number of ranges satisfying this particular value should be as maximum as possible ! So,the how to pick that minimum integer ? We can say that the minimum value will be any one of the starting ranges (i.e among all the ranges pick the starting point of that particular range and count how many ranges satisfy ! ) To do this we need to sort the ranges according to their starting points ! Then iterate through all ranges pick the starting value and count how many ranges satisfy this value ! How to count ?? Build a segment tree with ending point of every range as leaf node and merge two child’s to get elements in the parent node ! Then for every query of type “How many numbers are greater than the current number in the range (0,current_index) ?” , to do this we can use lower_bound on each completely overlapping segment and sum them up and return ! Out of all the queries modify the maximum value accordingly along with the minimum value as the current starting point of the range !
My AC code : https://www.hackerearth.com/submission/16653996/
If you have any doubts feel free to ask !
Happy coding :slight_smile:

2 Likes
3
  1. Use coordinate compression on the values and build a segment tree as usual.
    Even if the range is large, the total unique values you must consider is usually not as large. For example, in this problem X, Y \le 10^9 but total unique values of X and Y is at most 2N. So if you have K distinct values you can map each of these values to an integer in [1..K] (usually preserving the sorted order). Now you can build a segment tree on a range of size K and solve the problem.
  2. Use a dynamic segment tree.
    This is basically a normal segment tree but you start with the root and only create nodes when you need them. Your root covers the range [1..10^9]. Now if you have to do an update in the left or right half, you first create the child node if it does not yet exist, and then go down into the left or right child to update it. For queries you can gather the result from the existing nodes without having to create new ones. This is slightly less efficient than option 1 because the operations will take logarithmic time with respect to large range the tree is build on, but on the plus side you can answer queries online.
1 Like
4

Thank you :slight_smile:

5

Thank you :slight_smile:

6

No Need of segment Tree. First Use coordinate compression for X and Y. Now you may observe that after doing this you will have atmost 2*10^5 distinct elements left. Now when you are compressing X and Y , just store this mapping between original number and new mapped value in a map. After you have done this process X and Y values one by one. Suppose current student’s mapped range is x=mp[X] and y=mp[Y]. So adding one to a given range can be done by using this simple trick: A[x]+=1 and A[y+1]-=1. Here A is the array initialized to 0. Do this range addition for all students.

Once you have done this , just take the prefix sum from 1 to 210^5(in worst case). Now check all indices from 1 to 210^5 and find the smallest index having the maximum value. So simply this is the maximum no. of students that can be made happy and to get the minimum no. of candies just output the map value of the smallest index for which maximum value is encountered.

2 Likes
7

I had this approach in mind but had a very raw idea tbh. Thanks for sharing.