Сегодня в 20:00 по Москве состоится TCO 2013 Algorithm Round 2B. Участвовать могут те, кто прошёл по результатам предшествовавших Round 1 и не прошёл в следующий раунд по результатам Round 2A. Регистрация началась. Первые 50 мест из этого раунда проходят дальше в Round 3.
Впоследствии будет проведен ещё Round 2C по таким же правилам. В параллельных им раундах с такими же задачами смогут участвовать и те, кто уже прошёл в Round 3. Первые 350 мест с наивысшим результатом в общем зачёте по Round 2 получат футболки TopCoder Open (общий результат участника здесь определяется как наилучшее место среди всех тех Round 2A, Round 2B и Round 2C, где участник набрал более нуля очков).
Всем удачи!
Я никогда не пробовал, а в таких раундах участие вне конкурса бывает?
Все, кто уже отобрался, могут поучаствовать в параллельном рейтинговом рауде. Причем, рейтинг рассчитывается раздельно по соревнованиям.
А если мне нет 18, я не отбирался и не регистрировался на TCO? Я в нем могу участвовать?
Нет, уверен. Просто, для тех, кто уже прошел, устраивается паралельное соревнование, чтобы не скучали во время основного :).
Печально :-( Понял, спасибо!
Пару часов назад пребывал в состоянии "понимаю, что чего-то не понимаю", когда безрезультатно пытался зарегистрироваться на предстоящий раунд. Раунд — важный и ответственный, так что пытался и пытался. На мои тщетные попытки апплет реагировал сообщением вроде "Registration is available only by invitations". Каково же было мое удивление, когда я обнаружил себя на 50-м месте в Раунде 2A (и, следовательно, прошедшим в следующий). Удалили читеров?
Так что теперь с интересом жду окончания раунда — Edvard и NALP сидят неподалеку в Центре олимпиадной подготовки и напряженно думают.
На чем так массово попадала 500? Я совершенно не ожидал, что подпрыгну со 111 места до 45.
У меня, по-видимому, TL. Непонятно как.
А, нет, ML. Ненавижу этот TopCoder с его ML в 64 метра.
Куча народу понаписала какое-то палево за 250 (которое ещё и непонятно, как челленджить), вот и попадала.
Мне кажется можно завалить так: a и b образуют рандомные перестановки, c переводит каждый элемент в одно и то же подмножество размером 25. Я правда не успел попробовать :)
По-моему, быстро найдется цикл... У нас же "одно и то же подмножество размера 25".
Да, согласен. Тогда так: в a из 0 переход в подмножество [1,50) размером 25, b и c — рандомные перестановки [1,50).
Я заслал бредятину — динамику за k*(n^4), проверяющую наличие пути длиной k в новом графе (вершины которого — пары вершин из старого).
Понятно, что максимальный по длине путь без наличия цикла — это что-то порядка n^2, т.е. около 2500, но у меня это не лезло в ТЛ, поэтому послал с k=200))) Мне не удалось придумать пример, на котором получились бы более длинные пути.
Вероятно, автору задачи это удалось))))
Можно было просто найти длиннейший путь в новом графе, перебирая вершины в порядке топологической сортировки. А если есть цикл — ответ -1.
Как решать Hard?
Я делал так:
Зажимаем все единицы в прямоугольник w x h (чтобы на каждой стороне была хотя бы одна единица). Затем разбираю случаи (1 <= w <= sx) и (sx < w <= X) и то же самое c Y. Внутри каждого случая формула включения-исключения (на каждой стороне должны быть хотя бы одна единица).
500 решалась поиском циклов в графе на парах из двух вершин с ребрами (u,v) -> (p,q) если можно как-то пойти u->p v->q или u->q v->p, потом топсортом и нахождением длиннейщего пути?
Еще надо было рассматривать переход u->p, u->q (тест 4).
точно, спасибо
Нет, если можно пойти (u или v)->p и (u или v)->q. Это разные вещи.
Кто умеет челленджить "ленивый перебор по состоянию 2^{50}"?
Ну, теперь то можно просто посмотреть тест
Но не генератор)
А, ну я придумал. Разобьем числа с 1 по 49 на много перестановок с взаимопростыми размерами (это второй вид транспорта). Первый же будет из нуля вести в по одному представителю от каждой перестановки. Тогда мы сначала пойдем 1, а потом будем ходить 2 очень долго (при этом снова пробуя один, но по один ходов нету)
Казалось бы, LCM не получится достаточно большим.
Да, проблема
Почему такое решение по easy правильно?
Оно неправильно, я такое почелленжил. Тест: 2 2 4. Ответ — 0.
Неправильно, когда
if (a == b && b == c). А с сравнением gcd правильно. Мне тоже непонятно, почему.Да ну? ab=ac=bc=2 в этом тесте => оно выведет вполне себе правильный ответ — 0.
Я так понимаю, спутано с
. Я слышал про зачалленджнутые решения такого типа.
Ну, почему при равном общем НОД надо делить на 3, примерно понятно. Рассмотрим сначала случай для 2-х чисел. Почти очевидно, наилучшим будет расстояние НОД/2 (если неочевидно, то примерно можно так доказать: пусть две последовательности начинаются в одной точке. Тогда, найдется такой "отрезок", что расстояние между деревьями разных видов по краям отрезка будет равно точно НОДу (т.к. ДУ kx + ly = gcd(x,y) имеет решение), а остальные, очевидно, будут не меньше НОДа. При смещении одной из последовательностей куда-либо, с одной стороны, будет увеличиваться расстояние между "нулями", с другой, будет уменьшаться расстояние между вот теми точками, расстояние между которыми ровно НОД, и максимум расстояний будет достигнут, соответственно, при смещении на НОД/2)). С 3-мя последовательностями аналогично. А вот над неравными НОДами я еще думаю сейчас; на контесте придумал что-то подобное, но не смог полностью доказать и, в конечном итоге, писал стандартный перебор) Ну, в принципе, понятно, что т.к. для 2-х опт решение НОД / 2, то для 3-х верхней границей будет минимальный НОД, делённый на 2, но как при этом "упихать" туда 3-ю последовательность, я пока не знаю.
Ну случаи с двумя и равными понятно. Не понятен основной случай.
Screencast
Таблица с рангами на майку. Будет обновляться. Взяты с каждого раунда лучшие 349-350.
А может кто-нибудь рассказать решения по 250 и 500? Из обсуждений выше ничего не понятно.
250.
Заметим, что наименьшее расстояние между деревьями двух типов равняется min((pos1 — pos2) mod gcd(perod1, period2), (pos2 — pos1) mod gcd(period1, period2)). Зафиксируем начальную позицию деревьев первого типа в нуле, переберем начальные позиции двух других типов, вычисляя на каждой итерации попарные расстояния. Итого получим решение за 2000^2.
500.
Начну с тупого решения. Пусть состояние игры — маска позиций, в которых может находиться первый игрок. Очевидно, что проигрышные состояния — это те состояния, маска которых содержит ровно 1 бит, либо с которых нет никаких переходов. Очевидно, что начальное состояние — все биты единичные. Если из начального состояния можно дойти до какого-либо цикла, то ответ -1, иначе — длина длиннейшего пути до проигрышного состояния.
Чтобы получить полиномиальное решение, следует заметить, что мы можем сократить количество состояний с 2^N до N^2, используя в качестве состояний пары вершин. Идея доказательства: если между какими-либо масками существовал путь длины K, то между парами, являющимися подмножествами наших масок, тоже будет существовать путь длины K (и наоборот). Нужно помнить, что из некоторых состояний, из которых не существует ребра в нашем уменьшенном графе, в исходном графе ребро таки существовало (и вело в проигрышное состояние), а из некоторых — нет (они сами по себе были проигрышными) — это нужно учесть при нахождении длиннейшего пути.
P.S. Исходники моих решений тут.
А почему второе расстояние достаточно перебирать до 2000? Кажется первое расстояние Δ b нужно перебирать до a, а второе Δ c до lcm(a, b).
Кажется, таки до lcm попарных gcd-шек. Я сейчас слишком сонный, чтобы доказать, почему он небольшой.
Перебираются же некоторые точки которые, которые будут формировать киви и грейпфрут, при этом если мы сказали, что яблоки имеют вид 0 + a*k, тогда Δ b лежит [0;b), а Δ c — [0;c)
Я ниже написал, что именно мне не понятно.
Да нет, hydrastuff все верно говорит. Мы же не перебираем Δb до a: Поскольку все циклично, тогда для всех пар целых чисел (i, j): ai = aj (mod a) = Δa. Где ai = Δa + i * a. То же самое верно и для b и c. Следовательно достаточно перебрать Δb в отрезке [0;b) и Δc в отрезке [0;c).
Если положение первого дерева мы фиксируем в нуле, то вариантов положения второго можно рассматривать b, а вариантов третьего — c, так как для каждого вида мы просто выбираем остаток от деления ВСЕХ позиций данного вида на соответствующий период.
Да но для подсчета ответа нам важен остаток третьего не только по модулю первого, но и по модулю второго. А таких пар остатков вроде lcm.
Ну, лично я делал так: пусть a — наибольший из интервалов. Зафиксируем одно из деревьев а в нуле. Тогда как минимум одно из деревьев k растет на [0, a-1], и как минимум одно из g растет на том же интервале. Всё, пара этих двух позиций полностью описывает нашу ситуацию. Более того, легко понять, что позицию дерева k имеет смысл перебирать от 1 до k, а позицию дерева g — от 1 до g, т.к. если у нас есть дерево вида g в позиции g + l, то дерево есть и в позиции l, очевидно. Насчет того, о чем вы говорите — остаток третьего по модулю второго — у нас есть смещение 2-го и 3-го относительно 1-го, из них двух мы можем получить смещение 2-го относительно 3-го.