I use Dijkstra too, and it works.
My algo failed when I did not use the right key.
I use Dijkstra too, and it works.
Like explained in posts above, be sure to use radians for your distance computations and not degrees.
to convert use the following formula when fetching latitudes and longitudes
x (radians) = x (degrees) * pi / 180
I had the same problem (all validation samples ok but missing one in the real tests so 84%), and adding the conversion finally got me 100 %
Passed with Dijkstra in C++ using maps, they are logarithmic for searching with the string identifier keys but when I search for the next shortest path at every iteration of dijkstra I have to linearly go through a map. Probably not optimal.
Thanks a lot NewboO !! I had the same problem and it was indeed the conversion of latitude and longitude into radians that I forgot to do. It is really weird that we managed to pass all the IDE tests cases with degrees instead of radians !
Another mistake connected to these unfortunate form of coordinates is order in what you read latitude and longitude, because even if you take them in wrong order you will still pass all tests in IDE and fail only one (Large number of stages) on submit.
I also had problems with “Larger number of stages” during validation. I’ve made a faster short path finder, and solved the problem. But I still don’t know if the problem was the time of execution, because the older program can run 3 times in the IDE test (calling 3 times the short path routine) without problem with time. So, the validation test is much longer or has a case that my old program cannot solve.
I think it would be a good idea, if validation tell us the cause of the problem (time of execution or wrong answer).
Thank you very much! Same thing here. It’s a nasty trap.
Degrees to radians… thanks, you save my time ^^
LOL TY Bro I was using a super fast implementation of Dijkstra with a Min-Heap and still failing the large test case.
after converting it to radians I passed
Same for me! Thanks a lot for this tip! You saved me from madness
In the question it lists the information about each stop, with some items being listed as “not used”. There is one item however (“The type of stop”) which is not explained, and does not appear to be used, but is not labelled as such. Anyone know what it is meant to be for? It doesn’t seem necessary…
Ha la la la la !!! I’m so dumb !!! :))
Every week for several months, i’ve found some time to read my code again and again because of this 83% submission…
Sure my Dijkstra was good ! Sure my degrees to radians conversion was good ! Everything was good in fact but always 100% in IDE and 83% in validation…
And today, i found it. Very funny… I was reading x = latitude and y = longitude… So bad because x is longitude and y is latitude… Reading y before x does the job !!! 100% Yeah ! Too glad…
Hi guys, I’ve read all your posts and taken everything in consideration. I convert latitude and longitude to radians when I fetch them by multiplying by the (pi / 180.0) factor. I use them correctly in the formula and I never use a name as a key for any of my maps. I get 100% on tests and fail on submit… any more ideas ?
Thanks a lot
I finally found my problem…thanks to those who tried to help ! (problem was I was only initializing the distances of the stops which are at the beginning of a route…)
I’m stuck at 83% in validation but my problem is with the 5th validator (5 stops, 2 roads).
I’ve converted my degrees to radians and I’m sure about my lons and lats so I have no idea where my issue could be…
If any of you have a tip or a guess about my problem, please do not hesitate to answer me
you’re the real mvp !
Well that’s funny because when we invert longitude and latitude, we pass all the tests in IDE. (but one failed during the validation)
Please, make an IDE test for that or something
Same problem here.
I use Dijkstra (A* with 0 heuristic) implemented in C++ and it passes all the tests in IDE and fails the “Large number of stages” in the verification phase. I have no idea why it does and can’t fix it for days
I also tried using float and double as well for distnance calculation.
So if you succeeded to solve the problem please let me know.
Solved: Convert degrees to radians
suddenly, i decided to solve this in pure C, just to see other people’s solutions if there is something funny
i had this solved in pascal so i was pretty confident that i’ll do it in no time
debug was terrifying, took me three days
and what i see as a result? only one participant except me also solved this in C