Helping Hands

general
1

Can anyone explain how is the output for 7 is 8 when it should have been 7.
@admin

3 Likes
2

Can you show the 7 steps in which you will achieve this?

3

Actually the solution is number_of_primes[n] + n - 3. Before 7 there are 4 primes(2, 3, 5, 7). We need to find max power of each prime before n and multiple them with each other, then replace other elements.
For 7:
1 2 3 4 5 6 7
1 2 3 4 35 6 35
1 2 105 4 105 6 35
1 2 420 420 105 6 35
420 2 420 420 105 6 35
420 420 420 420 105 6 35
420 420 420 420 420 6 35
420 420 420 420 420 420 35
420 420 420 420 420 420 420

3 Likes
4

(6,7)=42
(4,5)=20
(4,6)=420
(5,7)=420
(1,7)=420
(2,7)=420
(3,7)=420

2 Likes
5

Yes Iā€™m also confused because from my side steps are
Optimal steps are: [1,2,3,4,5,6,7]->
[1,2,3,4,5,42,42]->
[1,2,3,20,20,42,42]->
[1,2,3,420,20,420,42]->
[1,2,3,420,420,420,420]->
[420,2,3,420,420,420,420]->
[420,420,3,420,420,210,42]->
[420,420,420,420,420,420,420]

and answer should be 7

2 Likes
7

yeah, i got the same problem

1 Like
8

please explain the solution number of primes+n-3

9

yes mine is coming 7
1 2 3 4 5 6 7
LCM(4,5)=20;
LCM(6,7)=42;
1 2 3 20 20 42 4 2
LCM(20,42);
LCM(20,42)=420;
1 2 3 420 420 420 420
4 + 3 = 7 operations.
can anybody tell where i am wrong please

2 Likes
10

I did this but my output is 8. Just that my solution had a TLE verdict

11

how it is 8 for 7 ony tell this much please

12

bruh if you are getting tle try to run for 10^6 on your computer copy paste the output in in a array of 10^6 and run the code again to get the output in O(1) time

1 Like
13

Actually, the final LCM must be LCM of all numbers, so it contains max power of each prime before N including.

14

The steps seem to be correct to me ā€¦ And now I am wondering how did my solution pass . My code gives 8 for this case. Thanks for putting up a discussion for this.

2 Likes
15

You need to create array of number_of_all_primes_before 1000000 just once to solve TLE issue.

16

Can you tell me whats wrong in my solution
https://www.codechef.com/viewsolution/36688944

17

yeah i know that about lcm of all numbers , i just dont get your solution. of using number of primes[n] +n -3

18

You need to create array of number_of_all_primes_before 1000000 just once to solve TLE issue and the answer will be number_of_all_primes_before[n] + n - 3 seconds.

19

@fyter_112
[1, 2, 3, 4, 5, 6, 7] =>
[1, 2, 3, 4, 5, 42, 42] =>
[1, 2, 3, 4, 210, 210, 42] =>
[1, 2, 3, 420, 420, 210, 42] =>
[1, 2, 420, 420, 420, 210, 42] =>
[1, 420, 420, 420, 420, 210, 42] =>
[420, 420, 420, 420, 420, 210, 42] =>
[420, 420, 420, 420, 420, 210, 420] =>
[420, 420, 420, 420, 420, 420, 420]

20

You are getting 4 as output for 4 while it should had been 3

21

Oh okay bro thanks