[Community Puzzle] Van Eck's sequence

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.

3 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

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

For everyone who has faced troubles passing the final testcase. Note that printing to console is pretty heavy operation (this includes debug console messages).

1 Like

Exactly, I didn’t pass the last with console.error but without that it passed almost instantly. I used javascript map btw.

I think this can be a very good exercices to practice in C.