TopCoder Member SRM 489

14 лет назад, # |

Они, случайно, не перепутали задачи 500 див1 и 1000 див2?

→ Ответить

Jokser

14 лет назад, # ^ |

Как решать див2 1000? У меня на ум приходит только хэширование всех состояний и бфс. Ну и отсечения делать по-возможности.

→ Ответить

Connector

14 лет назад, # ^ |

Скорее всего венгерский алгоритм (ну или парасочетание с помощью минкоста).

Каждой фигуре из начального состояния соответствует какая-то фигура из конечного. таким образом для каждой пары фигур можно определить сколько понадобится ходов для перехода.

→ Ответить

14 лет назад, # ^ |

А что делать, когда все кони уже стоят на своих местах, но их надо подвинуть, чтобы пропустить пешку?

Пример 1:

...

.N.

.P.

---

.P..

.N.

...

Пример 2:

..P.P..
.P...P.
...N...
.P.P.P.
..P.N..
.......

-------

..P.P..
.P.P.P.
...N...
.P...P.
..P.N..
.......

→ Ответить

Connector

14 лет назад, # ^ |

"Moreover, a square may contain more than one piece."

→ Ответить

14 лет назад, # ^ |

Спасибо. Я условие только мельком читал, думал там обычные шахматные правила.

→ Ответить

14 лет назад, # ^ |

Я вот тоже думаю как решать. Оценка сверху количества позиций не такая и хорошая:

$\text{[math]}$

Но может решение и есть простой бфс, это же див2 всё-таки.

→ Ответить

Xazker

14 лет назад, # ^ |

Всего 20 фигурок. Задача на минимальный по стоимости парасоч, можно решить венгерским или мин костом, но это для изврата, динамика 20 * (2 ^ 20) (маску обработанных справа, количество обработанных слева) лучше подходит.

→ Ответить

steiner

14 лет назад, # |

+24

Поздравляю с победой!

→ Ответить

Egor	14 лет назад, # ^ \| 0 спасибо → Ответить

Connector

14 лет назад, # |

Как решается див1 1000?

→ Ответить

Egor	14 лет назад, # ^ \| +3 Вот мой код Если возникнут вопросы - you are welcome → Ответить

maksay

14 лет назад, # ^ |

Во всех решениях этой задачи я увидел ДП по номеру добавляемого дерева ( в порядке убывания радиуса ), еще одному параметру и собственно получаемой длине. Вот этот загадочный параметр, я так понял, что это что-то типа количество пар среди уже вставленных, между которыми нельзя вставлять новые деревья. Есть ли какая-то более простая интерпретация и правильно ли я понял?

→ Ответить

Egor	14 лет назад, # ^ \| 0 Скорее это количество мест, куда еще можно вставить дерево (при этом несколько подряд идущих мы считаем за одно) → Ответить

14 лет назад, # ^ |

Так в итоге, что является состоянием динамики?

→ Ответить

14 лет назад, # ^ |

Для каждой вершинки в порядке возрастания r надо определиться: либо соседние будут с большим индексом, либо одна из соседних уже есть, и тогда их можно "объединить" в одну вершинку, либо обе соседних уже в наличие, придётся объединять три вершины.
Параметры: номер обрабатываемой вершинки, текущая сумма длин внутри объединенных вершин, текущее количество объединенных вершин.

→ Ответить

14 лет назад, # ^ |

← Rev. 3 →

+11

Отсутствовал вторую половину SRM, 1000 сдал сейчас на практисе.

Отсортируем деревья по возрастанию r.
Представим что перестановка это такой граф-цикл из N+1 вершины. Чтобы получить по графу перестановку надо разрезать цикл по N+1-ой вершинке. Вес ребра i-j в графе это r_max(i, j)
Представим себе следующий разрез: вершины с 1 по i в одной части, i + 1 по N в другой. Пусть через этот разрез проходит s пар рёбер. Будем считать число вариантов соединений в левой части разреза.

Три параметра: i - текущая вершинка которую мы переносим через разрез, s - сколько пар рёбер есть в разрезе (проходит из одной части в другую), w - текущая длина перестановки, если учесть все рёбра между вершинами 1..(i - 1).
Значение - количество графов оказывающихся в "левой" части разреза.

Внутри надо перебрать сколько рёбер ведёт из вершины i налево, а сколько направо. Варианты:
2-0 : таких вариантов s * (s - 1) * 2, при этом s надо уменьшать на 1. Вес увеличивается на 2r_i
1-1 : таких вариантов ровно s, при этом s не меняется. Вес увеличивается на r_i
0-2 : вариант один, s увеличивается на 1.

→ Ответить

14 лет назад, # ^ |

не очень понятно, что значит "перестановка это граф-цикл из n+1 вершин". имеется ввиду набор циклов или что то другое? сколько элементов в перестановке n+1, если нет зачем фиктивная вершина?

→ Ответить

14 лет назад, # ^ |

Фиктивная нужна чтобы не вводить ещё два параметра - были ли конечные вершины цепи и есть ли сейчас от них отводы идущие через разрез. А так генерим все циклы и разрезаем их.

→ Ответить

14 лет назад, # ^ |

понятно, спасибо.

→ Ответить

14 лет назад, # ^ |

еще хотелось бы спросить, как получается ответ на задачу?

→ Ответить

14 лет назад, # ^ |

Мы будем знать сколько перестановок деревьев можно разместить на W лунках для каждого W. Ответ это сумма по W всех количеств, помноженных на биноминальные коэфициенты (надо вставить оставшиеся D-W лунок в N+1 место между деревьями)

→ Ответить

14 лет назад, # ^ |

Угу... теперь всё стало окончательно понятно, большое спасибо за разбор)

→ Ответить

14 лет назад, # ^ |

Наверное имелось ввиду: Значение - количество заданных состоянием перестановок.

→ Ответить