Roller Coaster puzzle discussion

Puzzles
#106

Hey peeps ! Trying to implement Tortoise and Hare Algorithm but get incorrect result for large datasets. Here’s my code:

[Mod edit: Please avoid posting codes on the forum.]

I did test it with all kinds of input data and it works but does one tests huge datasets anyways…

#108

Not all kinds of input data apparently. Please read the previous discussion, and you’ll find these cases for checking the correctness of your code.

Also, please try to describe what your code does instead of posting codes on the forum in the future.

#109

Thanks for the link @5DN1L. I have however did all kinds of testing with normal data and it works, as I have indicated in my previous post. Only when it starts to get to 10^9 problems arise.
I wanted to show my code in order for someone who has already solved the puzzle perhaps quickly pinpoint the problem. TBH I find it extremely inappropriate to not be able to post code at the coding forum. But it’s ok, I’ll post it on stackoverflow.

#110

Your code doen’t always give the correct answers for the cases with small values in the link. You should try debugging from there.

#111

@5DN1L, yes you were right I did have some errors with these specific tests. However after fixing them I still have wrong answer for the big data cases.

#112

If you want, you may send me your code in private message and I’ll take a look.

#113

This custom case may prove useful for debugging if you fail the last visible test (i.e. Test 6 “Works with a large dataset”) and the reason isn’t a timeout:

Input:

100 9 10
3
8
2
19
33
29
22
19
2
15

The output should be 724.

#114

My code works. I have even tested the “large dataset” locally. It takes between 3 to 4 sec… how fast it is supposed to be ? I read about memoization, but I’m seriously unable to get where I can apply in my code.

#115

In my first version I used shift and push with the arrays.
I already changed that and now a have a circular for.

#116

in Codingame, for a little bit more than 7000000 rides it takes more than 5s…

#117

Search memoization in this topic, and you’ll see what other players have talked about it.

#118

I did twice.

In fact. I just realized that my new code pass the large dataset of the validator but not yet the very large dataset.

And it doesn’t pass the large dataset test case

#119

So, have you done any memoization in your code?

If you do, there’s also a possibility that your calculation based on the memoization is wrong, instead of a timeout.

Try this case if you have not: https://forum.codingame.com/t/roller-coaster-puzzle-discussion/21/113

#120

apparently I don’t know how to do efficient memoization… it goes from 3s to 450s :sweat_smile:

#121

Maybe you use a human brain?

#122

:joy: I finally got it. Memoization, yes, but good method decomposing first.

#123

Juste merci !
je devenais fou :slight_smile: