Dementia "Helping Hand" question

help
1

In the question CodeChef: Practical coding for everyone
for n=7, I referred to accepted solution and checked for the answer and correct answer was 8 however from my side answer should be 7 by this way:
our initial array K looks like: K=[1,2,3,4,5,6,7]
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]

if we follow this way we can get answer smaller than 8 i.e 7
@admin, @dj_r_1 can you please look into this.

14 Likes
2

You changed 2 numbers in 1 step.

3

yes it should be 7 which two numbers are you talking about

4

Notice the last 2 numbers.

5

as stated in question " In one second any two of them can transfer knowledge to each other and knowledge level of both of them will become LCM(Ki,Kj),LCM(Ki,Kj). Here i and j are the index numbers of friends sharing knowledge."

so in last step I took index 6 and 7, is there any fault in choosing???

6

LCM of 210 (at index 6) and 42 (at index 7) is 210 not 420!

7

Oh yes,right but if I follow this way
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]

8

Yes you are right bro… please Start a new thread and tag admin let’s see what happens…

11

Actually I don’t know how to tag someone…

12

just add “@” before their user name… codechef admin is having “admin” as id

13

thanks I’ve done in this thread only

14

Great observation bro! Tag the admins

15

Correct

16

output for n=7 -> 8 seconds is getting accepted but i can do n=7 in 7 seconds.

1 2 3 4 5 6 7  initial 
1 2 12 12 35 6 35   +2 second ( selected i=3,j=4 and  i=5,j=7 )
1 2 420 420 420 6 420   +2 second (selected i=3,j=5 and i=4,j=7)
 3 remaining -> +3second  (select i= 1,2,6 with j=5)

I think test cases were weak?

17

Yes

18

More like wrong

1 Like
19

Can anyone please explain the algo for solving this problem? I could not get it. It will be a great help.

21

Absolutely correct.
I was following almost the same approach last night.
For : [1,2,3,4,5,6,7]
LCM = 3 X 4 X 5 X 7 = 420
Steps :
LCM 3 and 4 : [1,2,12,12,5,6,7]
LCM 5 and 7 : [1,2,12,12,35,6,35]
LCM 12 and 35 : [1,2,12,420,420,6,35]
LCM 12 and 35 : [1,2,420,420,420,6,420]
LCM 1 and 420 : [420,2,420,420,420,6,420]
LCM 2 and 420 : [420,420,420,420,6,420]
LCM 6 and 420 : [420,420,420,420,420,420,420]

Hence : total time should be 7 secs not 8.
This pattern can be continued for all numbers which have LCM as a product of 2^n (n>=2) type of numbers from the series which may have a discrepancy from the given correct solutions.

1 Like
22

please anyone who can tell …after this observation what is the correct solution of this problem

23

We are aware of this issue and we are currently trying to find the correct solution for this problem.

1 Like