Deja Vu impossible?

[konsi]

Hi,

i found that new challenge 'Remeber me?' pretty solvable. But this one keeps bugging me like:
HVM run ERROR: too many cycles: 10002 (PC=42, STACK_SIZE=4)
HVM run ERROR: too many cycles: 10002 (PC=42, STACK_SIZE=4)
HVM run ERROR: too many cycles: 10002 (PC=42, STACK_SIZE=4)

10002 cycles?? if you calcualte the worst case, then you have to check 128!/(2!*126!) = 64*127 = 8128 tuples, which leaves only a sparse 10002/8128 =~ 1.230.... operations (!) per commparsion, which is somehow impossible to archieve.

also submitting the program '1<p!' gives me the feeling that this schallenge is not meant to be 'fuzzed' ...

Cheating, like only returning a single element out of the first N memcells seems also impossible, as even my second program cannot compare more than 50 or so of the 128 memcells, and the dups never seem to be all in the beginning by chance...

Is there more to it or is this just a bug?

[tails]

It is solvable. Good luck!

[adum]

[konsi]

hm, solvable it seems, but not by a program which does really check all the elements.
Maybe I'ts somehow related to the one minute man, as I thought before....

[efe]

I solved it.
You need a complete different method here.
My program really checks every number (in the worst case) and still takes less than 10000 cycles.
Actually, there are some inputs where my program does not work properly, but the probability for this is very low.
With further improvements I think it is feasible to print out the duplicate number for ALL valid input arrays. That would mean a 100 percent probability of success.

[snibril]

Your calculation is wrong. There are 128 numbers given, so you have 10000/128 (~78 ) cycles per number. Thats pretty much.

[Karian]

Your calculation is wrong.

The calculation is correct. Mathematically, nothing is wrong with what he is saying. That doesn't mean the approach is correct ot solve the challenge in the given cycle limit.

[snibril]

If you want to calculate time or space that a program needs you look at the input and that are 128 elements, and not 8128 tupels. Cycles in HVM are the same as time.

[MerickOWA]

Given only 10000 cycles, you must be efficient at detecting duplicates. This is all about finding the best algorithm. ... think Big O

[Karian]

although indeed, this challenge lets us look at the input of 128 elements, I'm pretty sure that 99% of people who have solved the smaller version have been solving it with looking at the 66 tupels, and not the 12 elements. So the reasoning is pretty logical.

I'm not saying that your way of looking at it is wrong, but it is a logical step you have to take in finding the solution. And maybe in a way, with discussing this, we are giving a big spoiler for finding the correct solution.

[m!nus]

It definetly is solvable although it can take some time (about 4 hours for me)
I learned a lot

[sila]

I got the solution and it works fine, with no errors and with the right answer on the http://www.hacker.org/hvm/ but on the challenge side of “Deja Vu” I get the error messages “HVM run ERROR: memory read access violation @1490893 (PC=88, STACK_SIZE=1)” and so on. I can’t see why this occurs because my code, in the worst case, takes only 128 loops and that shouldn’t be too much and the error messages than again don’t speak about the loops. I simply can’t imagine what it means … do I really have to start with python???

[sila]

... or is there any work around for the HVM???

[uws8505]

As you see in the HVM description, the memory is limited to 16384 cells(if I'm remembering it correct). So the attempt to access memory cell 1490893 fails and spits an error. Maybe you only tested your code with too small values.

[yes-man]

I'm currently working on this challenge and without spoiling too much, I've got to say that the test sets used to validate the code are very specific if not mean :D