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 at http://groups.google.com/group/google-code?hl=en.
