Приглашаем вас поучаствовать в турнире трех четвертьфиналов — командном онлайн-соревновании, которое будет проводиться параллельно с четвертьфиналами ACM в Москве, Минске и Санкт-Петербурге в конце октября. Турнир будет организован совместными усилиями команды Яндекс.Contest, Олега Христенко (snarknews) и жюри перечисленных четвертьфиналов ACM ICPC. Даты и времена проведения: Московский ЧФ (регистрация) — 21 октября, 14:00 по Москве, Минский ЧФ (регистрация) — 28 октября, 11:00 по Москве, ЧФ в Санкт-Петербурге (регистрация) — 3 ноября в 12:00 по Москве.
Команды, участвующие в официальной версии одного из четвертьфиналов, могут поучаствовать в онлайн-версиях остальных четвертьфиналов. Команды, не участвующие ни в одном из официальных четвертьфиналов, могут принять участие онлайн во всех трех раундах. Результаты каждой команды на всех соревнованиях, официальных и неофициальных, будут учтены, итоговый зачет турнира будет производиться по системе Гран При 30.
Регистрация на онлайн-версию каждого четвертьфинала идет непрерывно вплоть до старта соревнования. Создать команду в системе Яндекс.Contest вы можете по ссылке «Мои команды». Все приглашенные в команду участники должны подтвердить своё участие в соревновании. После успешного создания команды необходимо зарегистрироваться на соревнование, указав вашу команду.
Правила отдельных раундов совпадают с правилами официальных четвертьфиналов.
Потренироваться сдавать задачи в системе Яндекс.Contest можно, приняв участие в A + B virtual.
На ваши вопросы и комментарии к этому посту могут отвечать несколько человек, кроме меня: Владимир Тен (vtenity), Лев Толмачев (lev.tolmachev), Виталик Гольдштейн (goldvitaly), Олег Христенко (snarknews).
Следите за обновлениями!
UPD. Онлайн раунд московского четвертьфинала стартует 21 октября в 14:00 по Москве, чтобы все могли поучаствовать в Codeforces Round 146 и CodeChef cook-off.
UPD.2 Появились ссылки для регистрации на все три ЧФ и точные времена их проведения:
- Московский ЧФ — 21 октября, 14:00 по Москве.
- Минский ЧФ — 28 октября, 11:00 по Москве.
- ЧФ в Санкт-Петербурге — 3 ноября в 12:00 по Москве.
UPD.3 В таблице результатов доступны результаты как онлайн-тура, так и официального тура московского четвертьфинала. Команды, поучаствовавшие в официальном московском четвертьфинале и регистрирующиеся на остальные туры, если они желают, чтобы их результаты были зачтены в турнире, должны указать в отображаемом имени команды в системе Яндекс.Contest строку, совпадающую или максимально похожую на ту, которая отображалась в мониторе московского четвертьфинала. Команды, поучаствовавшие в онлайн-версии московского четвертьфинала и являющиеся участниками официальных четвертьфиналов в Минске или Санкт-Петербурге, должны указать отображаемое имя в системе Яндекс.Contest, совпадающее или максимально похожее на официальное название команды.
UPD.4 Опубликован объединенный монитор двух прошедших туров по системе Гран При 30. В случае равенства очков по системе Гран При 30 мы дополнительно ранжируем команды по суммарному рейтингу по системе ИТМО, как на Открытом Кубке. Приносим свои извинения, что система разрешения ничьих не была опубликована изначально. Обращаем внимание команд, что склейка результатов производится по отображаемому имени. Команды, у которых не склеились результаты, отписывайтесь в комментариях. В третьем раунде проставьте себе ровно такое же отображаемое имя, как имя в объединенном мониторе. Мы даже собираемся с началом третьего раунда (точнее, как только хотя бы одна команда совершит посылку) в объединенный монитор добавить и третий раунд и надеемся, что объединенный монитор после этого будет показывать текущую ситуацию в каждый момент времени с учетом положения команд в третьем раунде турнира. Ясно, что для команд, участвующих в официальном четвертьфинале в Санкт-Петербурге, изменятся отображаемые имена, и потребуется некоторое время на их склейку.
Что слышно о заявленом мероприятии? Состоится? Осталась неделя до Московского ЧФ и хотелось бы иметь информацию для планирования тренировок и участия в контестах.
Состоится. Опубликовал обновление с более точными датами. Ссылки на контесты появятся чуть позже.
Неудачно как-то на 21-е попадает: Московский ЧФ пересекается с CF 146. А вечером еще CodeChef Cook-off (Гена проводит).
Ок, проведем с 14:00 до 19:00, чтобы можно было с 11:00 до 13:00 написать CF 146, а с 20:00 CodeChef.
Виртуальное участие потом будет, да?
Будет, но уже вне конкурса.
Вот еще что хочется спросить про виртуальное участие: можно ли начать виртуальный контест, скажем, в 13-00, если настоящий начинается в 11-00?
Потому что на Codeforces, например, надо ждать окончания настоящего контеста.
бывает же такое, авторы все-таки прислушиваются к мнению участников, и переносят... круто
Все ссылки для регистрации и времена начала опубликованы в апдейте к посту.
А на английском языке задачи будут?
Вообще-то вроде все соревнования официальной ветки ACM ICPC — с задачами исключительно на английском языке.
Спасибо, просто хотел убедиться.
В прошлые годы на Западно-Сибирском четвертьфинале задачи вроде были на русском.
А можно отрегистрироваться, и заново зарегистрироваться, если состав команды поменялся? А то в списке зарегистрированных состав команды не изменился. Или же просто не обновился?
Скажите название команды, я отменю регистрацию. Сами вы пока этого сделать не можете.
LU unusual.
Готово
Can you help me too?
The team is Mr Ron Anser
Done
а нам можно так сделать? StavTeam наша команда
а че так?
мы Larichev забыли добавить, и он гневался
ясно.
А где задачи, а то соревнование уже началось?
Условия задачи выдают "Сервис временно недоступен"
У меня одного сервис временно недоступен?
http://codeforces.me/blog/entry/5406#comment-108667
can't download problem statement (PDF file)
And here it is... The Russian statements :)
Did I just download the practise session Russian problems?
Походу все контесты сегодня будут откладывать на 10 минут)
Теперь задачи из пробного тура :)
У меня одного такие опасные задачи по ссылке?
Да что за фигня. Теперь там задачи пробного тура Яндекс тренировок.
Что-то никто ничего не пишет, у вас уже работает? У меня все еще кроме ленты новостей ничего не грузится(соревнования пустая страница).
Уже 45 минут контест идет. Пустая страница — какая-то старая версия браузера, видимо. Я сам на это когда-то жаловался, обещали поправить...
Как-то не хватает часов с остатком времени рядом с табличкой.
Ага, надо будет сделать.
За какую сложность решалась B? У меня динамика за O(N·A3·B2) получает ТЛ 9. Надо было ее оптимизировать или можно проще?
А там что, надо 3 билета держать на руках????
Да, надо 3. Тест:
Ууупс=)
У меня сложность, кажется, O(n B^4 A log что-то), но много отсекается. Решение такое. Сразу поэлементно сложим последовательности, получим последовательность из n нулей, единиц и двоек. Будем двигать окно длиной B по дням. Для каждого положения будем хранить мапу из кортежа значений в этом окне в минимальное количество действий, чтобы такого кортежа достичь (обнулив все левее окна и не трогая все правее). Но будем рассматривать не все кортежи, а только "разумные", то есть достижимые при "разумном" использовании билетов. При каждом положении окна запустим дейкстру по этой мапе, храня пометки в сете. Вершина — кортеж значений в окне, переход — купить билет ровно на этот период времени и каким-то "разумным" образом распределить его поездки внутри окна. Разумное использование билета — выбрать некоторое k и уменьшить первые k единиц до нулей и первые A-k двоек до единиц. После дейкстры посмотрим на все кортежи с нулевым первым элементов и для них сдвинем окно на 1 вправо, получая начальные кортежи для следующего положения окна. Достижимых вершин для каждого положения окна, кажется, O(B^3). Несмотря на длиный текст, пишется очень просто.
Как нормально решать Е? Миллион ифов и WA22.
там уродство с даблами, у нас упало на этом тесте 3 -0.1 -0.1 0.01
Ну 1 1 ответ, не? UPD: Отлично
у нас выбирало 2 1 2, потому что (-0.1)*(-0.1)>0.01
Надо было на паскале решать.
У вас может упасть на какой-то из перестановок этого теста: 3 1 -0.5 -2 Ответ 1. По-крайней мере у нас когда был ВА22 бага была на таком тесте.
а что делать, если ваши тесты проходит, а WA 19?
Можно написать генератор тестов, брутфорс и сравнить с ними.
А как J решать? Мы посылали quicksort, и получали WA13. Интерактор заваливал его?
У нас прошел обычный Mergesort. А Quicksort заваливался. Его интерактивно несложно завалить.
Блиин, всё настолько просто. Спасибо.
там вроде бинпоиском можно, у нас зашло
Эм, а где там можно воткнуть бинпоиск?)
это надо спрашивать у Creed...
ищем бинпоиском куда вставлять :) и получаем точную оценку на число операций.
Эм, а с чего бы ему вообще куда-то вставляться? нет же транзитивности.
не понял вопроса, но отвечу. поддерживаем отсортированную последовательность и ищем первое место, где a_i < newElement и newElemtn < a_i+1.
Вопрос: почему такое место есть? И если есть, то почему все будет хорошо с бинпоиском? Транзитивности-то нет.
Первое не найдете — транзитивности нет. А вот какое-то найдете.
Есть — потому что либо можно в начало либо в конец, либо где-то поменяется, туда и можно.
А бинпоиск находит какой-то корень не только на монотонной функции.
Да, действительно, согласен. Спасибо
да, согласен. я если честно не читал задачу, а только слушал решение от сокомандника. действительно просто поддерживает инвариант с тем, что a[L] < newEl и newEl < a[R]. и бинпоиск сойдется к какому-то корню
Приведите, пожалуйста, пример по заваливанию рэндомизированного qsort в интерактиве
Например, на каждый запрос (a < b) интерактор возвращает false если a == b, либо если уже просили сравнить (b < a) и тогда вернули true. В остальных случаях возвращать true.
Тогда, по-видимому, классический quicksort с рандомным выбором элемента будет заваливаться: каждый раз подмассив a[l..r] будет разделяться на очень неравные части.
Это не совсем корректный тест, по условию a == b быть не может, но вот возвращая все время false повалить можно. Спасибо, идея ясна.
Честно говоря, я не знаю всего условия. Но я не понял, почему тест не корректный. Я имел ввиду что-то вроде:
В условии прописано, что для любой пары ламп, джин точно знает, какая из них ему нравится больше. Поэтому условие
if (a == b)никогда не выполнится. Да это так, придирки.У нас quicksort на линейном порядке с медианой трёх случайных элементов в качестве опорного валился примерно на 15% запусков, посылать не рискнули.
Я не знаю, верно ли то, что я скажу далее. На сколько я понял(переводчик из меня фиговый), что в случае невозможности построить последовательность, то нужно вывести n + 1 0. В qs может возникнуть такая ситуация, что если построить орграф с ребром a-b, означающим, что b > a, то может появиться цикл, что как бы совсем плохо. Строго не доказывал, но проверял на существование этого цикла. Возможно я не прав.
P.S. Писал merge, скорее всего там цикла быть не может 100%. Но qs совсем другая.
P.P.S. Описанный выше способ с бинарным поиском — это вновь изобретенный велосипед. Называется сортировкой бинарными вставками
а что такое 18+, 16+... рядом с задачами? возрастные ограничения или сложность?
Это отсылка к новому закону о тв-программах, где указывается возрастной лимит. Сложность задач от этого вроде не зависела.
ну как сказать, во всех задачах кроме Е, в принципе, я думаю, совпало
Кто-нибудь в курсе, что за трешня с табличкой в итоге? Сперва продлили, потом вырубили за 5 минут до конца по service unavailable, сейчас показывает, что финальное время 5:35
Кое-какие накладки со временем начала. Подробнее ответит жюри, если посчитает нужным.
В одной из аудиторий МГУ произошёл сбой, из-за которого старт для этой аудитории был отложен на 35 минут (дисплеи у участников были выключены; дежурный ошибочно ожидал устной команды о начале контеста). Соответственно, только для этой аудитории турнир продлили.
Кроме того, по техническим причинам (различные инструкции, выданные дежурным площадок) команды, пишущие в остальных аудиториях МГУ, получили условия на 7 минут позже команд в МФТИ.
При подведении итогов жюри пересчитало результаты с помощью электронных таблиц; так как оба сдвига не повлияли на распределение призовых мест и путёвок в полуфинал, то было решено не затягивать закрытие и оставить в предварительных результатах всё "как есть".
В данный момент обсуждается вопрос о пересчёте таблицы перед публикацией окончательных результатов. Лог четвертьфинала для виртуальных контестов будет распространяться в пересчитанном виде.
Как решать H и G?
G: подвесим дерево за какую-то вершину, обойдем dfs, если во время обхода dfs направление ребра совпадает с направлением dfs по этому ребру, запишем на ребре 1цу, иначе 0. будем хранить для каждой вершины сумму ребер до нее от корня, а так же, ее глубину.
когда поступает запрос x, y: нужно чтобы все ребра от lca(x, y) до y были сонаправлены обходу dfs, а ребра от x до lca(x, y) противоположнонаправлены обходу dfs. это проверяется просто, если сумма х (по ребрам, которую мы храним) — сумма lca(x, y) = длине пути от x до lca(x, y), а сумма y — сумма lca(x, y) = 0, то "Yes", иначе "No"
А как предполагалось решать задачу D? У нас O(NlogN) получало TL20. Причем на случайном макстесте работало локально от 3 до 6 секунд.
Есть ли какое-нибудь линейное решение задачи?
На разборе рассказывали за (N log N + M log N). Суф. массив плюс хитрый стек возможных максимумов при фиксированной правой границей, двигаем правую границу постепенно слева направо, плюс RMQ.
У нас было такое же решение. Значит надо еще пооптимизировать.
На разборе NlogN решение рассказывали.
Нужна любая структура, которая умеет сравнивать суффиксы и искать lcp (даже хеши сойдут). Далее, можно решить задачу оффлайн — посортить запросы по правому концу, далее двигаем правый конец и поддерживаем 2 множества: для данного правого конца r множество суффиксов всей строки, начинающихся не правее r, которые бывают максимальными (это халява), и множество суффиксов префикса, заканчивающегося в r, которые бывают максимальными (это уже сложнее; будем добавлять туда все встречающиеся префиксы, а в процессе строить граф, если мы не добавляем в первое множество суффикс, начинающийся в r, то добавляем дугу из него в самый короткий элемент первого множества M; и удаляем r и всё, достижимое по дугам, из второго множества в момент времени r + LCP(r, M)).
Upd: Ну и понятно, как обрабатывать запросы, имея второе множество: это просто запрос минимума на отрезке.
Имхо, офигенная задача от Васи Астахова :) Вроде бы, наука до этого такое делать не умела. Ещё кажется, что это можно обобщить на онлайн-запросы.
А у жюри есть решение на Java (желательно без хешей)?
А то что-то даже в дорешивание не удается пропихнуть, и запас хаков уже исчерпан.
Ну я не жюри, так что не уверен, что мне следует на этот вопрос отвечать. Но если очень интересно — могу попробовать написать на Java сегодня вечером, я почти уверен, что зайдёт (особенно если без суффиксного массива решать).
Для других суффиксных структур алфавит слишком большой, а хеши в наше время каждый валить умеет.
Ну хеши можно писать так, что заранее заготовленными тестами они не валятся. В любом случае, попробую написать на java в ближайшее время.
Для четвертьфинала суф массив проходил с запасом, видимо на contest.yandex.ru кэш у машинок поменьше, а тл выставлялся по решению с хэшами, которое летало. Я попросил увеличить тл и провести реджадж на виртуальном контесте.
TL установлен в 4 секунды, все решения с вердиктом TL пересужены.
А кто сдал H, как? Мы придумали в две динамики за квадрат (количество путей, количество изолированных вершин) => (число способов, среднее), но свалились по #TLE из-за того, что пришлось считать в логарифмах.
Кстати, либо gcc тупит, либо сервер медленный — у меня локально на далеко не топовом ноутбуке решение из-под вижака работает 1.8 секунды, а на сервере оно не лезет в TL.
Считали те же две динамики, но без логарифмов. Чтобы первая динамика не вылезала за экспоненту дабла, делили перед пересчетом всю строчку на одно и то же число.
Ой блин, они, оказывается, числа одного порядка. Я почему-то в голове прикинул, что разброс между ними большой. А он, оказывается, равен примерно e.
Кстати, решение с логарифмами все-таки заталкивается под самую границу, если хорошо работать с памятью, выставить отсечение точно (2*i + j <= 4000) и не считать среднее в логарифмах.
У меня было 2 динамики. Первая f(n, k) говорит, сколько есть перестановок из n элементов среди которых k выделенных могут принадлежать циклам длины 1, а остальные — нет. Вторая g(n, k) — это то же самое, только не количество перестановок, а суммарное количество циклов в них. Чтобы ничего не переполнялось, сразу считаем это количество, деленное на n!. Для этого каждый раз при переходе делим результат на n.
Если у нас вся перестановка неизвестная, то ответ равен
. В общем случае, посчитаем сколько уже есть циклов (пусть это количество равно c), а также сколько есть цепочек (k) и сколько неизвестных позиций (d). Тогда ответ равен 
.
Да, то же самое, только я почему-то решил, что делить не получится из-за большого разброса значений и посчитал в логарифмах.
У нас линейное решение.
Считаем такую велечину f[n] = 1 + 1/2 + ... + 1/n это средние число циклов в перестановке длины n. Пусть у нас цепочек a, изолированных точек b, законченых циклов c потом считаем велечину
d = Sum[i = 0, i <= b, C(b, i) * (a + b — i)! * (f[a + b — i] + i + c)(-1) ^ i]
e = Sum[i = 0, i <= b, C(b, i) * (a + b — i)! * (-1) ^ i]
d — это суммарное число циклов в хороших перестановках e — число хороших перестановок
ну и ответ собствено d / e и считали всё в логарифмах
Кто-нибудь знает, почему в Java рекурсия глубины 10^5, с одним int в параметре получает stackoverflow?
Java version "1.6.0_20" OpenJDK Runtime Environment (IcedTea6 1.9.10) (6b20-1.9.10-0ubuntu1~10.04.3) OpenJDK 64-Bit Server VM (build 19.0-b09, mixed mode)
Запускается с параметрами -Xmx512M -Xss64M
В К у кого-нибудь были проблемы с хэшами?
Нет. Там и без хешей с мэпом нормально заходит. UPD Нет — в смысле с хэшами сдалось.
Время до окончания контеста (в правом верхнем углу) криво показывается: иногда показывается правильно, а иногда — на час меньше.
Что-то новенькое от Яндекса: сразу показывать полные результаты виртуальных участников.
В смысле полные?
Show external results и видишь все задачи, решенные командами в Минске и вчера в СПб
Зарегистрированным на контест не показывается) Да и посмотреть их можно было и раньше на официальном сайте ЧФ.
Но вообще этого не стоило делать, конечно.
Ну, делать стоило, только, как у всех, имитировать сдачу задач в реальном времени. Тогда и реальным участникам можно было показать.
Для участников она имитируется. Полные результаты видны только тем, кто не зарегистрирован на контест.
Если вам понравились задачи Western subregional contest 2012, то плюсуем (ну и минусуем те, кому не понравился)!!! Так же хочу услышать ваше мнение о нашем проблемсете! Спасибо. [моя один из авторов]
Мне очень понравилась легенда задачи про немонотонные последовательности :)
В некоторых задачах было довольно сложно распарсить условие:(
Что за фигня?? Почему постоянно пропадает монитор, вкладка соревнования и т.п.? Просто белый экран.
The interface worked really slow for me. Did it happen to other people too?
During the last hour it worked very slow
Так все-таки, контест будет продлен?
Даже Codeforces меньше тупит!!!!!!!
Что надо было в F сделать?
Рекурсивное решение. Разбиваем множество вершин на 2 равных. Решаем задачу для каждого множества. Затем соединяем каждую веришну из первого множества с каждой вершиной из второго, используя наименьший цвет, который не использовался в раскрассках этих множеств. Когда только 1 вершина ничего не делаем. Получается цветов O(logN).
Там abacaba нужной длины надо вывести в каждой строчке. Вроде как раз это и получается.
берём смотрим на двоичные разложения номеров двух вершин, находим какой-нибудь бит, который в этих разложениях отличается, красим ребро между этими двумя вершинами в соответствующий номеру бита цвет (каждому номеру бита ставим в соответствие свой уникальный цвет). Несожно видеть что а) по каждому цвету будет двудольный граф б) цветов задействовано верхняя целая часть log_2(N). Получаем AC.
Какие-нибудь идеи как решать L? Или хотя бы как понять условие. По словам niyaznigmatul я понял, что там есть что-то еще кроме отсутствия вершин связных с тремя попарно несвязными.
Граф обладает двумя свойствами:
1. Если рассмотреть множество вершин N(v) (соседи вершины v), то граф на этих вершинах связный
2. В графе нет подграфов K1,3.
А как можно было понять первое?
"The news about the success of any contestant passes from any of his acquaintances to all his acquaintances (probably through other people). Two persons do not communicate unless they know each other and when they do, they only discuss people they both know, but not themselves."
Передать данные об успехе товарища x могут только его непосредственные соседи друг другу, так что они должны быть связны.
Я решал так:
1) начинаем с треугольника 2) если можно куда-то вставить вершину в цикл, вставляем 3) если нет, но еще есть вершины, связанные с циклом, то нетрудно видеть, что будут вершины, соединенные с как минимум двумя вершинами цикла, скажем пусть вершина a соединена с v_i и v_j. Тогда заметим, что v_{i-1} и v_{i+1} обязательно соединены, и v_{j-1} и v_{j+1} обязательно соединены. Тогда нам достаточно одного из следующих ребер, чтобы перестроить цикл, включив в него a: v_i-v_{j-1}, v_i-v{j+1}, v_{i-1}-v_j, v{i-1}-v{j+1}, v{i+1}-v{j-1}, v_{i+1}-v_j, так же достаточно, если i+1=j-1 или i-1=j+1. Дальше я просто пытался найти такую тройку a, v_i, v_j, чтобы одно из этих условий было выполнено, и это почему-то всегда получается. Я пытался доказать, что это всегда получится, но не смог :)
Ну я пытался делать что-то такое же. Но без первого условия у меня был контрпример. Надо отметить, что ни мы, ни Angry Maffin этого условия не заметили. И думаю мы такие не одни.
Доказать это не получится. Пример графа:
Если в нём построить цикл 1 2 3 4 5 6 7 8 1 и попытаться описанным способом добавить вершину 9, то это не выйдет. (Именно такой цикл может быть построен последовательным добавлением вершин, смежных с парой соседних по циклу: 2 4 7 2, 2 4 6 7 2, 2 4 6 7 8 2, 2 4 5 6 7 8 2, 2 3 4 5 6 7 8 2, 1 2 3 4 5 6 7 8 1.) Но чтобы получить тест, на котором решение «упадёт», требуется перенумеровать определённым образом вершины. Аналитически это сделать сложно из-за использования HashSet'а. Возможно, такой перенумерации для этого графа и не существует, но идея может использоваться в других примерах.
Все понял, повезло :) А как правильно — чуть докрутить это, или что-то совсем другое?
Да, тесты были не очень качественные, потому что сложно придумывать неправильные решения, когда хорошо знаешь, что делать в более широком классе графов:)
Основа идеи — полная циклическая расширяемость таких графов (при очевидно необходимом условии связности) — правильная. А дальше у меня всё совсем по-другому:) Пусть у нас есть граф G, цикл C и вершина
, смежная с 
. Построим цепь от x до ближайшего из соседей v по циклу (до u), содержащую только вершины из окружения v (такая цепь существует в виду локальной связности). Теперь возьмём на этой цепи ближайшую к u вершину 
. Если y смежна с u (и с v по определению цепи, которой y принадлежит), то всё очевидно. Иначе она не смежна и со вторым соседом v (поскольку u ближе), тогда соседи v смежны, значит, можно «изъять» v из цикла. Теперь, пройдём по цепи от y до u и индуктивно покажем, что либо мы уже умеем расширять цикл, либо верно следующее. (Пусть z текущая вершина цепи, а s — следующая.)
А значит, все вершины цепи от y до z можно изъять из цикла (одновременно).
Если z смежна с соседом t по циклу для s, то мы сможем изъять все вершины цепи от y до z, а также v, смежную с s и «встроить» всю эту конструкцию вместо ребра st. (Если s = u, вершину v не нужно изымать.) Если же z не смежна с соседями s, то соседи s смежны между собой и s также можно «изъять».
Если сосед t вершины s смежен с v, можно изъять всю цепь от y до z, а также вершину v и встроить вместо ребра st. Значит, среди вершин цепи от y до z нету двух соседей по циклу.
Остаётся заметить, что рано или поздно, очередная вершина цепи будет смежна с соседом следующей, поскольку каждая вершина цепи смежна с v — соседом u (конца цепи).
Изложение громоздкое, но идея, надеюсь, прозрачная.
Да, все понятно, круто! Это сильно круче моего решения — я дошел только до выбора y фактически.
Извиняюсь, я криво прочитал условие.
Но в задаче же нет такого условия
Да, спасибо, меня научили правильно читать условие этой задачи.
I'm getting WA in test case 3 on problem I. I'm solving it as vertex cover of a tree (building the trie and considering the empty string is not allowed). I tried testing it with various tests and it 's giving the right answers. Does the idea seem to make sense? Is there some special tricky case?
Try this test case:
That was it, thanks.
это какая-то срань господня, а не ajax, мы просто колоссально много времени в начале контеста не могли открыть страницу с задачами, посылками и проч. — просто белый экран — класс, я так понял, если не особо быстрый инет — хрен контест напишешь
интересно, после такого количества недовольных, администрация что-нибудь изменит?
Расскажите как решать D и K с Минского контеста?
D: 2 раза применить алгоритм описанный здесь: раз для опредиления порядка в котором будут йти лабки в каждой контрольной, и раз в каком порядку будем писать лабки.
стоп, а зачем первый раз? всегда же выгодно упорядочить лабы внутри контрольной по неуменьшению длительности, разве нет?там это в третьем случае и написано...а кто-нибудь может объяснить, что здесь будет являться f(t)? ведь у нас штраф зависит от позиции, на которой будет стоять контрольная работа, не?
Не могли бы вы пояснить: почему недостаточно просто отсортировать по
? (это, наверное, одно применение алгоритма Джонсона).
а у нас w[i] прикрепленно к конкретному p[i], разве не к позиции (i)?
Видимо так. Я только учусь читать, так что это нормально:)
Потому что мы сперва должны сдать 1 предмет полностью, потом другой и т.д.
все таки?
Я все-таки не пониманию, что написано в том комментарии :o)
K. Для маленьких (<100) напишем перебор. Для четных. Решим для (n-8)/2, умножим все на 2, добавим две 4. Для нечетных. Решим для (n-9)/2, умножим все на 2, добавим 3 и 6.
P.S. Это решение от niyaznigmatul. Мы писали такое же но посложнее. Мы для остатков по модулю 6 делали. Для четных так же. Для кратных трем (3n-6)/6 и прибавить 3 и 3. Для остатка 5- потом добавить 2 и 3. А для остатка 1. Решить для (n-55)/6 и добавить (2,4,21,28).
K. Для всех чисел напишем перебор :) Переходы будут двух видов: заменить число 1/n на k чисел 1/(nk), либо заменить число 1/n на 1/(n+1) + 1/(n * (n + 1)). Возможных переходов первого вида довольного много, поэтому будем делать лишь тот, который максимально приближает сумму к заданной.
Это решение работало почти мгновенно для больших n, а для маленьких почему-то несколько ответов не находилось :) Пришлось вписать их руками.
Я сейчас в дорешивании сдал похожее решение. У меня тоже 2 перехода: либо заменить 1/n на 2 числа 1/(2*n) и 1/(2*n), либо заменить число 1/(2*n) на 2 числа 1/(6*n) и 1/(3*n). Только для трех маленьких тестов оно не нашло решения и пришлось запустить перебор, когда n ≤ 55.
А у меня без ручных случаев :) Для <100 напишем перебор. Для больших n вместо ручного кодирования 1/2+1/4+1/4 и 1/2+1/3+1/6, просто пытался брать все разложения из перебора для <100. Не сильно меньше кода, но чуть меньше думать надо :)
Задача D. Вроде никто пока нормально не объяснил.
Пусть у нас есть 2 лабы, и мы сначала сдаем первую (в момент времени t). Тогда мы получим штраф, равный w[1] * t + w[2] * (t + p[1]).
А если мы сдаем сначала вторую, а потом первую, мы получаем штраф w[2] * t + w[1] * (t + p[2]).
Эти два значения отличаются на величину w[2] * p[1] — w[1] * p[2]. Если она меньше нуля, выгоднее первый случай, иначе — второй. Теперь можно посортить все лабы в данном предмете с этим компаратором.
Теперь посмотрим, чем равен штраф в группе из k лаб, если начинали мы так же в момент времени t. Он равен w[1] * t + w[2] * (t + p[1]) + ... + w[k] * (t + p[1] + ... + p[k-1]).
Здесь имеют значение только слагаемые (w[1] + ... + w[k]) * t, т.к. оставшиеся произведения (обозначим их за X для краткости) не зависят от времени сдачи лабы.
Соответственно, если сдавать сначала первую группу лаб, а потом вторую, то штраф будет равен (sum_w1 * t + X1) + (sum_w2 * (t + sum_p1) + X2), а если сначала вторую, а потом первую — то (sum_w2 * t + X2) + (sum_w1 * (t + sum_p2) + X1). Видно, что они отличаются на величину sum_w2 * sum_p1 — sum_w1 * sum_p2. Отсортив группы лаб по этому компаратору, получаем искомое разбиение.
Для закрепления можно решить задачу J вот отсюда, правда, она посложнее в реализации, но идея та же.
Круто объяснил, теперь понял. Мы не успели её додумать, была бы седьмая)
Как решать А?
Рассмотрим строку T = S + S из которой удален последний символ. Тогда все циклические сдвиги — это подстроки длины n = |S| этой строки.
Разобьем наш шаблон на части q1, q2, ..., qk из букв, которые находятся между звездочками. Тогда если мы хотим проверить подстроку [l, r] строки T на то, подходит ли она к шаблону, достаточно чтобы части qi присутствовали между l и r в качестве подпоследовательности, причем между собой не пересекались. Дополнительно накладывается следующее условие: если шаблон не начинается со звездочки, то начало q1 должно быть в позиции l. Аналогично, если шаблон не заканчивается на звездочку, то qk должно заканчиваться в позиции r.
Чтобы это все проверить, достаточно пройти по строке T справа налево и поддерживать динамику f(pos, i) -- самое раннее возможное окончание куска qk, если мы начинаем прикладывать кусок qi к позиции pos или правее. Она довольно просто пересчитывается.
Сложность O(|S|·|Pattern|).
Как решать B?
Тернарным поиском по углу наклона боковой стороны
я знаю человека, который сдал перебор угла наклона с точностью 10^-6
PS. если не знать тернарный поиск, можно было еще бинпоиском по производной
Я знаю одну команду, где просто нашли сами корни производной.
они, случаем, не упоротые? там же бешеная производная
А как, кстати, не упоротые доказывали, что в этой задаче можно делать тернарный поиск?
Мне кажется, что когда написать решение занимает примерно 3 минуты времени, и тестирование идет сразу на всех тестах, доказательство — пустая трата времени
А как предлагается тестировать решение? Штрафные попытки тратить?
Да. Это гембл, безусловно, но чаще всего оправданный. Особенно когда пишешь лично, а не командой
Да. В геометрии обычно либо прокатывает, либо многоугольники и в формуле какие-то min/max/etc.
Ну либо сказать, что функция непрерывная и не особо упоротая, сделать 104 тернарников на маленьких отрезках и выбрать лучшее решение.
На самом деле, тернарный поиск — штука, которую можно сделать немного похожей на бинарный поиск по производной. Во всяком, случае, те две точки(которые обычно выбираются как l + (r - l) / 3 и r - (r - l) / 3) можно выбирать сколько угодно близкими друг другу(это как минимум улучшит время работы в маленькую константу раз), а поскольку от производной для выбора следующего интервала требуется только знак, то этот знак будет совпадать с разностью значений в точках, например r - 0.49(r - l) и l + 0.49(r - l) .
Это дает очень хреновую точность — собственно, если классический тернарный поиск находит с точностью eps, то этот метод будет находить с точностью 50 / 3 eps
Хм, и правда. А я всю жизнь думал, что у этой идеи нет минусов.
Как решается задача D (Western QF) ? Идея посортить хитро строки в порядке уменьшения длины префиксов (отдельно для каждой группы строк, начинающиеся с общего символа) не прошла 22 тест :-(
Суфмассив