Странно, что никто ещё не написал об этом.
Сегодня проходит (уже заканчивается) заключительный этап Opencup сезона XI (Весна 2012). После окончания предлагаю обсудить задачи здесь.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.04.2024 14:58:43 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
какое ограничение на размер посылаемого файла стоит на сервере?
64 KiB : http://opencup.ru/index.cgi?data=ocb/rules/gp&menu=index&head=index&class=ocb&ncup=ocb, пункт 5.2.4
Расскажите, пожалуйста, как решать С и D.
C: Построим явно перестановку. Легко за O(n) найти ее порядок[upd:судя по всему порядком называется нечто другое.](просто ищем все циклы, вершины, которые входят в какой-то цикл повторно не обрабатываем.
Помогло добавление if(n<k) return 1;
Можно подробнее, а то совсем непонятно про циклы и прочее...
Нашли перестановку p(n) ищем такое минимальное k, что p(p(...p(n)..) (k раз) = id.
Для этого для каждого числа находим такое K и берем НОК по всем. Пока что это o(n^2) на тест. Заметим теперь, что если для x данный ответ k, то для p(x) p(p(x)) итд тоже, поэтому теперь можем искать за О(n) на тест
Классика же
понятно, что если карта стоит на каком-то месте, то рано или поздно она на него вернется, найдем сколько действий нужно для этого за О(n) (просто промоделируя ее положение после очередного действия), так для каждой карты и среди всех этих величин НОК — это будет за О(n*n) (всего n карт, для каждой моделируем за О(n))...
теперь поймем, что если карта стояла на месте i и переходит в позицию p[i], то для позиции p[i] количество действий нужное для ее возврата в позицию p[i] равно количеству действий для i. аналогично для p[p[i]], p[p[p[i]]]...
т.о. найдем длины всех циклов, найдем их НОК — это и есть ответ
Порядком элемента называется такое минимально k что элемент в этой степени тождетвенный, так что именно это =)
ну я сперва так счтиал, а потом меня смутило определение на википедии, поэтому исправил, все равно ниже формально определил, что хочу
Можете объяснить, почему этот код (задача С) получает RE 2?
http://pastebin.com/p2mnPxHp
У меня тоже RE2 было на контесте, переписал на BigInteger(java) и зашло.
gcd стек не переполняет, особенно такой)
Да, вы правы, просто тоже был RE2 и не внимательно посмотрел код, решив, что gcd тоже рекурсивная)
А можешь свой код показать?
Эту задачу я писал...
http://pastebin.com/FnzYL7h0
Потому что надо писать не
a*b/gcd(a,b), аa/gcd(a,b)*bНу я так и пишу, тем не менее :)
Это я к посту про BigInteger, почти уверен что ошибка была в этом
Интересный факт: если строку 61 заменить на while (x != i) получается TL 2.
D: Изначально мы знаем, что самый нижний диск нужно положить на стержень B и только. Идем с конца строки (то есть по уменьшению размера дисков) и смотрим куда нам нужно положить этот диск(i, индексация с нуля):
1) Если у нас диск сразу лежит в нужном месте, то логично, что меньший диск (i — 1) нужно кинуть на него и сумма не меняется;
2) Иначе мы прибавляем к сумме перекладывание, которое будет необходимо для того, чтобы переложить этот диск на нужный стержень + количество, которое нужно для перекладывания всех меньших дисков с оставшегося стержня (считаем, что все они уже там). Это будет (1 + (2^i — 1)), то есть 2^i. Теперь мы знаем что (i — 1) диск должен лежать на оставшемся стержне (Например: перекладываем с А на В — меньший лежит на С).
Ну и идем так до начала строки, каждый раз решая похожую задачу для меньшего количества дисков. Разница лишь в том, что меняется стержень, на который надо кидать. Как-то так :)
Как решать J? Никогда бы не подумал, что такое решается, да еще и не очень адово.
Строим convex-hull за квадрат: берём какое-то ребро выпуклой оболочки (как его найти — отдельный вопрос), ищем 2 грани этого ребра (за проход по всем точкам), для рёбер граней повторяем то же самое.
Я умею инкрементально строить: начинаем с трёх точек, когда добавляем точку, находим, какие грани будут удалены, какие добавлены, и перестраиваем. Не знаю, насколько это адово, но подебагать пришлось.
Совсем не адово. Вот код. Я такое на контесте раза 4 писала, идея как у eatmore.
Мне куда интереснее, как можно за разумное время написать H. J писал первый раз выпуклую оболочку 3D, но достаточно просто вышло.
В H я может быть что-то не так понял, но вроде ничего сложного: сделали для каждого круга события, когда он появился в поле зрения и когда исчез (если этот отрезок углов пересекает ноль, разбиваем его на два), посортили события, прошли. Совсем мало кода. Только WA 2.
Всё правильно. WA2 может получиться, если считать, что длина каждого отрезка меньше половины окружности (а это не так). Ещё один особый случай — когда красный круг касается оранжевого.
А чем выделен случай касания?
Тем, что некоторые алгоритмы поиска общих касательных могут неправильно работать в этом случае. Как и способы определения того, какое из пересечений этих касательных с внешней окружностью будет началом отрезка, о какое — концом.
Ой. Мы все трое что ли неправильно поняли условие? Бывает же такое. Из английской версии, сложилось ощущение, что надо считать отношение площадей. Так да. Задача значительно проще.
Circumference — окружность.
В русской это значительно лучше прописано. Но и отсюда понимается однозначно. Чисто наш косяк. Даже не спорю.
Как решать I?
(вроде) Свел к тому, что нужно уметь находить 1 любую расстановку, если она есть. Дальше не получилосьПерестановку Куном найти можно же. А как свести к тому что ты написал?
лажа
Построим граф исток -k- первая доля -матрица- вторая доля -k- сток, k бинпоиском
Если в нем нет полного потока, то, очевидно, задача неразрешима.
Если в нем есть полный поток, то по лемме Холла из него можно восстановить ответ, найдя паросочетания k раз.
а как решалось К?
Будем восстанавливать ответ слева направо.
Ясно, что если у набора зафиксировано первых i символов, а последним стоит символ с номером j, то количество наборов длины n с таким префиксом равно C(n — i, m — j).
Будем пытаться поставить на i-ую позицию символ j. Если количество наборов с таким префиксом меньше K, то вычитаем это количество из K и переходим к следующему символу. Иначе ставим данный символ на i-ую позицию и переходим к позиции i+1.
спасибо конечно за ответ, но нечего непонял
Могу привести пример, может с ним будет понятнее:
N = 5, M = 3, I = 8
1) Пытаемся поставить на 1 место '0'. Количество наборов вида 0.. равно C(5 — 1, 3 — 1) = С(4, 2) = 6, что меньше I -> I = 8 — 6 = 2
2) Пытаемся поставить на 1 место '1'. Количество наборов вида 1.. равно С(5 — 2, 3 — 1) = C(3, 2) = 3, что больше I -> на 1 месте стоит '1'.
3) Пытаемся поставить на 2 место '2'. Количество наборов вида 12. равно C(5 — 3, 3 — 2) = C(2, 1) = 2, что равно I -> на 2 месте стоит '2'.
4) Пытаемся поставить на 3 место '3'. Количество наборов вида 123 равно C(5 — 4, 3 — 3) = C(1, 0) = 1, что меньше I -> I = 2 — 1 = 1
5) Пытаемся поставить на 3 место '4'. Количество наборов вида 124 равно C(5 — 5, 3 — 3) = C(0, 0) = 1, что равно I -> на 3 месте стотт '4'.
Таким образом наш ответ — '124'
а в В считаем динамику d[i] — покрыть первые i точек, поддерживаем выпуклую оболочку (x[i], d[i — 1] + x[i] * x[i]) и в ней указателем лучшее разбиение находим?
Типа того. Обновление оболочки — выкинуть несколько последних вершин и добавить новую. Поиск ответа — бин. поиском.
У нас зашло что-то совершенно левое. Поддерживаем ту самую динамику, а пересчёт делаем за большую константу, перебирая только некоторые точки, найденные из кучи эвристических соображений.
В A — стратегия: на каждом шаге строим как можно больше рабочих, на все остальные деньги строим заводы. Если нужны солдаты, то вначале пытаемся делать их вместо рабочих на текущем шаге, если не хватило — то на предыдущем, если всё равно не хватило — fail.
Кстати, а эта стратегия доказуема? Мы это засылали не доказывая, в надежде на вселенский рандом.
Утверждение. Делать солдата более чем за один день до боя не выгодно. Потому что если вместо него сделать в первый день работника, во второй день на заработанный им рубль построить фабрику, то начиная с третьего дня на этой фабрике на рубли, заработанные работником, можно будет делать солдата каждый день.
Поэтому солдата делаем либо за день до боя, либо в день боя, причем показывается, что в день боя выгоднее. Если у нас фиксированное количество солдат, которых мы делаем в текущий день, то жадность в распределении остальных денег очевидно правильна.
У меня решение без отката назад. Рассматриваем текущий день. Если нам нужны солдаты, чтобы воевать сегодня — делаем их, не можем — fail. Возможно, нужно делать солдат, чтобы воевать завтра. Посмотрим, сможем ли мы их всех сделать завтра. А именно, по текущему дню однозначно определяется, сколько фабрик у нас будет завтра (+количество работников минус количество фабрик). Если этих фабрик хватит, чтобы сделать всех необходимых солдат завтра — не делаем сегодня. Про послезавтра не задумываемся в силу утверждения. Иначе определяем, сколько сделать сегодня.
Не совсем детальное доказательство, конечно, но мне хватило, чтобы считать решение полностью доказанным :)
а какое ограничение на m в задаче G?
Статического массива на 221 хватило. По идее, там нет кратных ребер. То есть, в худшем случае, не более N(N — 1) ребер (не стал делить на 2, ведь каждое ребро может быть одного из двух цветов).
По-моему, там было написано, что каждое ребро не более 1 раза.
А у меня одного был ступор в B и мысль, что требуемое решение должно работать за O(n) ?
Да.
кто-нибдудь может объяснить, почему в С не получается большой ответ, вылазящий за
long long?гарантируется условием.
где это гарантируется?
В последней строке Output'а: All possible inputs yield answers which will fit in a signed 64-bit integer.
К сожалению, в русской версии условия это предложение любезно опустили.
Вот и какие условия лучше читать? бывали случаи, что и в одной версии условия опускали что-то... и в другой =(
Лучше всегда на языке оригинала. Кэп подсказывает, что для задач Гран-При Америки язык оригинала — не русский ;)
А вот мы читали условия на языке оригинала и по фразе "Output this number with 4 decimal places of accuracy" в задаче J сделали вывод, что достаточно выводить правильно первые четыре цифры числа (чтобы относительная погрешность не превышала 10 - 4). Мы выводили даже 6 цифр, и наше решение не прошло по точности, хотя при изменении формата вывода проходит. Оказывается, что русский перевод "выведите с точностью 10 - 4" больше соответствует чекеру :)
Первые три нагуглившиеся ссылки (1, 2, 3) говорят о том, что так по-английски всё-таки называются знаки после запятой, а не значащие цифры.
Скорее уж условие на русском ("с точностью 10 - 4") можно понять неправильно: абсолютная или относительная погрешность имеется в виду?
Ну и, конечно, не очень хорошо, что это не следует из примера.
В третьей ссылке приводится разница между accuracy и precision. Там есть примеры.
Да, пример явно указывал на то, что выводить ровно 4 знака после точки необязательно)
Просто обидно получается, что не сдали задачу из-за неправильной интерпретация английской фразы. Причем решение получает ответ с требуемой точностью, только выводит в неправильном формате.
Опс, а я не дочитал до этого места, только первую страницу посмотрел. То есть decimal places (авторское понимание) конфликтует с accuracy (ваше понимание), вместо accuracy в правильной фразе должно быть precision или пусто, так?
Согласно примерам, accuracy измеряется в significant digits, а precision — в decimal places. В условии задачи шла речь об accuracy в decimal places. Поэтому мне честно непонятно, что имели в виду авторы. Почитав документ 3, больше склоняюсь к тому, что они имели в виду accuracy (т.е. относительную погрешность, как и мы).
Ну авторы-то имели в виду то, что написали у себя в чекере. Но вот в условии они, похоже, сформулировали это не идеально.
Ответ Gassa: да, если по условию требовались именно 4 знака после десятичной точки, то вместо accuracy должно было быть precision. Это бы исключило двоякое понимание. По крайней мере, у людей, разбирающихся в данном вопросе. Хотя все равно хотелось бы более доходчивого объяснения в условии (например, фразы типа "после десятичной точки" или "отличающийся от правильного не более чем на 10 - 4") для чайников.
Кроме того, если бы в системе стоял стандартный чекер (rcmp4), проверяющий, что абсолютная или относительная погрешность не превосходят 10 - 4, то решение, выводящее шесть знаков в сумме, прошло бы, потому что в этом случае относительная погрешность была бы меньше. Я скачал тесты с сайта американского полуфинала и проверил. Значит, в системе какой-то другой чекер для вещественных чисел.
Потому что авторы специально составили тесты так, чтобы ответ не вылезал за
long long. И написали об этом в условии.А как решать E и G? Выгодно ли в Е присваивать некоторому подмассиву значение его медианы?
В E вроде баянистый факт, что всегда надо брать медиану для подмассива — посчитаем f[i][j] — значение при b[i] = b[i + 1] = b[i + 2] = ... b[j] = медиане подмассива [i..j]
и dp[K][N] — на сколько уже блоков разбили, конец последнего блока. переход: перебираем конец следующего блока
надо только быстро считать f[i][j]
В G: обозначим B — ребра весом 1, R — ребра весом 0, построим минимальный остов, если его стоимость больше, чем k, ответ 0, иначе попытаемся заменить каждое красное ребро на какое-то синие, чтобы граф оставался связным (эту жадность нетрудно доказать)
Чем легче всего быстро считать f[i][j]? Декартовым деревом?
Эта медиана — всегда одно из a[i]. Посортим все a[i], оставим только уникальные, и для каждого подотрезка [L..R] запустим тернарник.
более того, это вроде средний элемент в массиве.
а за сколько это будет? за N^2 все отрезки, еще за NlogN сортировка, нет?
или я что-то не понял?
Сортировка один раз в самом начале.
То, что в первой правке, вроде бы необязательно...
Да, тернарник найдет средний элемент в массиве, но я не придумал как его считать по-другому.
ааа... все понятно.
Медиану можно искать без тернарного. Есть баянистая задача: запросы двух типов — добавить число в массив и вывести медиану. Можно завести два мультисета, в каждом из которых будем хранить половину массива, причем все числа в одном сете не больше, чем числа в другом. Добавляем элемент в нужный сет, чтобы не испортить условие на содержимое сетов. Если размеры сетов после добавления стали отличаться больше, чем на 1, перекинем одно число из сета в сет.
можно и им, можно вроде еще мутить следующую вещь: переберем начало — i, для суффикса [i..n] посчитаем втупую (отсортируем суффикс и возьмем средний).
теперь заведем двусвязный список по отсорченному массиву и дерево фенвика (или дерево отрезков) для суммы, изначально в дереве фенвика все значения = 1, означает что этот элемент есть в нашем двусвязном списке.
теперь удаляем элемент j (изначально j = n), переходим к отрезку [i..j-1], поддерживаем для каждого отрезка медиану, при переходе к следующему отрезку медиана может сдвинуться на 1 влево или вправо, дерево фенвика нужно для того, чтобы узнавать сколько элементов на отрезке [0..указатель на текущую медиану], если это значение больше чем номер медианы, сдвигаем влево на 1, если меньше вправо — переход вправо или влево по двусвязному списку.
кто-нибудь может написать, как делать это красиво?
Ну если за n^2*lg(n) решать, то просто декартовым деревом делается. Там, по сути, только добавление же нужно + k-ый элемент, а это сплит один и всё.
нет, все это шлак, мне нужно поистенне изящное решение
существует подозрение, что для всех отрезков величину f[i][j] можно узнать за N^2
Решение G: вначале проверим, что граф связный, иначе дерева не существует. Пусть в графе n вершин, cr компонент связности по красным рёбрам и cb компонент связности по синим рёбрам. Тогда нужное дерево существует тогда и только тогда, когда cr - 1 ≤ k ≤ n - cb.
Как это доказывается? Полтура пытались это доказать/придумать конструктивный алгоритм, плюнули, послали, получили ОК. Надо было это, конечно, с самого начала сделать...
как вообще это в голову может прийти?!
не говоря уже о доказательстве
Опыт и интуитивное понимание предмета задачи (в данном случае — остовных деревьев).
Остовные деревья — хороший объект. Хорошие объекты обычно существуют, если им ничего так явно не мешает. Например остовное дерево существует если ему не мешает разрез 0 величины.
Посмотрим что может явно мешать
1) Слишком много компонент по синим ребрам. Тогда просто не бывает дерева в котором так много синих ребер.
2) Слишком мало компонент по красным ребрам. Тогда придется брать много синих.
Что такое слишком много и слишком мало выписывается из очевидных соображений. А почему этого достаточно, Женя уже написал ниже.
Ну, например, вначале построим дерево с k = cr - 1, а потом будем вставлять в него синие рёбра по одному. При вставке ребра смотрим путь между его концами по дереву: если на нём только синие рёбра, то тогда не вставляем новое ребро, иначе выкидываем одно из красных рёбер на этом пути и вставляем синее. В итоге всё, что было связано по синим рёбрам в исходном графе, будет связано по ним и в дереве, значит, в дереве будет n - cb синих рёбер. Поскольку на каждом шаге количество синих рёбер меняется не более чем на 1, любое промежуточное значение также можно получить.
Проверять связность, кстати, необязательно — она дана в условии А так у нас в точности такое же решение