I heard that Google uses Levenshtein_distance<http://en.wikipedia.org/ wiki/Levenshtein_distance> algorithm to find cheaters.
On May 19, 12:41 pm, Monang Setyawan <[email protected]> wrote: > I mean, for checking K submissions together. I'm thinking of more than two > dimensional edit distance. Or you can compare this to computing LCS of > multiple strings. > > > > On Wed, May 19, 2010 at 2:36 PM, Liu Cheng <[email protected]> wrote: > > 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]<google-code%[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]<google-code%[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]<google-code%[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 > athttp://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.
