PROBLEM LINK:
Author: kol_adm
Editorialist: dhirajfx3
DIFFICULTY:
Easy
PREREQUISITES:
Sorting
PROBLEM:
Given R Red frogs and G green frogs, each located on the line (initial position). Now each second the ith red frog moves vi units forward and similarly ith green frog moves ui units backward. Provide the maximum number of frogs that will be simultaneously located in the interval [A,B] both A and B inclusive, at any integer instant of time.
QUICK EXPLANATION:
For each frog find the time interval for which it is present in interval [A,B]. Then sort all the time intervals and find the instant at which number of time intervals that overlap are maximum.
EXPLANATION:
For each frog find the time interval for which it will be available in the interval [A,B].
Finding the interval for each frog:
Lets find the interval for any red frog then finding time interval of green frog can be derived similarly.
(Always_present denote those frogs which are always present in the interval [A,B], Pi denote the time interval for which the frog is in the [A,B])
- If frog doesn’t move, that is vi = 0 discard this frog if its not in [A,B] else add 1 to Always_present.
- Discard frog if it jumps over the [A,B] without staying inside for a second.
- Discard the frog if its located beyond B initially.
- If its already present in [A,B] then set Pi.start = 0 and set Pi.end = (B-ai)/vi
- If its not present in the interval and stays for at least one second then set Pi.start = (A-ai-1)/v+1 and set Pi.end = (B-ai)/vi (integer division in all cases)
The pseudo code below demonstrates how to do perform above steps:
(Here v[i] denotes the movement speed of frog i,
a[i] denotes the initial position of frog i,
P denotes the set of time intervals for which any frog is in
[A,B]. A,B and Always_Present have their usual meanings as described above. Here all divisions are integer division)
set_intervals(v, a, P, Always_present, A, B)
Interval I
for each red frog i :
if v[ i ] == 0 :
if a[ i ] >= A and a[ i ] <= B :
Always_present++
else
if a[ i ] >= A and a[ i ] <= B :
I.start = 0
I.end = (B - a[ i ])/v[ i ]
P.add(I)
else if a[ i ] < A:
I.start = (A - a[ i ] - 1) / v[ i ] + 1
I.end = (B - b[ i ]) / v[ i ]
if I.start <= I.end : // check jump condition
P.add(I)
See the image below, which shows all the conditions, also note that the if a frog jumps over [A,B] then its start time is greater than its end time.
Now we have seen how to obtain the time intervals for red frogs in which they will be in [A,B] similarly find the time intervals for green frogs and add their append their time interval vector to previously created time interval vector P for red frogs.
Now we will see how to get the point at which the overlapping of time intervals is maximum. For this we need to sort our calculated vector P with respect to start time then end time. (This can be done easily done for example in C++ just sort pair<long long,long long > P with std::sort.
Now we have time intervals in sorted order the pseudo code below demonstrates how to find the point at which overlapping is maximum and get the value of that maximum.
get_maxima(P,Always_Present)
S = multiset() // multiset in C++ or any other
data structure or container which allows
insertion,search and deletion
in logarithmic time
currently_overlapping = 0
Ans = 0
for each interval I in P:
while S is not empty and Smallest element of S < I.start:
delete Smallest element of S
--currently_overlapping
S.add(I.end)
++currently_overlapping
Ans = max( currently_overlapping, Ans)
return (Ans + Always_Present)
Note that in the above pseudo code P contains time intervals from both red and green frog and always present all frog inclusive of greed and red which are always present in the interval [A,B]
Lets see why the above algorithm works:
As show in the figure above, the point at which maximum overlapping occurs should be a point at which some time intervals begins, because that is the only point which first increases overlapping, and it is easy to see that we are evaluating the number of intervals overlapping at each start point of some time interval by ++currently_overlapping in the above pseudo code, i.e. after removing all those time intervals which end before the current interval I starts we remove from the multiset S decreasing the current_overlapping altogether.
If you are still not convinced, try to simulate the pseudo code on the image shown above.
Time complexity:
Sorting + Inserting and deleting from multiset =
O((R+G)log(R+G)) + O((R+G) log(R+G))
So, O((R+G)log(R+G))