Roller Coaster puzzle discussion

Puzzles
#42

The constraints are confusing in the French version for the larger dataset :smile:

Is it actually 10 to the ninth power ?

“Contraintes
Pi ≀ L
1 ≀ L ≀ 109
1 ≀ C ≀ 108
1 ≀ N ≀ 10000
1 ≀ Pi ≀ 107”

6 Likes
#43

Same on English version:
1 ≀ L ≀ 109
1 ≀ C ≀ 108

1 Like
#44

Incorrect game conditions, because:
Constraints
Pi ≀ L
1 ≀ L ≀ 109
1 ≀ C ≀ 108
1 ≀ N ≀ 10000
1 ≀ Pi ≀ 107

If so, you can not pass a some of tests.
But it is necessary to forget about the boundary conditions, and immediately passes all the tests, except for the last.
It’s bug?

1 Like
#45

[English]
Hello, I just perform this puzzle with clojure, but I previously didn’t know this language. Because I am a beginner is this language, I am not proud of my code and I think that I didn’t used the potential of Clojure. Could you give me some advices?
For example, how did you store input datas? I have used:
(def groups [])
(loop[i N]


(def groups (conj groups Pi)) ; add “Pi” to vector “groups”


I imagine that there is a better way to create it (recursively?), but I have not been able to do it


[French]
Bonjour, je viens de terminer ce puzzle en Clojure, mais c’est un langage que je ne connaissais pas auparavant. Parce que je suis dĂ©butant dans ce langage, je ne suis pas fier de mon code et je pense que je n’ai pas utilisĂ© le potentiel de Clojure. Est-ce qu’il serait possible d’avoir quelques conseils ?
Par exemple, comment stocker proprement les donnĂ©es initiales? J’ai fait ainsi :
(def groups [])
(loop[i N]


(def groups (conj groups Pi)) ; add “Pi” to vector “groups”
J’imagine qu’il y a un meilleur moyen pour crĂ©er le vector “groups” (recursivement ?) mais je n’ai pas trouvĂ© comment faire
 Un conseil ?

#46

Thank you very much.

#47

Salut alberola,

DĂ©solĂ© de t’ennuyer mais si je me baladais sur le forum car quelque chose d’étrange (ou en tout cas qui me semblait Ă©trange) se passait avec mon code et je suis tombĂ© sur ton post. Je crois que toi appliquons plus ou moins la mĂȘme idĂ©e. Je passe les tests jusqu’au dernier oĂč j’ai une valeur fausse d’environ 15%. Je trouve cela vraiment Ă©tonnant car je n’ai pas le sentiment que le dernier test rajoute quoi que ce soit au niveau de la logique du problĂšme, c’est juste une instance beaucoup plus grosse. Sais-tu ce qu’il se passe ? Merci

Jo-Yun

#48

This find-the-loop trick actually brings the running time down to O(N).
Used this technique to solve in Python and Closure.
The Closure code is rather long (compared to 20 lines) and ugly, though.

#49

Delete the debug messages - great advice :slight_smile:
I couldn’t pass the large dataset test with my prinErr code in JavaScript.

#50

Hi,
I have not seen any message about Javascript, so here it is.
First I did like everyone with an array and add/substract functions in array, but it did not pass the last test because time execution. So I changed the algorithm by removing all push/splice/slice functions. Instead of removing the beginning of the queue, pushing it at the end of array, and calculating for next round, and I do not manipulate the array and let an index reading the array and going back to the beginning until I reach C rounds. It passes 100% with this approach.

#51

I can olny complete the very large set but not the large set. My IDE has the correct solutions for all test cases. :confused:
Help?

#52

Forget it. Already saw the error. Hmm, 180 lines of code is alot. :smile: I saw other player’s solutions and I think i complicate it too much
 Oh well


#53

En deux mots : dynamic programming.

#55

Thanks for the hint !
My first solution was a naive FIFO queue, i then changed it to a simple array with start/end pointers, and i still couldn’t get the last test in time.
Memoization for the win \o/

#56

Well, I solved it in C#, and I can’t really say that’s a Hard puzzle, you just need some caching and that’s all.

But the thing is I saw many published solutions without the memorization/cache, and my question is:
How did they pass the tests?!?!?!?!?!?!?!

I even copy/pasted some of these solutions and in my IDE all and every one of them without the caching fails at the last test (I must say I didn’t try to submit it, just testing in IDE).
So, how did these solutions pass the validators?

#57

This was a good one! My first attempt was a simple brute force solution, no dice obviously. :smiley: Then I memoized it. Still not quite fast enough. Then I noticed that “dynamic programming” was mentioned in the briefing, so I studied a little and discovered a smart way of solving this. In the end I was able to solve test case 6 under 0.02 seconds and got 100% (python 3).

Very useful exercise, thank you!

2 Likes
#59

Personnellement, j’ai rĂ©solu ce challenge grĂące Ă  cet algorithme:

Je peux ainsi résoudre le dernier test unitaire en à peine 6ms.
Bonne chance!

2 Likes
#60

I Agree with the analysis. And then there are the half-way caching solutions that are passing the tests. I tested in CG IDE one highly-voted 30-line C-language solution that looped C times, and it found the answer to the large dataset in 50000 clock ticks. My solution detects the loop and then calculates the costs for the pre-loop, the loops and the post-loop. This is about 100 lines of code. It does the large dataset in 35 clock ticks, yelding to 1400-fold difference. Maybe the provided solution testing times are bit too lax or the datasets are too small


#61

Il suffit de le coder naivement en javascript :confused:

Je suis trĂšs intriguĂ© par la mĂ©thode d’évaluation des algo, je m’explique :

  • javscript implĂ©mentation naive (boucle for, somme+test) => 100%
  • python implĂ©mentation naive => fail sur large dataset
  • clojure implĂ©mentation naive => fail sur large dataset
  • python optimisation (cache [index, money], permet de sauter des itĂ©rations) => fail sur large dataset
  • clojure optimisation => fail sur large dataset

Bref, je pense qu’il faut utiliser la mĂ©thode de la tortue et du liĂšvre pour le faire “correctement” en python ou clojure mais en javascript c’est cadeaux et de niveau “facile”

#62

What is the challenge at the Validator 9: “Works with a large dataset”?

My code runs in 2ms for all the test cases. (Obs.: 40ms to read data, and 2ms to solve).

I passed at the Validator 10: “Works with a very large dataset”, that is more complex, but didn’t pass at 9. Anyone has any clue?

I already change everything to long, so, it is not overflow.
I’m coding in Java.

#63

Maybe you are overflowing round repetition? Honestly I don’t think it is possible. But it’s the only thing that came to my mind