JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Round Tables External Competitions ACM ICPC analysis [ 1 2 3 ]    NEXT >
 ACM ICPC analysis | Reply I've posted my solutions to some of the problems on my blog: http://blog.brucemerry.org.za/2014/06/acm-icpc-2014.html. I'll update it as I solve more of the problems.
 Re: ACM ICPC analysis (response to post by bmerry) | Reply > I'm pretty sure I've seen either this exact problem or a very similar one before.I'm pretty sure too.
 Re: ACM ICPC analysis (response to post by bmerry) | Reply The ICPC Live analysts did prepare the solutions presentations for all tasks, but sadly due to scheduling issues most of them remained unaired.Here are the slides I prepared for problem I: http://people.ksp.sk/~misof/share/wf_pres_I.pdfFor problem I, the team from Comenius U was the only one that had the intended solution. A few other teams had randomized solutions that are hard to break, and the rest (including Iowa State who had the fastest time) just got lucky that the test data did not kill their particular heuristic.For problem E, I came up with the same solution Bruce already describes nicely in his blog: this is basically just DFA minimization. (As for the worst case, there are at most nk iterations, because we only split the original equivalence classes into smaller and smaller ones, and at the end there are at most nk of them.)There is also an alternate solution to E based on hashing. Basically, we can just generate and hash everything reachable from a given vertex starting via a given edge in 1, 2, ..., sufficiently many steps, and then compare two vertices by comparing their cyclic sequences of hashes. This is basically a poor man's approximation of the automata-based solution. It's probably easier to come up with, but finding a usable hash function is still a very non-trivial exercise.
 Re: ACM ICPC analysis (response to post by ffao) | Reply Surveillance (Problem K) was also a repeat from USACO Feb 2010 (Covering the Corral):http://tjsct.wikidot.com/usaco-feb10-gold
 Re: ACM ICPC analysis (response to post by tehqin) | Reply The USACO analysis has a nice alternative solution, that takes linear time after initial sorting: http://cerberus.delos.com:790/TESTDATA/FEB10.corral.htm