How to solve Code Wars 3.0 COW3G?

I just wrote something (without logic) and it passed :stuck_out_tongue:
https://www.codechef.com/viewsolution/32401646
i found the largest number divisible by i and largest number divisible by i+1 (present in array) and took their lcm.
for i in range 1 to 1e5
It is completely WA for even small test cases :frowning:

1 Like

I see some people did lcm(a_{i}, a_{i+1}), but that was not correct. You have to amortize the solution with some break statements to make it faster or check for a certain amount of left-right may work. For some strong test case, checking for a certain amount of left-right may fail (but not sure). For the below test case some solution will fail.
4
2 5 8 12

3 Likes

I just saw one of my college mate passed it in O(n^2) these solutions should be marked wrong for providing justice to others

It’s okay for unrated contest… (it’s just for practice i think)

1 Like

that’s not going to happen bro
:joy:

1 Like

Please have a look at this thread also…is my logic correct or not?

yeah I was just kidding :slight_smile:

I found this problem hardest! I mean compare it to the difficulty level of the other 6 problems. Even the last one was way easier.

3 Likes

I sort the array in decreasing order and check when i get the gcd of two elements 1 the print the product and break
here is the link of my solution

1 Like

It seems like shady to me but comparing all pairs of distinct largest 1000 or so elements apparently gives correct results. I cannot prove it, but It seems to me that it should be correct, unless someone helps me see other way

can you prove it bro?

How can this even work on arrays where all elements have a common multiple, say [2, 4, 6] ??

bro I know its a wrong solution but because of weak test cases it passes

1 Like

it wont even work on input 2 3 4 8

@benmirt Sir,can you kindly explain your approach for the problem
CodeChef: Practical coding for everyone
PLease Sir,it would be of great help to others like me who could not solve.
Thanks in advance.

No I don’t mean it but even some 6-7 star guys have written the same code that’s why I wanna ask brother

I did it without any logic and seriously I don’t except AC
its just hit and trial method without any logic

1 Like

How to solve the last one?

OK, so you need to observe that at any time the number of RIGHT moves need to be greater equal to the number of DOWN. (Or the reverse). So it boils down to number of good bracket sequence problem.

I think you’ll take it from here. The answer is just \frac{2}{N}

1 Like

Number of correct bracket sequence is nth Catalan number. How to transform that to probability specifically coming to (1/n).