Roller Coaster puzzle discussion

Thank you for your feedback, Nicolas and Delgan. I can think about 2 more optimizations I could do in my code. Currently, it takes incredible 47 seconds to run the last test lol… reading that it can be done in 0.2 seconds using Python motivated me a lot :smile:

Edit: 100% now using Python, thanks again for the feedback!

1 Like

i have a bug with validation here too, same as in Doctor Who - The Gift
from ide window i can not pass large dataset test, but on submit this test is ok

There is some French text left in and I think the P in limitation “1 ≤ P ≤ 107” should be Pi.

Fixed, thanks

I used the memorization trick, just as you did, but my algorithm in Clojure still takes around 5 seconds to execute the last test (not enough), while my java file takes less than 700 ms.

I am using java.util.HashMap in Clojure to store the group earning and next position (faster than hash-map from Clojure), also type hints. I am new at Clojure, maybe I am missing some optimization or just using the language the wrong way. Any ideas?

Hi, notice that there are only 5 groups, you can’t seat more than 100 + 200 + 300 + 400 + 500 = 1500 in one train. Just because you don’t have other people.

4 Likes

Thanks for the puzzle. Did it in Java. Used just 3 plain int arrays. For the last “large dataset” don’t forget to comment out/delete all unnecessary code, including debug outputs System.err.printlns. Good luck!

Hey I tried this. i used a hashmap

map<int,pair<int,int>> mhash;

The pair holds the next group index and the earnings of the current group. I still get a time out in C++
What am I doing wrong ?

if (mhash.count(front) > 0){
    paisa += mhash[front].second;  // Paisa stores the total earnings.
    front = mhash[front].first;    // Front is the index of the next group;
}

I get the correct answer of 89744892565569 when I run it in Visual Studios but it takes 15-20 seconds

##UPDATE : Solved it by removing map.

Apparently the logarithmic access time of a map was too solw so I used arrays which game me a constant access time.

Hi, I had exactly the same behaviour by using a map<size_t, pair<size_t, __int64>>…about 20 to 25 seconds in debug mode under Visual Studio (168 ms in release mode)  for the large data test set.
I replaced the map by a vector and obtained 208 ms in debug mode and 33 ms in release mode.

1 Like

Avoid using erasure in whatever data structure you’re using. A solution among many, in C++, would be to use an iterator that goes back to the beginning of your vector once it reaches the end.

Hello everybody,
I tried to achieve a 100% score in bash, but did not managed yet.
I don’t want any hint/clue yet. Just want to know if somebody managed the 100% score in bash ?

Nobody did :blush:

I finally did it.

My short code with 1 array and no memorisation doesn’t pass the last test in the IDE but it passes validation. Dodgy.

1 Like

Another trick using memoization: when find the loop index, add all remaining loops at once, it doesn’t need to continue looping.

2 Likes

Hello everyone,
I manage to code a solution in C++. I get all test cases green(execution in less than 1ms on the large dataset).
However when I submit my code I reach 86% as the last test fails.

As I don’t know why my code fails, is it possible to get a small feedback from those cases?
Regards

is the last test named “Works with large dataset”?
this test means that your alorithm complexity is too high

I just passed the last test in Clojure with a java.util.HashMap.
I had to remove all debug outputs, it seems they are really slow in Clojure.

My Java program passes all the tests with 100%, but when I submit, it fails the last test (large dataset). I’m pretty sure it’s not because of speed issues. I profiled the last tests case, and the entire application runs in 30ms, of which 28ms are just reading the input. Is there are way to debug the validation test cases used after submit?

Just did it in clojure. No special hashmaps needed. Just go with simple vector and terminal recursive loop, all will roll fine :wink: