[Community Puzzle] Van Eck's sequence

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 :slight_smile:

Hey,

your 1st idea was good.
Just think about this : do you REALLY need to save ALL the sequence to solve the problem ? :wink:
Maintenance of large objects takes time.

3 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.

2 Likes

Hi @Liam5 @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 :grinning:

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.

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

2 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.

2 Likes

Thanks, just the #pragma command managed to do it for me.

FWIW, I used a <map> and no optimization and it went just fine.

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