lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  PHC 
Open Source and information security mailing list archives
 
Hash Suite for Android: free password hash cracker in your pocket
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Mon, 19 May 2014 10:33:14 +0200
From: Christian Forler <christian.forler@...-weimar.de>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] OT: Pw0nd the tech riddle

On 18.05.2014 03:53, Bill Cox wrote:
> You guys are the biggest online geeks I've run across, on average, so
> if you enjoy dumb tech riddles (which I suspect many of you do), read
> on, but it's way off topic.
> 
> I was challenged with a puzzle yesterday, but I don't believe the
> guy offering the puzzle understands the solution very well.  Once I 
> understood his puzzle (which took me a while - I can be slow), I
> gave him the optimal solution, running in O(N), in about 10 seconds.


A optimal runtime of O(N) for a NxN matrix sounds legit. :-)

Good work! :)

> He didn't seem to like it, so we moved into highly unoptimal
> territory, and before giving up on the discussion, he pressed me on
> how long I though his preferred solution would take, "in my gut".  I
> stuck to O(N*log2(N)). 

Yep. The algorithm proposed by devendraiiit  runs in O(N * log(N)).


> He was clearly unimpressed.  I'm giving myself kudos for sticking
> with my gut, which turned out to be exactly right, but only if I give
> the guy the benefit of the doubt and improve his algorithm slightly -
> doing a binary search on the diagonal, rather than picking the middle
> element.  I simply couldn't accept that he was advocating picking the
> middle element and then recursing on 3 N/2xN/2 sub-matricies...
> that's just nuts.  Here's a link to an online discussion of the
> puzzle I found today:

Starting from the element A[N/2][N(2] looks like a good idea since you
only need about O(N) steps to find any element, i.e, the distance from
A[N/2][N(2] to the target Value is at most N/2.

BTW. The idea of using binsearch on the diagonal is pretty cool. :-)


I soon as I read the problem description I also came up with a recursive
Algorithm. It looks very natural for this kind of problem. :-)


Lets try the O( N + log(N)) algorithm where you start at A[1][1].
Lets assume that we are looking for an element X which is not on the
diagonal. Then we run down the diagonal until A[i][i] >  X.
then we know X must be i the left bottom or the right top corner.

Then we take a close look at the NxN matries with the diagonal
(A[1][i-1],...A[i-1][N]) and (A[i+1][1],...A[N][i+1]).

And so on and so forth, until we got the element.


Best regards,
Christian





Download attachment "signature.asc" of type "application/pgp-signature" (535 bytes)

Powered by blists - more mailing lists