Закончился очередной этап опенкапа, давайте обсуждать задачи.
Интересует, как решать D.
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 дней
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 дней
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.11.2024 05:26:28 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
Тут говорят, что так же, как и D с прошлого опенкапа
Можно подробнее?
Как вы умудрились не сдать ее?
У нас не пересекаются составы на первые два этапа
Хм, в задаче про "свертку" все очень мило решалось независимо по битам, так как требовалось вывести особую сумму. У нас решение задачи с всесиба выглядело как-то совсем по-другому.
Для начала поймем "наивное" решение: мы можем для каждой маски перебрать ее подмаску, которую должен знать один человек из пары, а оставшуюся должен знать второй. Получилось 321. То же самое в немного другой интерпретации: для каждой книги мы можем перебрать, кто ее будет знать (0 — никто, 1 — первый, 2 — второй, а если знают оба, то мы можем выбрать кого-то одного).
Теперь заметим, что возможных вариантов битовой маски для пяти книг (математически — монотонных функций от пяти переменных) всего лишь 7581. Поэтому для каждой пары монотонных функций от пяти аргументов мы можем предподсчитать их дизъюнкцию.
После этого мы можем перебрать все возможные варианты для 16 книг (как бы выполнив подстановку 16 переменных в нашу булеву функцию), это 316. Раз мы 16 переменных фиксировали, значит каждый участник пары превратился в булеву функцию от 5 переменных, а дизъюнкции таких функций мы уже знаем.
Решение за O(n*2^n): http://codeforces.net/blog/entry/14344#comment-193260
Лично мне ещё интересно услышать про 3, 5 и 8.
3) Переберем k. Пусть k' -- первая степень k, бОльшая n. Проверим за n / k', что соответствующие подстроки размера k' равны префиксу размера k'. После этого рекурсивно проверим это для префикса размера k'. Итого для одного k получается
, что суммарно дает решение за 
.
Подстроки можно сравнивать хешами, тогда вообще O(n) будет.
UPD: На самом деле получается O(n log n) из-за суммирования по всем k.
Мы z-функцией сравнивали. А как линию сделать? Там n log n из-за суммы по всем k.
Да, действительно, исправил.
Воу-воу, откуда n·log2(n) то? Если я правильно понял, то для одного k ты делаешь n / k + n / k2 + n / k3... = C·n / k, то есть в итоге O(n·log(n)).
В третьей задаче можно просчитать Z-функцию для строки, а далее надо заметить, что паттерны строк для фиксированного k (которые появляются при генерации Si(k)) имеют вид ki * m где m пробегает значения от 1 до k - 1, а значит, чтобы проверить всевозможные значения k, требуется достаточно мало действий.
В 5-ой задаче зашел N3logN: для каждого возможного значения ширины можно бинпоиском найти наибольшую высоту кровати, которую можно протолкнуть через портал (делается dfs-ом с убиранием вершин, через которые нельзя пройти), а дальше надо найти по данным значениям ответ.
В 5-ой можно избавиться от логарифма, если учесть тот факт, что функция монотонная — с увеличением ширины максимальная высота может только уменьшаться. Поэтому вместо того, чтобы для каждой ширины делать независимый бинпоиск, будем использовать идею двух указателей.
в 5 упихали такое: запустим дфс из первой вершины. будем хранить
vis[vertex][width][height]— были ли мы в этой вершине с такими widht,height. После дфса тупо переберем все width и height у последней вершины, и выберем наилучший. Только нужно отсекать ветки dfs'a, когда мы зашли в вершину с более худшими параметрами, чем раньше.В 5-ой для каждого возможного значения ширина запустим Дейкстру и найдём максимальную высоту
8, будем поддерживать для каждой колонии жива она или нет и очередь с приоритетами с расстояниями до других колоний, делаем n-1 итераций, каждый раз выбираем минимум (из очередей, выкидываем вершину если она относится к мертовй колонии), затем объединяем две колонии, пересчитывая соответствующи столбец и строку в таблице. Получается N*N*lgN
В 5-ой, кстати, можно было для каждого значения ширины построить остов на переходах с максимальной возможной высотой — O(MAXW * N^2) с алгоритмом Прима.
кто ещё сдаёт на ejudge, уходите с него! один и тот же код (по 8ой) сначала получил тле 7 на ejudge, потом OK на yandex за 2.2 сек, а потом OK на ejudge.
upd. язык — c++
Да, с 4-ой тоже самое.
На Яндексе 5.5, на ejudge'е был TL.
Это все очень печально, на самом деле. А нельзя никак на одних машинах тестировать?
Насколько я знаю, там все тестируется на одной машине. Даже слишком на одной. На нескольких ядрах в параллель. Проблема скорее из-за этого может быть, если много памяти. Хотя возможно я давно не прав. snarknews знает лучше.
Ну просто тогда странно: 5 подряд запусков на Яндексе проходят 8-ый тест за < 5 секунд, 5 подряд на ejudge получают TL8 (при TL = 6 секунд).
http://i.imgur.com/Hs2ZgyB.png
http://i.imgur.com/7UJxmgA.png
Самое решение для тестов:
http://pastie.org/9691348
Яндекс и ejudge это-то разные машины разумеется. Я скорее про случай с перепосылкой в ejudge меняющей вердикт.
Как решалась сумма из второго дивизиона? Тринадцатая задача, вроде как.
а как 10 решать про бассейн?
Вспомнить что нужным свойством (постоянным углом между касательной и направлением на фиксированную точку) обладает логарифмическая спираль, потом взять несложный интеграл.
Можно честно решить двумерный дифур, либо перейдя в полярные кординаты, либо записав его для комплексной функции вещественной переменной
Скажите, а у кого-нибудь получилось сдать в дорешивание D? Пытаемся это командой сделать, но всё, что угодно, даже полный перебор, в котором ну не может быть ошибки, или забитый в код вывод ответа на сэмпл, получает WA 1.
Если на первый вопрос никто не откликнется, но у вас есть сданное на контесте решение, отправьте его, пожалуйста, в дорешку, чтобы можно было наверняка знать, что-то не так с дорешиванием или всё-таки с нами?..
upd. Разобрались: оказывается файлы не нужны, а мы с ними отправляли. Спасибо всем, кто отозвался.
У нас хоть и не сданное, но получает ровно тот же TL17, что и на контесте — т.е. первый тест проходит — как в дорешке на opentrains, так и на Яндексе.
На яндекс контесте с файлами проблемы, попробуй без них
Расскажете в личку поподробнее?
Кому-нибудь приходилось бороться с WA 15 по 10-й задаче?
а результаты собственно Всесиба где-то есть?
Конечно же, нет, гоплан лежит
Замороженные результаты Всесибирской олимпиады им. Поттосина (ACM номинация) и замороженные результаты матча Москва-СПб.
А почему за Москву играет МИСИС а не Moscow SU Tiramisu?
При выборе состава команды Москвы предполагалась симметрия по вузам: 3 МФТИ 2 МГУ 1 МИСИС — 3 ITMO U 2 СПбГУ 1 SPb AU. При этих условиях выбор делался по результатам Московского ЧФ.
А про участие команд ВШЭ на онсайте в момент выбора команд я, увы, забыл.
Any idea for 9?
The solution to D uses technique known as "fast zeta transformation".
Refer the solution of EvenPaths for more detail.
Would you please fix the link?? It looks unavailable
Поздравляю команду Saratov SU 1 с победой!!! Супер круто!!!
Еще не до конца ясно, победили ли они — ранклисты с Яндекса и с ejudge еще не объединили. Или я ошибаюсь, и где-то есть уже объединенный ранклист?
Результаты второй номинации Всесибирской олимпиады им. Поттосина ещё не разморожены.
Более того, результатов нет ни у кого, кроме жюри Всесибирской олимпиады (это сделано во избежание возможной утечки), в частности, я не заносил полные результаты ни в одну из внешних систем (ejudge, Я.Контест), они там есть только в замороженном виде. Так что итоговые результаты Гран-При будут только утром 4 ноября, после закрытия основного мероприятия.
7ю задачу как решать? Там макс парсоч или что-то такое?
без букв — стандартная задача, да, решается парсочем. одинаковые буквы нужно сжать в одну вершину, так как по условию чётность у них одинаковая.
Перечитывал условие раз 10, а то что четность одинаковая у окрашенных пропустил... Спасибо)
hello,ftiasch,where can i find the problem of open cup GP of Siberia
http://official.contest.yandex.ru/contest/811/enter/
Когда все-таки смержат ранклисты с Яндекса и ejudge? Очень хочется увидеть достоверную таблицу результатов!
Кто-нибудь может объяснить решение 9ой задачи про треугольники? У меня ничего толкового не получается.