ALEXTASK - Editorial

alextask
basic-prog
editorial
lcm
nov16
simple

#1

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.


#2

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


#3

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


#4

@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.


#5

@srd091 thankyou :slight_smile:


#6

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


#7

@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


#8

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 ?


#9

For C++ users…

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


#10

@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


#11

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.


#12

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


#13

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

Thank You


#14

can someone plz point out whats wrong in my


[1]?


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

#15

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


thank you…


#16

Can somebody help me solve why this solution is wrong,


[1]
This code works for most cases but don't know for which it is failing. This code works in O(N).

Below are the test cases that i tested, ( which passed successfully )

    10
    10 2 3 10 4 5 4 3 3 4
    
    6
    3 4 5 4 4 3
    
    3
    2 3 5
    
    4
    1 8 7 11
    
    4
    4 4 5 6
    
    10
    1 3 4 2 6 7 10 44 1 2
    
    10
    10 2 3 10 4 5 4 3 3 4
    
    10
    1 3 4 2 6 7 10 44 1 2
    
    7
    58 59 100 10266 6844 10000 1000000
    
    4
    1000000000 1000000000 999999999 999999222
    
    5
    1000000000 2000000000 989898989 878787878
    
    2
    1 1
    
    2
    4 1


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

#17

can anyone explain task… actually i am not getting it


#18

what are u not getting

@soni_singh


#19

rather than checking every possibility we should lake the LCM of two smallest numbers in the array the should check for only those pair which in which element are then the LCM of smallest
for EXAMPLE

we have an array say

3,3498,45,435,656,67,4,10,5

we sort it

3,4,5,10,45,67,435,656,3498

then we took LCM OF 3 & 4 which is 12 and check for only those element which are less than 12


#20

Hi all,
I have tried the same logic first sorted the list ,
If there is ‘1’ in the array then the next element is the result.
Otherwise fining any similar elements , as the list is sorted the first such element is taken.
Then the lcm is taken between first element and rest of the array and min of that is returned.
Then depending on which is the lesser one, the result is calculate.
The code is here . what is it I am doing wrong?