I hope you guys enjoyed participating in Encoding April 2020. We are extremely happy to see so many of you participating! Do feel free to share your valuable feedback using this form:

https://forms.gle/vqCXbiEqhcC1rHGE6

You can also use this thread to post your doubts or discuss solutions!

4 Likes

Can somebody just brief the approach for â€śCobbs and mazesâ€ť ?

PROBLEM LINK:CodeChef: Practical coding for everyone

@rahul_g

1 Like

For every entry and exit points you could run Dijkstra and see whats the shortest path to the other entry/exit points except itself. If the shortest path is less than K then the maze Fails. The maze PASSES if the shortest path considering all the entry/exit points is >= K. @cubefreak777

2 Likes

Use Floydâ€“Warshall algorithm for all-pair shortest path, then just check the min paths for all pairs in A.

Yes, I tried it but wouldnâ€™t that be O(n^3) and n is 10^3 so shouldnâ€™t it give a TLE ?

TLE solution : CodeChef: Practical coding for everyone

Wow I didnâ€™t notice the constraints. My O(n^3) passes anyway. Bad tests I guess.

1 Like

I canâ€™t understand how did your N^3 solution passed. I was also using the same approach( because earlier constraints written was N<=100) but I got **TLE** with O(n^3). Then I commented about it, and they said itâ€™s N<=1000, it was typo.

TLE solution : CodeChef: Practical coding for everyone

If tests were bad then why did the same approach of mine give TLE?

You can optimize your code by using ints instead of int64, and just use 1 matrix, not 2.

value of N has changed to 1000, how can you apply floyd warshall its compexity is O(N^3) alone?

please correct me if I am wrong but please check the constraints again

It was really a nice contest for me , I did 5 questions in 20 mins approx and was at rank 3 one moment, (very cool for me) but then I tried the Bob question , first I implement it in python it gave me TLE and run time errors then I switched to c++ and surprised to me it gave me runtime error and siegev error. I was bit shocked and left the contest

Hey, this link is for mu submission to Bob question, could you please help me figuring out where I was wrong why it was giving me run time errors?

Is it fine to run Dijkstra for 100 times with a graph of 1000 nodes?

I think yes. if dijkstra complexity is considered to be v^2, then 100* v^2 should pass. Or you could use priority Queue and reduce the dijkstra time complexity to vlog e

I looked into the solutionsâ€¦the test cases had instances where number of vertices were indeed 1000, but I dont know how the n^3 solution passed. Although c++ solutions with fast i/o were the ones that mostly passed, not all of them though. Also the question had no multiple test cases. It still unclear to me how the n^3 solution passed, which should not have. Many n^3 solutions in JAVA and python got TLE.

Thank you for pointing that out mid-contest mate! I overlooked it!

If you have done the next questionâ€¦Bobâ€¦please explain it

Yes @first_semester for Bob and the cookies what you were expected to do was a pretty straightforward bfs/dfs from source to destination. Out of all the path you had to count the number of paths that had the smallest length. However, you had to take care of the case where there may be multiple paths crossing a single point on the graph. I think thats all that you had to do!