hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Deja Vu impossible?

 
Reply to topic    hacker.org Forum Index » Challenges View previous topic
View next topic
Deja Vu impossible?
Author Message
konsi



Joined: 19 Nov 2008
Posts: 3

Post Deja Vu impossible? Reply with quote
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' Smile ...

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?
Thu Dec 18, 2008 3:13 am View user's profile Send private message
tails



Joined: 10 Jun 2008
Posts: 191
Location: Tokyo

Post Reply with quote
It is solvable. Good luck!
Thu Dec 18, 2008 4:15 am View user's profile Send private message
adum



Joined: 19 Apr 2007
Posts: 390

Post Reply with quote
Very Happy
Thu Dec 18, 2008 5:22 am View user's profile Send private message Visit poster's website
konsi



Joined: 19 Nov 2008
Posts: 3

Post Reply with quote
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....
Thu Dec 18, 2008 12:49 pm View user's profile Send private message
efe



Joined: 26 Oct 2008
Posts: 45
Location: germany

Post Reply with quote
I solved it. Very Happy
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.
Thu Dec 18, 2008 3:46 pm View user's profile Send private message
snibril



Joined: 26 Oct 2008
Posts: 31

Post Reply with quote
Your calculation is wrong. There are 128 numbers given, so you have 10000/128 (~78 ) cycles per number. Thats pretty much.
Fri Dec 19, 2008 6:51 am View user's profile Send private message
Karian



Joined: 09 Jan 2008
Posts: 75

Post Reply with quote
snibril wrote:
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.
Fri Dec 19, 2008 12:08 pm View user's profile Send private message
snibril



Joined: 26 Oct 2008
Posts: 31

Post Reply with quote
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.
Fri Dec 19, 2008 5:27 pm View user's profile Send private message
MerickOWA



Joined: 07 Apr 2008
Posts: 182
Location: HkRkoz al KuwaiT 2019 HaCkEr 101

Post Reply with quote
Given only 10000 cycles, you must be efficient at detecting duplicates. This is all about finding the best algorithm. ... think Big O Wink
Fri Dec 19, 2008 9:46 pm View user's profile Send private message
Karian



Joined: 09 Jan 2008
Posts: 75

Post Reply with quote
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.
Fri Dec 19, 2008 11:55 pm View user's profile Send private message
m!nus



Joined: 28 Jul 2007
Posts: 202
Location: Germany

Post Reply with quote
It definetly is solvable although it can take some time (about 4 hours for me)
I learned a lot Smile
Sun Dec 21, 2008 2:59 am View user's profile Send private message
sila



Joined: 16 Oct 2010
Posts: 4

Post Reply with quote
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???
Mon Jun 06, 2011 5:49 pm View user's profile Send private message
sila



Joined: 16 Oct 2010
Posts: 4

Post Reply with quote
... or is there any work around for the HVM???
Mon Jun 06, 2011 6:21 pm View user's profile Send private message
uws8505



Joined: 23 Jan 2011
Posts: 32

Post Reply with quote
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.
Mon Jun 06, 2011 7:28 pm View user's profile Send private message
yes-man



Joined: 30 Jan 2009
Posts: 22

Post Reply with quote
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
Thu Nov 14, 2019 4:21 pm View user's profile Send private message Send e-mail
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Challenges All times are GMT
Page 1 of 1

 
Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.