Petr's blog

A week that needs a suffix structure
By Petr, 10 years ago, In English

http://petr-mitrichev.blogspot.com/2014/07/this-week-in-competitive-programming_29.html

  • Vote: I like it
  • +27
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

nothing about Codeforces Round #258?
i'm a bit disappointed! :(

EDIT: hmm, i guess it's because it was a Div-2 only round. Petr never mentions those in his blogs.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

Can't find any discussion of your heuristic solution of TCO-Round-3A hard problem.

You have implemented (as far as I understand your solution) a heuristic for shortest Hamiltonian path, namely local search with random restarts. Local search checks every 2-opt operator (in random order) and applies it if it improves answer.

It is interesting to know what your intuition was and how much evidence you had that this heuristic will find optimal answers on 50-vertex graph of this problem, especially if we mind the fact that 2-opt heuristic is not the most powerful (unlike 3-opt or Lin–Kernighan for example)?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +35 Vote: I do not like it

    I'm planning to write a separate blog post about that solution.

    Thanks for the links to 2-opt, 3-opt and Lin-Kernighan! I was not aware of the publications on this subject.

    In short, my situation was quite straightforward: I understood the problem statement incorrectly (I didn't notice that tubes were not intersecting), and couldn't come up with a solution, so I decided to implement a heuristic which I remembered working well in a IOI 2002 practice problem (http://www.ioi2002.or.kr/eng/PracticeCompetitionMaterial/red.pdf). I was expecting it to fail :)

    → Reply