4 августа стартовала традиционная летняя серия индивидуальных соревнований SnarkNews Summer Series-2014. Соревнования проводятся на системе Яндекс.Контест, также доступна страница проекта на Яндекс.Контест. Опубликовано расписание серии.
Участвовать в серии могут все, кто имеет логин на Яндексе. Соответственно, для регистрации нужно зарегистрироваться на Яндексе и войти хотя бы в один из раундов серии. логин и пароль от почты и являются логином и паролем на вход в систему Яндекс.Контест.
чуть-чуть по-раньше бы об этом узнать.
Самое логичное время для объявления — за пол-часа до конца первого раунда.
Мне почему-то показалось, что некоторые участники начали решать после окончания. Или я как-то неправильно понял обозначения в таблице, и если в участника в 15:30 под никнеймом пишет 1:10, то он начал не в 14:20:) Или в часовых поясах запутался, не знаю...
По задачах: какая оптимальная асимптотика в D? Наивная динамика за N^4 проходит со временем 0.1 или даже быстрее. Если переписать ее в другую сторону и прикрутить частичные суммы, то вроде бы получим решение за N^3. Можно ли еще быстрее? И можно ли решить С за чистый квадрат? У некоторых, говорят, квадрат на логарифм получал TL.
Если считать, что int'ы можно сортировать за линию, то С можно решать за квадрат:)
А если у нас квантовый компьютер, то все вообще круто)
Если длины отрезков уже отсортированы, то каждый раз при просмотре новой группы отрезков нам нужно уметь брать максимум по всем предыдущим ребрам вершины, можно эти максимумы хранить отдельно, это понятно) Я думал — вдруг надо как-то вообще с другой стороны к задаче подойти.
Еще я понял, что все же не умею решать D за куб:)
У меня решение в D за O(N^3*K) — это, по-твоему, куб или 4 степень? Интересно, зачем такое маленькое К в задаче?
Как решать с такой асимптотикой?
У меня динамика какой отрезок нужно решить — сколько шариков тащим с префикса и какой у них цвет, и внутри я перебираю, какую часть отрезка порешать независимо от префикса — а к другой части "протаскиваю" то, что осталось от префикса. Получается вообще N^3*K*C, где С — число различных цветов.
Динамика — сколько стоит удалить отрезок, если к нему слева добавить еще Х (X < K) шариков такого же цвета, как и первый шар. Пересчет — смотрим, как в конце концов удалится первый шар. Либо его удалим первым ходом, либо вместе с каким-то шаром такого же цвета из отрезка (переберем его). Во втором случае нам точно нужно вначале удалить все шары, которые между этими двумя, а потом переходим к задаче для меньшего отрезка, когда есть (Х + 1) шар такого же цвета, как шар в начале отрезка.
Как решать С? Опишите пожалуйста)
Состояние можно однозначно определить последней парой вершин, которые мы посетили. Одна из них определяет, откуда мы можем ходить, другая — какое у нас сейчас ограничение на длину хода. Отсюда получаем очевидное решение за N^3 — отсортировать все отрезки по длине, решать от более длинных к более коротким, для каждого отрезка перебирать всех валидных соседей, с которых мы могли на него перейти.
Чтобы получить из этого N^2*log(N), вместо перебора предыдущих отрезков по одному, будем вытаскивать каким-нибудь Фенвиком максимум среди всех вариантов, у которых длина не меньше необходимой. Если заметить, что нас каждый раз интересует максимум среди всех рассмотренных соседей, за исключением соседей с такой же длиной, то можно вместо Фенвика банально хранить максимум для каждой из точек. Только тогда нужно добавлять отрезки группами (сначала добавляем все отрезки одной длины, потом обновляем максимумы), чтобы не получилось пары соседних переходов с одинаковой длиной — например, (0,0)->(1,0)->(2,0).
Я еще это не писал, но кажется, что это верно. Если мы можем пройти с одной точки в другую, то проведем ребро между ними (ориентированное). Найдем все компоненты сильной связности. Теперь у нас есть ациклический ориентированный граф. В таком графе можно искать путь максимальной длины за проход ДП-шкой. Вроде все :)
Проще: посортируем ребра по уменьшению длины + ДП-шка.
А когда нельзя из точки пройти в другую?
Если dist(0,0,A.x,A.y) <= dist(A.x,A.y,B.x,B.y), тогда нельзя пройти с точки А в B. Вроде так.
Следующий ход можно сделать только если dist(B, C) < dist(A, B). Кажется, ты не так понял условие.
Да, сорри :) Нужно думать новое решение.
У тебя "точка" — это точка из входных данных, или пара точек? В первом случае нельзя определить, можно ли сделать ход (мы не знаем, какая была длина последнего перехода), во втором — в графе динамики будет N^4 ребер.
Почему для того, чтобы посмотреть результаты, надо стартовать виртуальный контест и ждать 1 час 20 минут?
Проверьте, ссылка на результаты есть на snss2014.snarknews.info
Ну я же не совсем дурак, естественно, я вбивал эту ссылку, но меня перебрасывало на главную и предлагало стартовать виртуальный контест. А сейчас я стартовал контест и, естественно, вижу по этой ссылке текущие результаты.
Как получить доступ к английским условиям? На сайте написано, что условия есть и на анлгийском, но если в правом-верхнем углу поменять флажок, то меняется язык интерфейса, а условия те же.
А как B решалась?
Я делал так. Пусть расстановка тарифов существует, обозначим di кратчайшее расстояние от истока до i'ой вершины. Заметим, что для любой дуги uv верно dv ≤ du + 2 и dv ≥ du + 1. Заметим, что эти условия на di — ещё и достаточные (при условии, что di — целые). Преобразовав второе условие в du ≤ dv - 1, получаем линейную программу для кратчайших путей следующего графа: в исходном графе каждой дуге делаем стоимость 2 и добавляем обратную дугу веса -1.
Осталось поискать в полученном графе отрицательный цикл (или, если его нет, кратчайшие расстояния от истока). Ограничения несколько страшные для Форда-Беллмана, но он, как ни странно, заходит. Возможно, для графа такой специальной структуры можно и без ФБ сделать.
nvm
Чего-то никто не спрашивает про задачи с новых раундов... Как решается с третьего раунда задача F?
Согласно условию, необходимо найти ближайшее к Е число Х, которое дает указанные остатки по модулям 1, 2,..., n. Найдем значение этого числа Х по модулю LCM(1,...n)=T; пускай это значение Q. Далее среди всех чисел вида pT+Q выберем лучшее — достаточно рассмотреть только соседей Е с каждой стороны.
Чтобы найти Q, можно использовать какой-нибудь алгоритм Гарнера, но ограничения позволяют писать почти любые переборы:)
Обидно профукать победу в раунде, написав if (ans==0)ans+=res; вместо if (ans==0)ans+=rl;
У меня вопрос по В из раунда 2 — какой там максимально возможный ответ? У меня получилось что-то далеко за пределами 64битного типа, но я не подумал о int128, длинку писать тоже не стал, а отправил в открытую с обычными long long. Тесты убогие?:) Я сейчас в очередной раз перечитал условие, никаких ограничений вида гарантируется, что ответ... не нашел.
Как решать D со второго раунда?
Заметим, что хотя бы один квадрат будет содержать одну из следующих пар точек: (самая нижняя левая, самая левая нижняя), (самая нижняя правая, самая правая нижняя), (самая правая верхняя, самая верхняя правая), (самая левая верхняя, самая верхняя левая). Решим для первого случая, а остальные сводятся к нему путем отражения всех точек относительно вертикальной и/или горизонтальной оси.
Мы решили, что один квадрат будет содержать самую нижнюю левую и левую нижнюю точки, значит мы однозначно можем определить позицию его левого нижнего угла. Для удобства перенесем эту позицию в начало координат. Теперь, если сторона этого квадрата будет равна S, то в него попадут все точки, у которых max(x, y) <= S. Отсортируем точки по max(x, y) и будем перебирать их по убыванию этой величины. Пусть мы рассматриваем какую-то точку, тогда все, которые идут в порядке сортировки раньше нее, точно попадут в квадрат, при условии что текущая точка лежит на его стороне. Следовательно, нам нужно найти наименьший квадрат, который покрывает остальные точки, после чего попробовать обновить ответ. Ну а этот второй квадрат ищется просто: его сторона равна max(X_max — X_min, Y_max — Y_min), где X_min — наименьшая X координата точки, которая не попала в наш квадрат (т.е. лежит в порядке сортировки после текущей точки), и т.д. Ясно, что поскольку мы перебираем точки по убыванию max(X, Y), то как только мы рассмотрели какую-то точку, мы можем обновить X_min, X_max, Y_min, Y_max при помощи ее координат, т.е. по сути мы будем на ходу поддерживать эти величины и за О(1) находить площадь наименьшего квадрата, в который попали все "остальные" точки. Сложность O(NlogN).
А как присуждаются баллы, когда место делится? В лексикографическом порядке по хэндлу?
Там же скорее всего с точностью до секунды считается (и судя по таблице, округляется round'ом: у вас 0:58 + 0:08 — D = 56, у azizkhan.almakhan — 0:58 + 0:07 — D = 56).
Ага, ясно.
как решать c и f из последнего раунда ?
F — если мы зафиксируем длины строк из ответа, то можно проверить, что такие длины могут быть за O(|T|) хешами. Чтобы понять, какие длины x, y нам подходят, решим уравнение ax + by = |H| в целых числах; решений, где x, y ≥ 0 приблизительно
, то есть их можно просто все перебрать, и работать все будет за 
.
Точнее, решений не
, а 
, но время работы такое же получается.