what is the time and space complexity of Dijkstra's algorithm? In the wikipedia article it's given that if the priority queue is implemented as a binary heap,then time complexity is bounded by O( (E+V) log(V)). This makes sense,but also somewhere I have seen it's given O ( Elog(V)). I'm wondering which is more precise. I suspect the former one is more precise. What do u say guys?? Any answer will be appreciated.
Yesterday night I went to the nearby cyber cafe to attend the first programming contest of my life. But I had to complete the contest in 1/3 time as the cyber cafe was about to get closed by 9:00 p.m.(Don't have PC at home, this I am writing from my school lab.).
Made a new codechef account for the same purpose, settled myself on a computer with 20 mins to go for the contest.
The wait ended and and the problems flashed on the screen.
Started the first problem with full excitement. The problem was set by Udit Sanghi, and the problem statement started with something bad about schools(What else did you expected) which on one go I understood it is unsolvable for me, atleast in the given time constraints. Went for the another problem "Ant in a Box", Ahhh this was the problem I came for, but the genius inside me thought that following formulas are same
for the first value of q(1,1) state of the bear at 1,1 changed from 0 to 1, so the new score will be 3(earlier it was 2).Again for the second value of q(1,4) state changed from 0 to 1 so the new score will be 4(just before it was 3).