https://www.codingame.com/training/easy/van-ecks-sequence
Send your feedback or ask for help here!
Created by @Crypticsy,validated by @TBali,@ItsAFeature and @Andeagi.
If you have any issues, feel free to ping them.
Hi all !
Iāve tried to pass the tests 5 and 6 that respectively compute the 56804th and 1000000th value of Van Eckās sequence. My code is working but on CodinGameās IDE, the compute time is too long (around 7 seconds on my machine for the test 5 and way way way more for test 6).
My first idea was to create a dictionary that holds each number as a key, and itās latest occurence as the keyās value. I append to my sequence the value that corresponds to the sequenceās latest value. Then, I had to increment each value at each loop. This took something like 65 seconds for test 5, and I have not tried test 6.
My second (and way faster) idea was to browse the reverse sequence and append the reversed index when the latest occurence is found :
latestvalue = l[len(sequence)-2::-1].index(sequence[-1])+1
sequence.append(latestvalue)
(latestvalue is the value to check for latest occurence, sequence is Van Eckās sequence)
Then, do you see any way to improve the compute time of the sequence ? Iāve seen people already solved this puzzle using Python, so it should be feasible.
Thanks for reading and for your help 
Hey,
your 1st idea was good.
Just think about this : do you REALLY need to save ALL the sequence to solve the problem ? 
Maintenance of large objects takes time.
5 Likes
Hello. Your first idea (using dictionary) is the right way to solve this problem.
But you should not increment each value at each loop because it will take so long for big inputs.
Instead, when you get some number, you should subtract from current index (length of sequence so far) the index of this number that is in dictionary, so you get number of steps back to last occurrence of this number, and in fact this method is very fast.
5 Likes
Hi @Liam @Deltaspace,
Thanks for your fast answers! Indeed it was not necessary to work with the list containing the full sequence, I kept only the two latest elements of the sequence at each loop according to your advice Liam, and using the value of the round as a value for each key (each number in the sequence) in the dictionary according to your advice Deltaspace and it work perfectly 
Now, my program computes the 56804th element of the sequence in 0.03515s and the 1000000th element in 0.63306s.
Thanks again !
2 Likes
The first 2 test cases are really handy to test the basis. However, they both start with A1 at 0. Maybe adding an extra simple test case with A1 != 0 would be really handy.
3 Likes
I agree. I pass the first two cases, but my algorithm may be flawed, b/c I get 15 for the next one instead of 11, and the 1 instead of 7.
Should the āA Little Longerā sequence start off looking something like this?:
1, 0, 0, 1, 1, 2, 0, 2, 1, 3, 0, 3, 1, 4,ā¦
Or am I doing something wrong?
The sequence starts like this : 1, 0, 0, 1, 3, 0, 3, 2, 0, 3, 3, 1, 8, 0, 5, 0, 2, 9ā¦
You are supposed to append the offset with the latest occurence of the number, not the amount of times the number as appeared so far
4 Likes
Cool. Thanks and my bad. I guess I just didnāt understand the instructions at first, but now I have it fixed.
Hi everyone!
Iām really at a loss here. Iām doing this in C++ and that last test doesnāt want to pass.
I have only one loop, in which I check in a map if An has been seen before. This is my only container since I only use the last value of the sequence. I also use a specific variable for the 0, since it comes up so often, so that I donāt have to access my map as often. What am I missing to make it faster ?
Edit : my first test runs at 0.06 ms, A little stress at 24.2 ms, and a custom example of 650000 calculation runs at roughly 300 ms.
Iāve just tried this and the combination of map nearly always being the wrong choice in c++ and no optimisations makes this slightly harder. You could try using unordered_map or putting optimisation pragmas at the top (before includes):
#pragma GCC optimize("-O3")
Either of these options let my code pass whereas the version using map with no optimisations will fail the last test.
4 Likes
Thanks, just the #pragma command managed to do it for me.
100% in Java by using HashMap. No optimisations
The blazingly fast PHP++ also solved it with very simple code. Time complexity O(n), space complexity also O(n). Last ide test takes around 0.1 sec.
1 Like
I had a hard time passing the last stress test on this. I used an unordered_map and tried RoboStacās optimization pragma (thanks RoboStac). Still didnāt pass. I was pretty sure I only kept track of the minimum data required - I think you have to keep track of all the numbers youāve seen, because you donāt know which numbers you will see further in the sequence. I ended up just using a simple array to store the last indices of the numbers seen, and that made it pass. But then I was not using any hash maps at all in the final solution.
Iām having a really hard time passing the final test. Iāve tried rewriting it with only storing the last time each number is seen. I rewrote it in 3 different languages now.
Stuck at 83% banging my head against the wall.
My algo is using a simple āforā cycle N times. In it there is just a simple if-else and a few variable assignments. This takes ~0.1sec for N=1M in an interpreted language. Maybe your algo runs more than N times, or doing something unnecessary complex in it?
I rewrote it using Map in Javascript instead of an array and that was even slower.
Then I went back to using an array to store the current position of each number and it magically started working, though itās the same as before. ĀÆ_(ć)_/ĀÆ
/ragequit