I honestly think it doesn’t need to be in hard. More like medium.
really powerful idea!
As detailled by some other, I don’t know how are configured the timeout limits from one language to another, but it seems javascript has a huge advantage here.
I couldn’t get 100% and had a timeout even when caching intermediate results, both in Python and in C. Finally tried in Javascript, and got 100% with the most “naive” (I would even say “dumbest”) algorithm possible and no cache/optimisation at all…
bottom line: If you can’t get 100% , try in Javascript!
Any advice or hints how to find patterns for memorization?
I would appreciate a link to basics or to something I should start with looking for memorization’s solution.
…and after thinking “heavily”…
I could calculate range of groups for each starting index (from 0 to N groups), that way that the range is <= places limit. Then each time the ride starts it would be possible to use that range.
That’s seems a lot of calculations at the start and probably it’ll generate more ranges then needed. Thus “in time” creation should be better.
I ponder if that’s memoization/memorization.
Edit: it worked 
Thank you for your help 
First hard problem, I didn’t have too much trouble (in Python). I handcrafted a test case that should take care of everything and is easy to check by hand :
3 n 5
1
2
2
1
1
and the answer is given by
n : 0 1 2 3 4 5 6 7 8 9 10…
answer : 0 3 6 8 10 13 15 17 20 22 24…
TIP: if you write the queue at each step by hand, a repetting pattern should appear and with some arithmetics you can exploit that to quickly find the answer, though it takes a some more lines of code. I don’t know if it is required but is O(min(C, N)) instead of O© wich is significantly faster if you have a few groups (5) and a huge number of ride (10**7): in this case it runs instantly
The same thing happened to me. But to me it stated something along the lines of “timed out”. So you need to optimize your solution.
EDIT:
My problem was C printf formatting. I love uint64_t, but it has a special form:
printf("%" PRIu64 “\n”, C);
I was unwittingly printing it as a regular int. I suppose this truncates, because it was printing everything correctly but C>1^32.
I’m doing this in C.
I am memoizing: if the starting index has been encountered before, it just reads the number of people and the next index.
It works smoothly and fast on all but the last TWO tests.
It does NOT run out of time; it completes on both of them, but prints the wrong number. I changed most of my ints to u_int64_t, doesn’t help. The penultimate test says you need 2^32, well u_int64_t should be fine with that. I also changed all the other ints to unsigned int just in case.
Still, on test 5: 705007704 instead of 4999975000
test 6: 1550915649 instead of 89744892565569
That last solution is under 2^47, but it’s calculating wrong.
Any ideas?
Thank you.
1 Like
Thanks, Ferrus. Alas, my solution calculates that one correctly, but gets the last two wrong.
Hello
Has anyone done it in Javascript?
There’s a “solution” tab where you can select JS and see that 100 users shared their solution in JS.
So, answer is yes, at least 100 users.
(The solutions for a language are visible only if you already solved it in the same language.)
1 Like
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.