PROBLEM LINK:
DIFFICULTY:
Simple
PREREQUISITES:
LCM, basic programming skills
PROBLEM:
You are given N events, the i-th event will occur every Ai-th milliseconds. Find the first millisecond when at least two events is happening at that millisection.
EXPLANATION:
First subtask
A very straight forward way to solve this problem is to check for every millisection starting from the first millisecond whether at least two events will occur on that millisecond or not, we stop at the first millisecond in which at least 2 events occured at this millisecond and this will be the answer.
For example, let’s say in the first millisecond one event will occur then we go to check the second millisecond and let’s say no events happened then we go and check the third millisecond and for example 4 events will occur in that millisecond then we stop and the answer is 3.
but how to calculate the number of events which will occur in a particular millisecond (say x-th millisecond )? since i-th event will only occur in the milliseconds which are divisible by Ai then we should count the number of tasks in which x mod Ai = 0
so for each millisecond, we should iterate over the array A with a loop and keep a counter to the number of milliseconds which are divisible by the current millisecond, after that we check the counter, if it’s bigger than 1 then the answer is the current millisecond, otherwise we go and check the next day.
the complexity for this solution is O(N*answer), unfortunately since the answer can be large so this solution will not get full marks.
full solution
Since the required millisecond can be large then we need to find an idea that does not iterate over the milliseconds one by one.
One idea is to try to find a way that immediately calculate for a particular pair of events the first millisecond in which those two events will both occur in that millisecond, other events might also be by coincidence occur on that millisecond but that doesn’t matter us. if we find such a way then we just iterate through all pairs of events and apply that way on them then we select the minimum millisecond among all pairs.
now, given two events what is the first millisecond in which both tasks will occur? let’s say the indices of those two tasks are i and j, then such a millisecond must be multiple of both Ai and Aj, among all such milliseconds we should pick the minimum millisecond so we just need to calculate the least common multiple (LCM) of Ai and Aj and this will be the answer for this particular pair of tasks.
now let’s explain how to calculate LCM of two numbers (say A and B), there’s a well-known formula for it:
LCM(A,B) = A * B / GCD(A,B), where GCD(A,B) means the greatest common divisor of A and B, to calculate it we can use a very well-known euclidean algorithm which is described by the pseudo code below, basically it make use of the mathematical formula GCD(A,B) = GCD(A-B,B)
gcd(a,b):
if b==0 then return a
otherwise return gcd(b,a mod b)
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.
