I think it will be O(N^2) to check each pair I once used LCS to do this and it worked well
On Wed, May 19, 2010 at 1:43 PM, Monang Setyawan <[email protected]> wrote: > Just curious. > > If we use edit distance to check K submission, what is the complexity? Is it > O(n^K)? > > On Wed, May 19, 2010 at 4:20 AM, Muntasir Azam Khan > <[email protected]> wrote: >> >> >> Actually, last year there were some lists of cheaters put up by users. >> These were generated using something much simpler than the approaches >> suggested here - mostly checked whether two submissions were exact >> matches or had an edit distance less than some small number. You can >> find lists of cheaters from last year in this forum thread at >> TopCoder: >> http://forums.topcoder.com/?module=Thread&threadID=650760&start=0&mc=41. >> The interesting thing is that even such simple checks found a huge >> number of cheaters in the Qual round. >> >> But these were made by contestants, the GCJ admins will likely be >> employing different methods. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "google-codejam" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/google-code?hl=en. >> > > > > -- > "Don't worry about what anybody else is going to do. The best way to predict > the future is to invent it." - Alan Kay > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
