Блог пользователя Petr

A week that needs a suffix structure
Автор Petr, 10 лет назад, По-английски

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

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится -22 Проголосовать: не нравится

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.

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

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)?

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +35 Проголосовать: не нравится

    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 :)

    → Ответить