Для тех, кто не в курсе: речь про вот этот гроб.
Вопрос к тем, кто страдал той же фигней, что и я пытался решить эту задачу: кто что пихал? Т.е. какая была функция оценки позиции, какие отсечения, ну и какой вердикт :).
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
5 дней
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
5 дней
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.11.2024 16:26:21 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Перепиши на C++, может зайдет :)
Нет, у меня все равно слишком неоптимальный перебор. Конечно, большая часть крутых тестов все равно решается, но, к примеру, за минуту-две, а на одном тесте решение вообще падает с OutOfMemoryException.
P.S. Легко сказать "перепиши на С++". У меня там больше тысячи строк кода, я это переписывать стану только тогда, когда оно будет работать на самых крутых тестах, к примеру, 10 секунд или около того.
Я толкал DFS-подобный перебор по состояниям вида (расположение ящиков, компонента связности, в которой стоим). После получения очень длинного ответа укорачивал его, проходя внутри компоненты кратчайшим путем и пытаясь "срезать" цепочку состояний. #TLE из-за первой части немного предсказуем.
У меня был бфсоподобный алгорим, типа A* (A-star), насколько я понял его из вики. бфс шёл вроде как с двух сторон, попеременно вынимая элементы из этих двух очередей, останавливаемся когда встречаем вершину достижимую с обоих сторон. Помимо этого была оценка на близость к ответу(как в A*) которая в идеале должна была вычисляться венгерским алгоритмом между ящиками и их позициями, но по факту какой-то жадиной для скорости. Кроме того использовались отсечения для тупиков. т.е. например если какой-то из ящиков загнан в угол не являющийся точкой назначения ящика, то бессмыслено сиськи мять и гонять оставшиеся ящики туда-сюда, ибо этот ящик так в углу и останется. Некоторое время у меня был АЦ, потом отсудили, потом опять АЦ, потом стало много житрожопых тестов и это не проходит снова и по видимому безповоротно. Имхо такую лажу более не впихнуть.
UPD: после ограничения размера графа поиска "с конца" до 2^13 вершин решение прошло до 57-го теста.
Насчет "лажи" Вы зря. Все нормальные решалки использую какую-то разновидность A*.
У меня, кстати, тоже A* с жадной оценкой позиции (правда, я учитываю еще количество ящиков, стоящих не на месте). Отсечения такие: таблица клеток, из которых ящик не допихивается ни до одной цели; поиск заблокированных ящиков (хитрым ДФСом); таблица "плохих" паттернов 2х2 и 3х3; поиск совершенного паросочетания между ящиками и целями. Мне сейчас интересно: может, кто-то писал отсечения покруче?
Когда-то, в марте 2008-го, я доходил до 56-го.
В январе 2012-го попробовал сдать еще раз. Аккуратно написанный bfs по состоянию "где сейчас ящики" дошел до 22-го теста. Далее я насчитал следующее: "предположить, что на поле нет ящиков, и для каждой клетки предподсчитать, куда можно из нее переместить ящик". Отсечение "проверять, что каждый ящик может дойти до конечной клетки, в которой сейчас нет ящика" доходит уже до 53-го теста. Если проверять, что существует паросочетание из ящиков и конечных клеток, то в системе это все равно падает на 53-м, но на моих тестах работает заметно лучше (раз в 100, 1000 быстрее). Далее планировал добавить meet-in-the-middle, но поленился.
UPD: не bfs, dfs с запоминанием
Описанное мною чуть выше решение падает на 55-ом тесте по Crash. На самом деле памяти нехватает, это ассерт.
Да, я знаю, можно лучше. Кстати, мое основное отсечение отлично ложится на твое решение (улучшить "отсечения для тупиков"). Если добавить, возможно получится AC.
P.S. По-моему, слова про 55-й тест лучше написать в собственно описание решения, читателям удобнее будет собирать информацию :-)
Насчет АС у решения с простым ДФСом я серьезно сомневаюсь, потому что от порядка обхода вершин многое зависит. К примеру, в моем решении простая жадина получает ТЛЕ 55, та же жадина + произведение количества ящиков, стоящих не на месте * глубину позиции — уже ТЛЕ 62 (то и другое — при наличии отсечения по паттернам 2х2 и 3х3, без него или ТЛЕ 23, или ТЛЕ 55, но последнее — при наличии отсечения с помощью паросочетания и хитрого поиска заблокированных ящиков).
У меня разница между TL92 и AC оказалась очень смешная. Я просто в A* начал обходить вершины просто по эвристике, а не по сумме пройденного расстояния и эвристики. До этого я думал, что добавление дедлок-паттернов 4x4 из ретро-БФСа достаточно для сдачи задачи, но оказался неправ. И еще в процессе пихания узнал, как пишется венгерский алгоритм за $$$O(n^3)$$$.