Два вопроса:
1) разрешалось ли делать посылки и в yandex.contest, и в еджадж? А то на еджадже посылки из yamndex.contest не показаны.
2) почему нигде в условии Е не определили произведение нуля перестановок?
И как решать A, B, C, F?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.05.2024 17:49:53 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
F — довольно весёлая задача. Во-первых, она, видимо, гуглится, во-вторых, её можно было решить так: посмотрим на первые несколько длин и заметим, что каждая следующая длина — линейная комбинация 72 предыдущих (заметим, конечно, при помощи Гаусса). После этого просто возведение матрицы в степень.
Безотносительно этого решения, интересно было бы узнать что-нибудь доказуемое.
Ну ты махнул конечно, что "заметим при помощи Гаусса". Чтобы понять, что последовательность — линейная рекуррента k-го порядка, нужно знать по меньшей мере 2k - 1 её членов (т. к. нам нужно запустить Гаусса на квадратной матрице, i-я строка которой состоит из чисел ai, ... ai + k - 1). А 72 член, не говоря уже о 143, это очень большое число (72 член — 602929610, а 143, соответственно, должен быть порядка квадрата этого числа).
Возникает вопрос — откуда взять эти 143 члена? Я вот не умею их получать никак, кроме моделирования строки, которым дальше первых 70 членов не убежишь. Я на туре (в Петрозаводске) убил тучу времени на эту задачу, проверил гипотезу о линейной рекурренте вплоть до 30 порядка (Гауссом), не увидел линейной зависимости, пожал плечами, и пошёл думать над другими задачами.
Был весьма раздосадован, узнав, что направление мысли было правильное. Так и не знаю, как бы посчитать первые 143 члена, не вдаваясь в теорию атомарных выражений.
Откуда взять — это на самом деле borderline для правил кубка (спойлер). Ну т.е. скачанная версия oeis может считаться справочным материалом, но учитывая её размер, на принтере её в здравом уме никто печатать не будет. (имхо — давно пора уже разрешить пользоваться всем чем угодно, тогда авторы трижды подумают, прежде чем давать задачи, которые можно найти в википедии)
С другой стороны, пользоваться чем-либо кроме мозга на контестах для действующих участников ACM — плохо (потому что на финале 100мегабайтных "справочных материалов" не будет). Но как решить такую задачу не используя вообще ничего — я не знаю. Интересно узнать, как её решали остальные команды, которые смогли её сдать.
Ну вот нам честность не позволяет пользоваться OEIS во время тура.
Собственно, можно было слегка модифицировать задачу так, чтобы она явно под OEIS не подгонялась. Ну не знаю, например, сказать, что мы два раза называем количество чисел в группе (т. е. "2" -> "222" -> "332" -> "223112" -> "222113221112" -> ...)
Мне вот больше всего было обидно, когда я узнал, что там рекуррента такой огромной степени. Эх, вот если бы природа сложилась так, что там бы была зависимость, скажем, тридцатого порядка, то была бы огонь задача =) А так...
Вообще говоря, если прийти к мысли (достаточно естественной), что эта последовательность состоит из атомарных блоков, которые меняются в соответствии с некоторым количеством правил перехода, то от неё уже можно куда-то плясать, пытаться найти эти атомарные блоки, а из них матричка уже выписывается элементарно. Вроде как, Миша Левин с этим справился за время тура.
В смылсе, честность? В правилах кубка же обтекаемо написано про справочные материалы + отдельно разрешён prewritten code. С такими формулировками всё что скачано до контеста — можно использовать (по крайней мере я это так понял :) ). Ну т.е. я не считаю oeis большой проблемой, вот те, кто гуглят задачи во время тура, — нарушают и букву и дух правил гораздо больше.
Да, если бы модифицировали, — задача имхо стала бы лучше. Любителям гугла и википедии в этом случае тоже было бы сложнее найти статью про Look-and-say sequence.
Если кто-то придумал всё с нуля во время контеста, от идеи про атомарные блоки и до решения, — то это очень круто :) Только на подобный процесс можно полконтеста потратить...
Под честностью в данном контексте подразумевается честность перед собой. Всё-таки мы писали этот контест как регулярный тур петрозаводских сборов, а о том, что это опенкап, мы вот вообще узнали пост-фактум. А на петрозаводских сборах (которые позиционируются как сборы вузов-участников чемпионата мира для подготовки к ACM ICPC) пользоваться интернетом во время контеста — это вообще какой-то моветон. Что толку тренироваться с использованием гугла и OEIS, если на финале ничего подобного нет?
Ну да, тут я полностью согласен, в ПЗ (да и вообще для действующих ACM-команд) пользоваться чем-либо кроме мозга противопоказано (<sarcasm>а то потом на финале по 15 минут дебагают компоненты двусвязности</sarcasm>).
Но всё же задач вроде этой на финале (к счастью?) не бывает.
Michael много времени потратил на втупление на распечатанные первые несколько последовательностей, пытаясь найти паттерны, и потом заметил, что как только у нас появляется последовательность 2111, то после 2 и перед 111 можно разрезать всё на две — там просто идёт цикл длины 4 после этого, не затрагивающий 2. Наше решение было основано только на этом факте.
Sorry the translators can't translate your idea properly. Would it be possible to explain it in english?
The key moment was to notice that once a substring "2111" appears, the part of the string ending with "2" and the part of the string starting with "111" start transforming independently (because the second part never gets 2 as the first character). Then we simply built a graph of strings that don't contain "2111", starting from 2 and applying the look-and-say transformation until a string splits into two (and then continuing building the graph from each of those two). It turns out that this graph has just O(100) vertices.
По второму вопросу — в Петрозаводске на контесте клар приходил. Странно, что к Опенкапу не исправили.
F — авторское решение базируется на том, что Look-and-say sequence можно представить в виде последовательности атомарных выражений, которые при итерировании не сливаются, а только распадаются дальше (см. Conway's cosmological theorem). Записываем переходы между атомами при итерировании в матрицу динамики, дальше возведение в степень.
В — в авторском минкост. Идея — на каждую границу между клетками внутри/на границе матрицы может смотреть не более одной клетки (иначе 2 клетки смотрят друг на друга). К каждой клетке ребро из S пропускной 1, от каждой границы клеток ребро к T пропускной 1, от каждой клетки к каждой из ее границ ребро пропускной 1 и стоимостью, равной числу вращений этой клетки для того, чтобы получить нужное направление. Мы на контесте писали минкост Дейкстрой и это было TL20 — то ли мы где-то налажали, то ли там лучше не писать Дейкстру. С Левитом заходит без проблем.
For F, but even if you know they are composed of atomic sequence, how do you find them? I mean different sources say there are around 92 atomic sequence. How can we find all of them?
B — сводится к mincost потоку: левая доля — клетки, правая — неупорядоченные пары клеток + специальные вершины для смотрящих вне поля. Стоимости определены в соответствии с условий.
Правда, это пришлось упихивать руками и ногами в ТЛ (в итоге пришлось вречную сделать шаги с нулевой длиной пути) — видимо, авторы любят неасимптотические оптимизации.
Есть подозрение, что может зайти какой-нибудь умный жадник.
Утверждается, что любое место вида >< можно "пофксить" за 1 или за 2 [1] и можно жадно проверять, что фиксится за 1, а что не фиксится(тут подробнее не умею)
[1]: В самом деле, пусть нельзя за 1, тогда видим, что это не последний ряд и если добавить ряд снизу, то будет что-то типа
а это можно превратить в
Это понятно, но когда можно за 1 или 2 несколькими способами — какой из вариантов выбирать? Может, там например будут хитрые interactions между горизонтальными и вертикальными. В общем, не очевидно, что это правильно.
Да, я понимаю, что неочевидно, мы сами поток пихали, но я слышал, про сданные такие^ решения в ПТЗ.
Мы сдали такой жадник. Представим все конфликты доминошками. Теперь будем уничтожать такие доминошки, которые можно уничтожить за 1 операцию, при этом не повернув чувака в другую доминошку. То есть условие поворота чувака — он повернется в того, кто в него не смотрит и не в конфликт. Потом можно доказать, что для каждой компоненты связности доминошек мы можем все разрулить, за число доминошек в ней +1.
Не понимаю, как в B можно было придумать mincost, когда там есть куда более очевидное решение. Построим граф. В нём из каждой вершины исходит не более одного ребра. Значит, каждая компонента связности — либо дерево, либо цикл, к каждой вершине которого подвешено дерево. Понятно, что нам нужно избавиться от циклов длины 2. Очевидно, что из двух вершин, смотрящих друг на друга, нужно повернуть только одну. Мы можем повернуть её не более чем тремя способами: чтобы она смотрела за пределы поля, чтобы она смотрела в другую компоненту связности или чтобы она смотрела на одного из своих сыновей. В первых двух случаях новых конфликтов не возникает, в третьем нужно повернуть сына аналогичным способом. Получаем такое решение: запускаем dfs, для каждой вершины считаем минимальную стоимость того, чтобы она смотрела в другую компоненту или за пределы поля, и прибавляем длину пути от корня для неё(весом ребра считаем то, сколько надо заплатить, чтобы родитель посмотрел на сына). Из всех вершин в дереве выбираем вершину с минимальным значением. Потом берём минимум из ответа для каждой из двух вершин лежащих на цикле. По-моему, это самая простая задача контеста.
A:
Будем решать такую задачу: уже есть префикс перестановки p1, .., pk, нужно сказать, сколько можно получить перестановок, чтобы префикс был такой и следующее число было меньше pk + 1. Можно понять, что можно получить каждый возможный оставшийся суффикс без последних 2·b - 1 символов, которые однозначно определяются по числам pk + 1, ..., pn - (2·b - 1) - 1 с условием, что внутри индексов с одинаковым остатком по модулю b можно как угодно переставлять числа. Другими словами, на месте pk + 1, ..., pn - (2·b - 1) - 1 может быть любой набор, который можно получить перекидыванием ещё не использованных чисел находящихся на одинаковых позициях по модулю b. Это можно несложно пересчитывать при условии, что у нас теперь число pk + 1 стало зафиксировано.
UPD: если что-то непонятно, то спрашивайте, попробую пояснить
Как решать D,E,H div2?
Разбиваем все прямые на семейства (по параллельности). Далее, отмечаем на абсциссе всевозможные точки пересечения с этими семействами. Строим граф — (точка на абсциссе, номер семейства). По условию задачи нам теперь надо найти максимальное паросочетание Диницем. Да, у меня WA2, ибо решение отправил за три минуты до конца:(
Зачем Диницем? Обычного Куна для паросоча достаточно...
Довольно "потоковый" контест получился — D и H тоже можно свести к потокам.
По D — разобьем прямые на группы по параллельности. Каждой такой группе дадим фиктивную вершину, и пустим в нее ребро пропускной 1, из нее в каждую прямую группы — ребро пропускной 1. Таким образом мы гарантируем выполнение условия "нету параллельных".
Дальше разобьем прямые на группы по точке пересечения с осью, опять сделаем тот же трюк с фиктивными вершинами — из каждой прямой пустим ребро пропускной 1 в ее фиктивную вершину, из каждой фиктивной в T — ребро с пропускной 1. Так мы выполним второе условие (о различных точках пересечения с осью).
Вся идея немного портится из-за прямой, которая совпадает с координатной осью. Но понятно, что такую прямую есть смысл брать только тогда, когда иных нету — иначе больше ничего взять вообще не получится (остальные либо пересекутся с ней на оси, либо параллельны).
H — рассмотрим квадрат евклидова расстояния. При изменении одной из координат вектора изменение значения этого выражения не зависит от других координат, а в сумме (u-v)^2=u*u+v*v-2*u*v нас интересуют только v*v, потому что все остальное — суммарно по всем слагаемым дает константу независимо от нашего максимального паросочетания. Получаем сведение к минкосту — между работниками и работами ребра как в инпуте, из S в каждого работника одно единичное ребро стоимости, равной пенальти (на сколько изменится сумма штрафа) за первую взятую работу, одно единичное ребро стоимости, равной пенальти за вторую взятую работу, и так далее.
Ту же идею "нам выгодно брать как можно более равномерно" многие команды использовали, чтобы вместо минкоста сдать итеративное решение, которое на каждом шаге ищет паросочетание.
E нужно было решать независимо для каждого цикла. Чтобы получить цикл длины 1 нам требуется ноль перестановок, для цикла длины 2 — одна. Если длина цикла больше, чем 2, то нам требуется две перестановки. Пусть цикл состоит из элементов a1, a2, ..., ak. Тогда первая перестановка меняет местами a1 и ak, a2 и ak - 1 и так далее. Вторая перестановка меняет местами a2 и ak, a3 и ak - 1 и так далее.
Куда слать аппеляцию по E? Тут не вижу кнопки чтобы отправить.
Можете опубликовать апелляцию здесь.
Как верно заметил автор топика, в условии не определено произведение нуля перестановок. Из здравого смысла тоже не получается вывести. Поэтому хотелось бы чтобы перетестировали без тестов, в которых предполагался ответ "0".
Из здравого смысла это как раз-таки очевидно.
Действительно?
По-моему, не совсем логично когда произведение нуля объектов зависит от размера этих объектов (которых ноль, то есть нет).
Ну произведение зависит от того, на каком множестве оно определено.
На числах — получаются числа На перестановках длины k — перестановки длины k. Две перестановки произвольной длины нельзя перемножать.
В птз по этому поводу был клар.
Кажется, это единственная причина что-то предпринимать по этому поводу.
В случае, если Вы определяете произведение одной перестановки, Вы тоже производите некое доопределение. То есть если есть произведение P(K) перестановок a1*...*ak, то его можно представить как P(K-1)*ak; соответственно, из этого выводится свойство произведения одной перестановки: P(2)=a1*a2; P(2)=P(1)*a2 => P(1)=a1; Но тогда шаг для нуля выполняется совершенно аналогично и приводит к ответу с тождественной перестановкой. Как раз любое другое переопределение выглядело бы неестественно.
Другой вопрос, насколько это построение стоит считать очевидным.
Случай произведения одной перестановки был показан в сэмпле.
По-моему о таких вещах лучше чётко писать в условии. К тому же, если в Петрозаводске был клар, значит у нас условие действительно было неполно.
Другой вопрос, почему авторы задачи решили написать в примечании про произведение ненулевого количества перестановок, но не стали писать про нулевое произведение, тем более когда это важно в задаче.
Вы опечатались или я что-то не понял:
чем отличаются "произведение ненулевого количества перестановок" и "нулевое произведение"
Нулевое произведение — произведения нуля перестановок. Произведение ненулевого количества перестановок — произведение перестановок, количество которых отлично от нуля.
Пардон, я идиот, прочитал ненулевого, как нулевого.
Насколько я понимаю математические построения, дело обстоит следующим образом.
В коммутативных группах (здесь и далее мультипликативная форма) можно дать определение произведения конечного множества. Такое произведение из естественных причин разумно доопределить единичным элементом для пустого множества.
В конечных некоммутативных группах можно дать определение произведение элементов конечной последовательности. Опять же, из естественных причин его можно доопределить для последовательности из нуля элементов.
Во всех случаях речь идет о доопределении так, чтобы выполнялись некоторые свойства. Условие задачи указывает определение произведения перестановок, то есть претендует на указание "с нуля" всех необходимых в задаче сведений. Произведение последовательности нулевой длины не следует из этого определения, равно как из определения не следует произведение одного элемента. Сами по себе выражения "представить как произведение нуля сомножителей" и "представить как произведение одного сомножителя" одинаково бессмысленны, между тем пример разложения в произведение одного элемента приведен в пробном тесте.
Из всего вышеперечисленного мне кажется, что условие просто кривое, а следовательно никаких претензий, кроме того, что оно одинаково кривое для всех, к нему быть не может.
Между тем, если в ПТЗ было явное разъяснение, что произведение нуля элементов есть единичная перестановка, а остальные участники не получили такого разъяснения, мне кажется (из принципа "все в равных условиях"), что все сабмиты с момента этого объявления, которые ошибаются в ответе для единичной перестановки, должны быть засчитаны.
deleted, нашел, где написано
Дорешивания еще нет?
Сдал H со стратегией робин гуда, сначала рассовал рандомно, потом от бедных к богатым увел. пути.
В D почему-то зашла жадность брать вершины, у которых меньше всего конфликтов, обновлять граф.
На yandex.contest можно дорешивать сразу после завершения контеста.
У нас такое ва22 по Д. Выложи код
http://pastebin.com/Nrwnhkgi WA 22 вроде от неправильной обработки прямых, параллельных y
Как писать G?
Сначала заметим что все звёздочки можно раскрывать пустой строкой, если раскроем иначе, то ответ не улучшится. А дальше рекурсия. Разобьём выражение на блоки разделенные "|", то что в скобках пока не трогаем. Если получился один блок, то рекурсивно раскроем скобки и вернём то, что получилось. Если блоков два и более, то раскроем их рекурсивно и вернём лексикографически наименьший результат минимальной длины.
Код
Пробовал решать регулярными выражениями, и гдето застреваю (ва12). Напишу алгорифм, а вы подскажите тест для которого он негоден. 1) каждую последовательност из символов Доллар заменяю на два символа — '()'. 2) провожу цикл — NOP до тех пор пока в строке могу провести замен: каждый раз проверяю поочередно, могу ли провести замен из списка заменов, если же могу — тогда провожу этот замен и посли NOP опять проверяю на возможность замены (начиная с первого). Список заменов: 1. Ищу в строке букву, посли которой следует >0 символов Звездочка --> заменяю на пустоту, 2. Ищу в строке последовательность из >=0 букв (перед которой неидет ни буква, ни закр.скобка, ни Звездочка), посли которой следует символ '|', посли которго следует последовательность из >=0 букв (посли которой неидет ни буква, ни откр.скобка) --> заменяю на кратчайшую (и лексикографически наименьшую) из тех двух найденых последовательностей, 3. Ищу в строке откр.скобку, посли которой следует >=0 букв, посли которых следует закр.скобка, посли которой следует >0 символов Звездочка --> заменяю на пустоту, 4. Ищу в строке откр.скобку, посли которой следует >=0 букв, посли которых следует закр.скобка --> заменяю на найденную последовательность из букв. Конец списка. Посли того как никакой из замен осуществить некак, выхожу из цикла и вывожу полученную строку (либо Доллар если она пуста). Код на Perl'e — http://ideone.com/soZ0q3
UPD. ой, извените, все таки выше описан алгорифм — подходит, это в коде была ошибка...(изправленный и даже очевидно подходит под описание — http://ideone.com/auIcKH )
What about Div 1 C?