Note for large dataset : I had a hard time finding how to pass the last test case, logging how far I could get while optimizing my code.
Then I remembered that “not logging anything” was an optimization, and that did the trick.
Nice challenge
1 Like
Truly awesome puzzle! Started with proper java queues - too slow, instead used one circular buffer - faster, but too slow for large data sets, I’ve finally used circular buffer and map for storing profits from every computed load - 100%! :D. Code is ugly as f but finally its fast enough ;). Kudos for puzzle creator!
How did you do it ? Got the exact same problem in C#, and I’m curious I don’t see anybody ask help about it. If I convert it to string it gives me the same wrong answer
Wow, I barely remember, but I mentioned the solution in my edit:
So it was calculating correctly all along, but truncating to a 32-bit int just during printing! I don’t know C# well enough to know if that’s an issue there, but just changing the printf statement fixed it for me.
Je confirme cette remarque.
J’ai fait un algo en Java en utilisant LinkedList, ça n’a pas pas marché pour réduire le temps CPU dû au fait d’ajouter et supprimer des éléments j’ai mis un tableau et j’ai réduit les instructions au minimum en vain (le dernier test n’était pas bon je était à 86%) j’ai repris le même algo en JavaScript sans rien changé à la logique je passe tous les tests et je suis à 100%. Je pense JavaScript à un léger avantage par rapport à Java sur ce puzzle
This puzzle was a good break from other things. This was my first time storing calculations for optimization. To pass the last test with the large data set was hard for me at first. I read the stuff in here and thought I could help out some.
at the beggining of each ride
if(calculated_values[queue_index] not calculated)
do calculations
store them
make note of the next person after this ride
else
recall our stored calculations when at this index in the queue!
add the previously recorded costs for the ride when at this index
set index to where we are after ride by recalling our old data
sounds crazy, but this alone got me to pass
got to think instead of adding each person to the cost per ride one by one, we can do one addition if this ride has already been calculated.
2 Likes
really don’t need a queue. i started off using one, but it’s too slow. an array is fastest, since we are never deleting data or adding data after the init of the puzzle, array is best for speed. simply keep track of your index in the array(instead of popping and pushing) then when at the end reset index to 0, it works like a circular buffer, but less overhead than a real vector/queue/list
Hey my code passes all but the large dataset test (even the very large dataset) once I submit it but passes the large dataset test in the IDE. any clues to why it could be the case ?
The test cases and the hidden validators (which are the actual cases used to assess your code) are different.
Okay but the problem isn’t speed (it is ok for the very large dataset) so its an edge case that isn’t present in the IDE’s tests ?
Does this previous comment help you in some way?
Yup thank you !
In spite of what the puzzle intro says, the only learning opportunity mentioned that is really relevant is simulation. Now the interesting thing about this puzzle is that the only thing you need to get a 100% score at it is an integer and the modulo operator. The modulo is needed only until you detect the start of a cycle. Hint: if you use a std::queue or a std::map or whatever, you are on a bad track from the very begning. It is of importance to notice that for perfect cyclics (a cycle start at 0) of short durations a hash can detect cycles very early but is very unpracticable in regard to all other cases. But in the end, even with a simple <self sensored / giving solutions is forbidden>, I am under 2 ms for extra large data sets. I would recommend to those who seek to get started with this puzzle to get acquainted with ring buffers, not for the ring buffers themselves, but for the management of their sections indices, until the start of a cycle is detected since there is NO DATA MOVED whatsoever in this puzzle. After which another mechanism that I am not at liberty to describe (forbiden) kicks in.
very nice idea… good riddle.
but can you please give the variables speaking names and not just L or C?
2 Likes
I everyone.
I have an solution that is kind of quick (3 ms for 2^32 , 35ms for the large data set).
However, i can passed all the sets, but the last, and i have no clue where i can be wrong (89744892635932 instead of 89744892565569).
Is there somewhere i can put my code to discuss with people, or is there a group on reddit?
I will try differents testcase with fewer data and see if i can reproduice the delta.
Edit :
I’ve tried with random number as n, l and c with my 2 method (naiv (that i knew working well) and [Programmation dynamique]).
Try different test case. My solution was wrong 1 on 4.
This testcase in particular help me :
l=4
c=20
n=5
lQueue = 1,1,1,3,4
Et bien pareil ici, si tu as réussi à trouver, je suis preneur !
There is Discord chat. You can find the link under the COMMUNITY menu.
1 Like
Same thing with java…An easy and very simple solution pass all the tests.
I haven’t notice, thank you !
Using Python3:
Solved test #9 by using dtype=float on my sums. Apparently one of my computed numbers is higher than 2**32. I guess I’m not summing efficiently. So i’m finally at 100% after a few hours of headache.
Also if it’s the only one you’re failing, it’s most likely because of the remaining values that are calculated wrong after you’ve multiplied your cycles. (The wrong formula can work for the other tests even #10)