Уже подошел к концу очередной SRM. Хотелось бы услышать решения второй задачи див1, с доказательством верхней границы времени работы.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
11:32:39
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
11:32:39
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 06:02:22 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
За 5ю степень пойдет? Будем оценивать качество каждой фирмы как 2 * число компонент — число вершин — 2. Тогда для каждой фирмы потребуется ее качество портов (или 0, если оно отрицательно). Считаем динамикой, состояние — (корень, номер последнего необработанного ребра), результат — вероятность для каждой пары качеств (при этом первым идет качество той фирмы, которой принадлежит корень). Пересчет за четвертую степень, состояний O(V + E)
Да, красивое решение
Не совсем уверен, но, по-моему, можно сделать за 3ю степень полностью забив на вторую фирму. Состояние (качество фирмы номер 1, какой фирме принадлежит текущая вершина). Все остальное тоже, только пересчитываем за квадрат. Так мы посчитаем матожидание денег, которое заплатит первая фирма. Умножив на два эту величину получим ответ.
Супер!
Есть хоть какие-то идеи, как решать 900? (И почему она 900, а не 1000 тоже).
Была мысль искать отрицательные циклы в каком-то странном графе на ребрах, пока получается. Но это непонятно ни почему работает, ни за сколько работает.
У меня получалось либо решить задачу для формулировки, когда можно делать циклы длины 2, либо только проверить, есть ли решение для исходной задачи (когда нельзя делать циклов длины 2). Объединить так и не вышло.
Сделаем граф двудольным. S — исток, T — сток, v — вершина, v_1 — копия вершины горизонтальная, v_2 — копия вершины вертикальная.
Будем искать сейчас mincost-maxflow добавим ребра пропускных способностей 2 и стоимости 0 из S->v, v->T. Дальше, добавим два ребра из v -> v_i пропускных способностей 1 и стоимостей 0 и field[i][j] == 'C'. дальше соеденим вертикальные копии с вертикальными и горизонтальные с горизонтальными ребрами стоимости 0 и пропускных способностей 1. дальше пустим поток понятно какой велечины проверим, что он достаточно большой и выведем стоимость. Кажется баги нет семплы оно проходило до глюков с ареной у моего компа.
Решение прошло в дорешке тупой Форд Беллман с очередью работает максимум 100ms.
А где здесь вообще ребра стоимости >0?
field[i][j] == 'C' оно бывает 1 или 0
А, сорри, не заметил. Да, решение похоже на правду.
Я надеюсь они не заставят дейкстру с потенциалами писать... я хочу что-бы фордбеллман с очередью прошёл, а то тогда это на 900 совсем не катит... он у меня был написан на контесте, но у меня что-то с компом случилось и ареной... и не смог отправить...
Да, решение правильное и ФордБеллман с очередью прошёл... =( Обидно из-за глючности софта не сдать 900 :'(