phc-discussions - Re: [PHC] OT: Pw0nd the tech riddle

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 linux-cve-announce 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]

Message-ID: <5379C1CA.7060204@uni-weimar.de>
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)