Codenation Hiring test discussion

all_too_well · July 21, 2019, 7:57am

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.

ankur314 · July 21, 2019, 8:03am

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

all_too_well · July 21, 2019, 8:15am

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.

gech_guy · July 21, 2019, 8:16am

I solved first one with all testcases passed.

mathforce · July 21, 2019, 8:17am

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

gech_guy · July 21, 2019, 8:21am

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.

ankur314 · July 21, 2019, 8:24am

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…

ankur314 · July 21, 2019, 8:26am

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

all_too_well · July 21, 2019, 8:28am

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

ankur314 · July 21, 2019, 8:29am

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

all_too_well · July 21, 2019, 8:30am

upper bound of m is 10^5.

kshitij_07 · July 21, 2019, 8:30am

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

ankur314 · July 21, 2019, 8:30am

You passed how many?

kshitij_07 · July 21, 2019, 8:31am

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

sahil01123 · July 21, 2019, 8:36am

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!

all_too_well · July 21, 2019, 8:37am

I didn’t submit this in the contest.

sahil01123 · July 21, 2019, 8:43am

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.

syntaxhacker · July 21, 2019, 9:14am

can you share your code

fiwisr · July 21, 2019, 9:27am

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

rk_221b · July 21, 2019, 10:11am

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