Feedback and Discussion for Encoding April 2020

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

https://www.codechef.com/viewsolution/32310191
My soln which game me Run time error :frowning:

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!

what is the use of rank in codechef

The use of rank in Codechef is similar to the use of ranks in any other competitive event around the world for any competition, i.e, to assess how good your performance was compared to others.

2 Likes

i always get successfully executed but while submiting it gives wrong answer why?

Maybe the logic that you are trying to implement misses some test condition that you might not have thought of! Usually if there is wa, then you should do a dry run of your code and see if it produces correct output on some self produced test cases.

1 Like

Okay thanks a lot!

Just keep practising, you’ll slowly get the hang of it!

1 Like

OMG,how fast do you code sir???

1 Like

hey please don’t call me sir, as I mentioned in my id name, I m in second semester (I made this id when I was in first semester)…for initial questions, I prefer Python maybe that give me advantage

So we can find the smallest path using Dijkstra but how we will count multiple paths of same length. Little bit confused, it would be highly appreciating if you help and thanks for helping me in COBB and MAZES, finally I got AC in it after using Dijkstra

1 Like

You will never miss a contest again.

A Companion to your Competitive Programming Schedule

In my busy schedule, there are a lot of moments when I forgot to take part in a contest on major platforms. So I developed an app that notifies me before every contest. Presenting the lightest app for your Coding Calendar.

Kody Alarm — Coding Calendar You will never miss a contest again.

Download Links

You can download it from Play Store using this link Kody Alarm - Coding Calendar

or

Download Kody Alarm

Main Features

  • Major Platform supported — Codeforces, AtCoder, TopCoder, Codechef etc
  • You can set a reminder for any contest on any major platform
  • You can turn on automatic notification so that I will be notified prior to any contest.

You can download it from Play Store using this link Kody Alarm - Coding Calendar

or

Download Kody Alarm

4 Likes

Hey!
editorial for Bob wants cookies:

Comment if you have any doubts.

2 Likes

Great :heart:

Thanks I got the solution

2 Likes