Feel free to send your feedback or ask for some help here!
1 Like
Bonsoir
J’arrive pas à obtenir un algorithme suffisamment performant pour réaliser le “large data” test. J’ai pu d’idée d’optimisation. (je suppose que le problème viens du temps d’exécution)
Sachant que je code en java et que j’ai utilisé un linkedList pour simuler la queue.
Est-ce que une List Ă la place du linkedList serait une solution plus efficase?
Si vous avez des suggestions je suis preneur.
cordialement. vincent
De manière générale, et en particulier avec les algos à mettre en oeuvre sur CodinGame, soit tu sacrifies de la mémoire pour améliorer le temps d’exécution, soit tu sacrifies du temps d’exécution pour diminuer l’utilisation mémoire. Ici, avec l’algo le plus simple, tu as beaucoup de mémoire qui reste inutilisée et donc disponible pour optimiser le temps d’exécution.
Autre chose, comme tu parles des LinkedList de Java, un autre bon conseil est d’éviter au maximum les insertions/suppressions. Même si le coût d’une opération n’est pas très élevé, les répéter des milliards de fois le devient, surtout lorsque des solutions moins coûteuses existent. Sur ce point, tu peux regader du côté des Circular LinkedList ou te contenter d’un simple tableau.
Bonsoir,
J’ai optimisé en utilisant le moins de if possible.
Après j’ai essayé avec un tableau qui a pris trop de temps.
Je me suis donc retourné sur une Circular LinkedList et même résultat .
Je vois pas vers quoi me tourner maintenant.
Si vous avez d’autres suggestions, je suis preneur.
Cordialement.
J’ai envoyer mon code à tout hasard, et il a passé tout les tests alors qu’il ne passais pas le test sur la large data.
coup chance ou autres je ne sais pas.
Ah ah, j’adore celui-la, en le lisant je me disais (“mais qu’est-ce que ça fout en difficile ?”) puis j’ai vu que mon code naïf avait environ le 50 ème des performances nécessaires au dernier test…
I was able to achieve a score of 100% in less than 20 lines of Clojure. The trick for the last test (large dataset) is to use memoization. Even though the group count is 1000, the actual group indices needed in the earnings calculations are only 173. Also, 126 of these indices appear more than 70000 times each! Imagine how much work you save by simply caching the first calculation and then just looking up the result every time you need it again…
6 Likes
Thanks, I go to try this in JavaScript.
This one is perfect!
I was using .NET queue first, solved all but last. Than my problems just began…
I even fired Performance Wizard (for the first time in my life) to check what’s the problem, fixed few LINQ stuff, but still got horrible performance.
Taking a pen gave results very quickly - if you start with some particular group, you will ALWAYS end up at fixed next group, and earn fixed amount of money.
Key is to store two maps / arrays (one of earns per group and one for index of group which goes next) and then just jump here and there and compute total.
Thank you for a puzzle!
It’s outstanding!
7 Likes
Bonsoir je ne comprend pas mon code fonctionne sur tous les tests proposés dans l’ide (sauf le dernier) en revanche des lors que j’envoi mon code il me valide seulement 10% (–")
De plus je ne comprend pas comment est t-il possible de réduire le temps d’execution pour le dernier test.
Ce que je réalise ces que j’ai un pointeur de début de liste et un pointeur de fin de liste (je n’utilise donc pas les fonctions d’insertion et de suppression qui peuvent ralentir un programme).
Cordialement,
Sanpas.
Personnellement je suis venu à bout du dernier test en remarquant que si le nombre de tour de manège est très grand par rapport au nombre de groupe (c’est le cas ici, 9 millions par rapport à 1000 groupes), on retombe forcément à un moment ou un autre sur la même configuration.
Exemple (les valeurs sont totalement prises au hasard) : si en 10 tours de manège j’ai gagné 100 000 dirhams et que le prochain groupe à passer est le groupe X puis que 30 tours suivant c’est à nouveau le groupe X et que j’ai cette fois-ci 500 000 dirhams en poche alors je sais que que tous les 30 tours je gagne 400 000 dirhams.
Je sais également que cette période peut se répéter (9 000 000 - 10) / 30 fois. Il reste à calculer le gain pour le nombre de tour restant.
Ceci fonctionne chez moi mais quand j’envoie mon code je ne valide pas le dernier test ><
4 Likes
Rewriting Roller Coaster puzzle solution in Clojure ?
Challenge accepted.
Achievement unlocked.
5 Likes
Hi,
I’m working on the Roller Coaster puzzle in C++ and I cannot pass the 4th test. The input data are:
10000 10 5
100
200
300
400
500
Which means that there are going to be 10 rides and each of them will be worth approximately 10000.
I get 97800 as a result. However, the expected answer is 15000 (which is clearly wrong). I cannot pass the corresponding test in the validation set either.
Any ideas?
Cheers,
Egbert
1 Like
A group cannot be twice in the same ride (thus the expected answer is actually the right one) 
6 Likes
I feel so stupid now:) Thanks
1 Like
I passed this puzzle with 100% in C++ (using the memorization trick).
I used the exact same algorithm in Clojure and I can’t pass the last test, I’m stuck at 85%.
I used arrays (instead of vectors) and type hints to make the code faster, it’s better but it still doesn’t work…
Any ideas ?
I passed all of the tests for the practice, but when I submit I get the one for the large dataset wrong. I am not sure what is wrong with it since it doesn’t show what I am getting vs what I am supposed to get. Has this happened to anyone else? I am using Java for it.
Is it possible to score 100% in this puzzle using Python?
Yes, I did it and I think that I’m not alone.
3 Likes
As I solved this problem using Python 2 some months ago, I can confirm that yes, it is possible! 
Actually, I just completed it once again.
I used the same method to optimize than you, and that was enough to get 100%.
However, I remember the first time I tried (a few months ago as I said), it was not efficient enough for some reason.
So I had to find another complementary trick, less obvious, to improve my score. And it worked!
I just made a few test.
With this second improvement, it takes me less than 0.2 seconds to solve the large dataset problem, but it takes me almost 5 seconds otherwise!
So it’s up to you, you can find another trick, or optimize the current structure of your code to make it more efficient. 
1 Like