# Dementia "Helping Hand" question

In the question https://www.codechef.com/DEM2020/problems/HELPHAND
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

14 Likes

You changed 2 numbers in 1 step.

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

Notice the last 2 numbers.

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???

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

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]

Yes you are right broâ€¦ please Start a new thread and tag admin letâ€™s see what happensâ€¦

Actually I donâ€™t know how to tag someoneâ€¦

thanks Iâ€™ve done in this thread only

Great observation bro! Tag the admins

Correct

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?

Yes

More like wrong

1 Like

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

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

please anyone who can tell â€¦after this observation what is the correct solution of this problem

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

1 Like