ALEXTASK - Editorial

PROBLEM LINK:

Practice
Contest

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.

Can anybody explain why this code of mine in python gave NZEC for larger subtask?

1 Like

Can someone please point out what i have done wrong in this code?

@sourav0457 you are missing a couple of things, new line after each test case, fin is not long long int, second loop in which you are finding minimum will have j< index not j<=index, and a return statement at the end of program.

your solution of after these corrections link.

@srd091 thankyou :slight_smile:

1 Like

Can anybody explain why this code in C++ produces AC to task # 3 and #4 but WA for other tasks?

1 Like

@ravibitsgoa You have to find lcm of all pairs , but you have done it only for the least two no which is be incorrect. For example try this test case

1

3

4 5 6

Your code will output 20 (lcm of 4 and 5) , but answer should be 12 (lcm of 4 and 6).

Check my solution for this link text

@srd091 don’t think it will be a problem as t declared in inner while will hide outer t in the inner while block.

1 Like

I have a doubt, Cant we just sort the array and take the lcm of the first 2 elements (smallest 2 elements) ? Doesnt that produce a correct answer ?

For C++ users…

You guys can easily use inbuilt __gcd(… , …) to avoid hustle in writing all code of gcd() externally!

1 Like

@chari407 no it will be wrong.

try this test case

1

3

4 5 6

As per your algo o/p will be 20(lcm of 4,5) but it should be 12 (lcm of 4,6)

Check my solution for this link text

check in answers , have tried to explained this … if anything isn’t clear feel free to ask

Can anyone tell why I am getting wrong answer on task 2. I am applying the same method as provided in editorial. Here is the link.

@error_503_404 I think there is a slight issue with the test case you’re failing. More specifically, there is extra whitespace in the input file. Using strip() on each line solves the problem, see this. Or it is always safer to use the split() function without any parameters, as here. According to the Python documentation
If sep is not specified or is None, a different splitting algorithm is applied: runs of consecutive whitespace are regarded as a single separator, and the result will contain no empty strings at the start or end if the string has leading or trailing whitespace.

Hope this solves your problem.

Thanks for helping, smsubham. It was a trivial mistake.

1 Like

@d1k5 using double variables - very bad idea. Your solution was good, but if you use long long to calculate LCA, a[i] and a[j] must be long long too

@d1k5 your program is correct but you have used double type for calculating the answer. Double can store 15-17 digits of precision but the answer in the worst case may go up to 1000000000*999999999, which leads to loss of precision. A long long can store this comfortably, but try this multiplication with double types, you’ll see the problem :slight_smile:

2 Likes

Can anyone please tell what I have done wrong in this code in Java.

Thank You

can someone plz point out whats wrong in my


[1]?


  [1]: https://www.codechef.com/viewsolution/12045932

can anybody tell me why this code gives WA for the last testcase ?


thank you…