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: <CALW8-7KY3qu=goG5GBbe48Mvhp50_iBONJt972VJwNeC3P2aQQ@mail.gmail.com>
Date: Mon, 19 May 2014 12:10:27 +0200
From: Dmitry Khovratovich <khovratovich@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] OT: Pw0nd the tech riddle

Unless I am mistaken, it can be done in 2log N. You first look at the first
row with the binary search, find maximal X' <= X, and then do the same for
the column where X' is.


On Mon, May 19, 2014 at 10:33 AM, Christian Forler <
christian.forler@...-weimar.de> wrote:

> 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
>
>
>
>
>


-- 
Best regards,
Dmitry Khovratovich

Content of type "text/html" skipped