Через два часа (16:00 MSK) состоится Single Round Match 611. Не пропустите, и желаю удачи!
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
18:53:58
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
18:53:58
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| 3 | atcoder_official | 162 |
| 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
Время на сервере: 22.11.2024 22:41:03 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
Как решать третью задачу div2?
Как решать 250 div1?
Проверь — можно ли с помощью второго набора элементов получить каждый элемент из первого. Потом наоборот. Для проверки конкретного элемента одного набора можно использовать только те элементы из второго набора, на которые он делится. Если из lcm таких элементов получается проверяемый, значит его можно составить.
Например, проверяем 12 для чисел 2, 6 и 4. 12 длится на 2, 6 и 4, но lcm (2,6,4) = 24, 24!= 12, а значит по вашему алгоритму его составить нельзя. Хотя его можно составить из 2 и 6.
В чем неправда?
UPD: А кажется Lcm 12, все понял:)
Как нормально решать 550 div 1? Я думал над какой-то ДП по подмножествам, потом ничего не придумал, написал решение, которое запускает градиентный спуск кучу раз, пока не наступит ТЛ, и оно прошло. Мне интересно точное решение, которое можно доказать. Вроде бы, я ни у кого не видел динамику по маскам, а тогда не ясно, почему ограничение до 20.
Да, я тоже долго думал, как решать по маскам — вообще ничего не придумал. Потом открыл решения и удивился, ни у кого 2^ нет. А можешь подробнее идею описать, как конкретно писал спуск?
Генерим какое-то случайное дерево. На каждом шагу градиентного спуска повторяем следующее. Удаляем одно случайное ребро и выбираем случайное ребро из тех, которые соединяют разные компоненты связности и при этом уменьшают ответ. На одной итерации град. спуска мы попробуем удалить 10 случайных ребер, после чего выберем одно, которое сильнее всего улучшает ответ (как проверять улучшение, я написал). Когда 15 итераций подряд мы не смогли улучшить ответ, делаем брейк. Теперь опять строим случайное дерево и повторяем все с самого начала, пока не наступит ТЛ.
Если знать среднее арифметическое длин ребер в оптимальном решении — пусть это будет m — то сами ребра можно восстановить, найдя минимальный остов в графе, где ребра с изначальным весом x весят (x - m)2. MST зависит только от относительного порядка весов ребер, значит если перебрать все такие порядки(зависящие от m), то можно найти ответ. Ну а два ребра с весами x1, x2 меняют относительный порядок когда
, генерим все эти точки, сортируем, на каждом промежутке берем m и ищем остов.
Ограничение до 20 потому, что решение за O(n6logn)