Codenation Hiring test discussion

i came up with this solution for even paths but was late to submit. Also please someone share approach for first question i only passed 35/42 testcases for first.

3 Likes

Hey! I could also pass only 37/42 tests. Some unnoticable corner case maybe. How many did you solve overall?

I solved only the first one. I wasted too much time on second question and read the third one when it was too late. Probably third was the easiest one if my code uploaded above is correct.

1 Like

I solved first one with all testcases passed.

I solved the first one completely …for every number you can calculate how many numbers have number of divisors greater than that number in the other range …take the sum and after that if result for first is greater than second print A else if result is less print B else print DRAW

2 Likes

I calculated sum of divisors of all numbers in given range. And then used binary search to compare sum values between each pair of numbers in given two range.

1 Like

If we calculate winning probability, shouldn’t we look for how many numbers have divisors less than the number of div of given numbers? This approach gave me 37/42. Can you explain your logic of taking greater numbers…

For the graph problem, I had similar approach complexity wise. Gave TLE on 10 test cases and 6 passed…

dfs is O(n+m) .this shouldn’t give TLE.

Yes right. It should pass…:grinning:
But i did something very similar and got tle

upper bound of m is 10^5.

1 Like

But m was constrained to be min(1e5, n * (n + 1) / 2). I too had similar approach and same verdict

1 Like

You passed how many?

32 / 42 in 1st and 7 /16 in 3rd

1 Like

Hey can you please tell your exact approach. I did a dfs but i could pass only 8/16 test cases and rest were TLE. Can you share your code so that i can check where i went wrong.

Thanks in advance!


I didn’t submit this in the contest.

Thanks
I also pretty much had the same approach,but as others i also faced TLE in 8 cases. Maybe there is some more optimization.

can you share your code

How to solve the 2nd question (Constrained GCD Array)?

@all_too_well Bro can you please explain your code little bit , how your dfs function is working and how you are storing path in dp vector…?? :thinking: