Блог Ивана Комарова -

Могу тебя утешить: Петино решение ненамного лучше, а то, что ты успел за время контеста графику написать, есть гуд. Я вот, например, это сделать не успел.

(Ответить) (Thread)

Кстати, а как в ЖЖ код вставлять?

(Ответить) (Thread)

Сегодня было два способа решения этой задачи.
Либо применить мозг и понять, что нужно посчитать разницу попаданий этих точек в круги.
Либо строить полный граф переходов и потом искать там путь (Флойдом например), при этом во втором случае выходит простыня кода, которая заведомо проигрывает по скорости написания первому решению.
К сожалению чаще всего не получается выбить из головы неоптимальное решение, если оно работает, и в принципе легко пишется.
А твоя графика продолжает иллюстрацию этого принципа)

(Ответить) (Thread)

Возражаю: уже на составление эквивалентного графа требуется применение мозга. Просто кому-то "неповезло" догадаться до способа, которым можно граф составить, прежде, чем короткое решение.

(Ответить) (Parent) (Thread)

Вот вот... Впоследствии, решая в практис руме, сразу же реализовал первый способ. А вот потом для графов уже пришлось применять мозг =)

(Ответить) (Parent) (Thread)

Так граф же деревом в итоге получается. Не нужен никакой Флойд, достаточно поиска в глубину, причём даже запоминать посещённые вершины не надо.

У Славы Исенбаева точно такая же идея, но он гораздо чище меня написал.

(Ответить) (Parent) (Thread)

Ну мне флойд проще, чем дфс)
Это же 300, тут почти всегда пишешь как тебе удобнее, а не как работает быстрее.

(Ответить) (Parent) (Thread)

Позаимствовал код :)

(Ответить) (Thread)