Как вы решаете задачи с Марафона?? Хотелось бы услышать от опытных в этом деле людей какие-нибудь полезные советы, идеи. А то надоедает каждый раз читая таску с Марафона думать лишь о полном переборе =) .. Буду очень рад услышать ваши советы
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3803 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3627 |
| 4 | ecnerwala | 3584 |
| 5 | orzdevinwang | 3573 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | Radewoosh | 3542 |
| 9 | jqdai0815 | 3532 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 163 |
| 2 | maomao90 | 160 |
| 3 | adamant | 159 |
| 4 | maroonrk | 152 |
| 5 | -is-this-fft- | 150 |
| 6 | atcoder_official | 148 |
| 6 | SecondThread | 148 |
| 8 | nor | 147 |
| 9 | TheScrasse | 146 |
| 10 | Petr | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 07.07.2024 18:54:50 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
Я не спец в этом вопросе, но попробую объяснить, как я это понимаю, на примере указанной задачи. У нас есть ломаная, которую мы назовем особью. Ее качество обратно пропорционально площади, которую она занимает. Пусть у нас на некотором шаге есть несколько особей, мы хотим получить новые. Это можно сделать двумя способами:
1) Просто повернуть одну в некоторой точке. Это будет мутация.
2) Можно взять две особи, у одной из которых качественное начало, а у другой - конец, попробовать их скрестить. Лично я этого не делал, поэтому не могу описать более детально.
После того, как новые особи (ломаные) получены, мы отсекаем нежизнеспособные (в данном случае, которые пересекают себя). Затем на следующий шаг мы возьмем часть хороших, немного средних и несколько плохих и повторим. Я выбирал с помощью рандома и магических констант :) Плохих надо брать обязательно, иначе можно быстро упереться в локальный максимум, который может быть далеко от глобального. Ну и так пока не закончится разрешенное время.
Здесь тонкий момент в выборе функции оценки качества особи. В данной задаче занимаемая площадь - вполне адекватный критерий, в то время, как в других задачах подбор такой функции может оказаться весьма нетривиальной задачей.
Когда я решал Planarity, у меня все уперлось в быстрое нахождение количества пересечений ребер - т.е. в получение значений функции. У OBepkJloEP ключевым моментом была скорость создания нового экземпляра. В некоторых задачах бывает сложно понять, что именно надо оценивать, чтобы добиться желаемого результата.
Как я понял, аналогичным образом решаются процентов 70-80 марафонов. В остальных случаях, конечно, надо закапываться в теорию, но подчас это не так эффективно. С тем же Planarity, я перерыл с десяток статей по рисованию графов, которые либо сводились к простым методам оптимизации (имитация отжига, генетические алгоритмы), которые для успеха надо было лишь нормально подогнать к ограничениям, либо были слишком узкоспециализированные и сложные и вообще не подходили к задаче
Далее, там, насколько мне помнится, коряво написан сам генетический алгоритм (застревает на локальном максимуме и не идет дальше). Плюс очень медленно выполняется подсчет числа пересечений (кажется, за четвертую степень).
На плюсах - посмотреть, сравнить скорость, ага))
Общался с одним чуваком, который на них неплохо укатывал, и один раз был в шаге от ТЦО. Он использует всегда генетические алгоритмы.
Я думаю на самом деле что большинство участников используют генетические алгоритмы. Но я не изучал вопрос - это только предположение.
В оптимизационных задачах обычно используют стандартные методы(генетические алгоритмы, имитация отжига и т.п.), а для прохождения в топ нужно использовать всяческие умные ускорения, как асимптотические, так и неасимптотические, и различные эвристики. Такими были, например, первые два раунда последнего ТСО. Еще был случай(Nasa Topcoder Challenge), когда очень и очень неплохие результаты давала обычная динамика. Но всё-таки к таким задачам подход вполне однообразный.
Среди остальных же задач встречается всякое, различные ИИ, дешифрование, поиск различных вещей , ну и вообще почти всё что угодно:) Здесь нужно хорошенько поработать над задачей и искать интересные идеи. Для меня показателен пример контеста про разбитую плитку, где можно было получить баллов 90 из 100 максимальных просто рассмотрев, как строятся тесты, и сделав соответственный прекалк.
Вообще, обычно в марафонах рулят хорошие свои идеи, стандартные алгоритмы если и встречаются, то только как кусочек задачи. Поэтому подход к каждой задачке свой, хотя, думаю, опыт "красных" тоже им неплохо помогает:)