Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.09.2024 00:43:06 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Обратите внимание — в этот раз старт в :05, а не в :10. По инсайдерской информации со следующего СРМа будет вообще :00
А кто-нибудь встречал такую фигню в арене: я выбираю в практисе задачу, и выпадающий список мгновенно открывается и закрывается, потом стрелками мне все-таки дается этот список и я встаю на "500" и жму Ентер. После открывается 250, а в чате пишется, что я открыл одновременно обе задачи. Это на компе openjdk6, есть ли возможность быстро все исправить?
UPD: после пару перезагрузок и перезапусков гнома стало работать, странно
Такая-же фигня, только со списком тестов. Список появляется где-то в левом углу экрана. У меня ubuntu 11.10, оболочка Unity, тоже openjdk6. Проблема решилась стрелками)
У кого-нибудь на винде такое было?
как я заметил, у меня все баги начинаются после того, как я разворачиваю окно арены на весь экран, то есть делать "maximize" окна не стоит, может быть это и Вам поможет
Не заметил, что надо результат по mod было во второй взять facepalm
Какая динамика в первой?
dp[текущая позиция][сколько цветов уже использовано] переходы понятны из того, что предыдущие min(pos, m) клеток попарно разного цвета
А как учитывать числа которые мы уже взяли, т.к. требуют, чтобы каждое число было взято?
в конце возьмем dp[p][n]
long long calc(int Rem,int pos,int N,int M,int P)/*Rem-number of songs we have not played,pos-position in playlist*/
``
можно было еще посчитать линейную дпшку, а потом по формуле включений-исключений с биномиальными коэффициентами
Привет, див-2... Как решалась 300?
Динамика [длина][кол-во чисел заюзано]
Чтобы поставить использованное число есть кол-во_исп_чисел-M вариантов. или можно добавить новое
Забыл: надо умножить еще на n! в конце, т.к мы использовали числа только по порядку, а нужны любые перестановки
В див-2 не было 300. Вопрос про 250 или 600?
Судя по сообщению, человек писал div1, а теперь думает, что выпадет в div2
Забыл добавить "так-то" =)
Я, наверное, переборщил, мне до див-2 больше 100 пунктов рейтинга.
UPD Не переборщил, -183
Уже понял, спасибо.
Есть ещё рекурсивное решение: для чисел <n,m,p> считаем ответ как n*(n-1)*...*(n-m)*(n-m)*...*(n-m) (всего p сомножителей) и вычитаем из него ответы для <i,m,p>, умноженные на число сочетаний из n по i, где i от 1 до n-1.
Результат Пети несколько удивляет:)
Скорость тестирования на этот раз приятно удивила
Как Div1-500 решать?
1) Избавимся. от переходов вида i->j для этого переименуем все i в j (или наоборот)
2) Избавимся от переходов i->i для этого их просто удалим.
3) Запустим dfs из исх. вершины по оставшимся ребрам. Если нашли цикл, то ответ -1, т.к из каждой вершины выходят 2 ребра. Если ответ не 0, то считаем ответ как сумма ответов детей
UPD: пока что не зашло, но думаю косяк в реализации
UPD2 зашло.
Если я правильно понимаю, то это Div 2 950. Её можно решить построением минимального остова. Для этого создадим массив g следующим образом:
1)если дорога есть, то добавляем ребро с отрицательной стоимостью уничтожения дорого
2)если её нет, то стоимость её постройки.
Потом модифицируем алгоритм Крускала:
I)Если мы добавляем ребро, то смотрим:
а) Это ребро было( стоимость отрицательная) -> ничего не добавляем к ответу б) Ребра не было (стоимость положительная, нам надо его построить) -> добавляем к ответу
II) Если мы не добавляем ребро, то смотрим а) Если это ребро было изначально -> то добавляем к ответу стоимость его уничтожения б) иначе ничего не делаем.
Судя по всему, это разные задачи
Я уже понял, надо было читать ваше решение перед отправкой своего.
Можно еще очень просто решить симуляцией. Единственное, что нужно дополнительно делать, так это считать не по одному модулю, который дан в условии. я использовал 3: 10^9+7, 10^9+6 и 10^15+37... Если начиная с некоторого момента после n шагов количество существ не изменилось, то тогда это количество и есть ответ.
К сожалению это решение я сдал только в дорешивании, потому что я забыл брать модуль после складывания количества существ. :(
А как доказать ,что N <? шагов в симуляции достаточно?A вдруг будет долго одно и тоже число и на каком то шаге внезапно увелчится?
Я кстати оговорился. N шагов недостаочно. нужно N+1 :) Просто я поправил это уже в самом конце, когда подгонял под тесты.
Рассмотрим существо произвольного типа. После каждого шага оно может или вырасти в количествах или перейти в другое состояние.
Если оно выросло в количествах, сумма изменилась и повтора не будет.
Предположим, что существо не выростало в количествах в течение N+1 ходов, а только переходило в другое состояние. Тогда у нас получился путь из N+1 вершины в графе из N вершин. Одна вершина точно повторяется. Значит у нас есть цикл. и при этом в этом цикле никогда не увеличивается количество.
P.S. Перечитал комментарий, на который отвечал... N+1 шаг делать недостаточно :) а вот 2*(N+1) точно достаточно. За первые N+1 шаги мы точно проскочим все размножения, которые могли бы быть. А потом уже справедливо то, что я написал выше
Доказательство не строгое.По крайней мере,то, что количество существ вообще не увеличится через N/N+1/2*(N+1) итераций не означает что не увеличится количество каждого из существ в отдельности.
А вдруг есть 2 цикла,проходящее через заданное существо,один длины N1 другой N2,причем фаза у циклов разная(то есть они начали крутится в разные моменты времени),(то есть, существа в них трасформировались с каких то других в разные моменты времени) )
Тогда мы можем получить увеличение в существе где пересекаются циклы в худшем случае через НОК(N1,N2),не?
Хм... Может быть я что-то выше неточно показал... = Ладно... Если уж хочется строгого доказательства, то пожалуйста:
Не теряя общности будем считать, что все вершины достижимы из 1. Остальные вершины рассмотрения не стоят. При разбиении существа на несколько других можно считать, что само существо продолжает идти, но как один из новосозданных существ
Утверждение 1. Цикл в оставшемся графе не может проходить через размножающие вершины. Если же он их содержит, то тогда после N+1 шага у нас будет появлятся некоторое увеличение количества каждый N+1 шаг.
В цикл точно можно попасть, потому что все вершины достижимы из 1. Кратчайший путь от начальной вершины до какой-нибудь вершины этого цикла не больше N+1, потому что он не может содержать повторяющихся вершин, а всего вершин N. Длина цикла также меньше N+1. Значит после N+1 шага мы гарантированно попадём в цикл и раз за проход по циклу мы будем попадать в размножающую вершину. За N+1 шаг мы пройдём весь цикл, который по длине меньше, а значит наступим на размножающую вершину и следовательно количество будет расти, если проверять его каждые N+1 шаг.
Теперь раз у нас в графе размножающие вершины не находятся в цикле, то мы можем для каждой такой фиксировать только одно какое-то конкретное ребро. Таким образом мы переберем все пути существа, потому что оно проходит размножающие вершины не более одного раза (если бы это было не так, то был бы цикл с размножающей вершиной). Будем рассматривать пути в графах, получающихся удалением нефиксированных ребер.
Утверждение 2. Все такие пути заканчиваются в вершинах циклах. И в этот цикл мы попадем после N+1 шага
Очевидно :) Мы можем делать шаги в графе не более N раз и на N+1 раз мы гарантировано будем в вершине, в которой были. Вот и цикл.
Утверждение 3. Количество существ не будет увеличиваться после N+1 шагов тогда и только тогда, когда в графе нету циклов с размножающими вершинами.
=> Дано: После N+1 шага количетсво существ больше не увеличиватся. Значит в графе нету циклов с размножающими вершинами, иначе бы каждые N+1 шаг количество росло.
<= Дано: В графе нету циклов с размножающими вершинами. Тогда все пути существа заканчиваются в циклах, не содержащих этих вершин, и в них мы придем за N+1 шаг. Внутри циклов любые движения не будут увеличивать количества существ, а значит количество существ не будет увеличиваться
Q.E.D.
В графе переходов длина любого простого цикла не больше N. Поэтому после N итераций мы по каждому циклу пройдем хотя бы один раз. Как-то так
Моё решение было проверка возможности (если есть цикл с хотя бы одной вершиной из которой выходит >1 дуги, ответ -1). Сделать это можно, запустив из всех вершин, до которых мы можем дойти и из которых выходит >1 дуги, DFS. Если можем вернуться — есть цикл — -1. Асимптотика позволяет.
После этого, 50 ходов симуляции дают ответ.
Это первая решенная мной 500-ка в жизни. По этому поводу расскажу свое еретическое решение.
Задачу можно интерпретировать следующим образом.
Дан вектор-столбец X = (1,0,0...,0)^T, который последовательно умножается на матрицу. Выяснить надо понятно что.
Возведем эту матрицу в какую-нибудь большую степень. A^(2^500) вполне подойдет.
Пусть X1 = A^(2^500)*X, X2 = A^(2^501)*X. Если сумма элементов X1 равна сумме элементов X2, то это дело скорее всего зацикливается, предельная сумма достигнута, возвращаем ее. Иначе оно возрастает бесконечно.
Еще, мне было страшно, что кто-то возьмет и поломает это решение, сделав каким-то образом последовательные увеличения, кратные 10^9+7, тогда алгоритм посчитает, что предел есть, хотя его нет. Поэтому я делал такую проверку по нескольким различным модулям.
Тебе было правильно страшно. :) Вот тест который такое как раз ломает:
{"2 2 2 2 2 2 2 2 14", "3 3 3 3 3 3 3 3", "4 4 4 4 4 4 4 4", "5 5 5 5 5", "6 6 6 6 6", "7 7 7 7 7", "8 8 8 8 8", "9 9 9 9 9", "10 10 10 10 10", "11 11 11 11 11", "12 12 12 12 12", "13 13 13 13 13", "13 13", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "13 13 13 13 13 13 13"}
Идея в том что есть 2 ветви, в одной генерится 7, в другой 8^3 * 5^9 = 10^9. В один и тот же момент они встречаются и после этого каждый ход удваиваются.
"какой-то образ" выглядит, например, так:
за 10 шагов получаем 10^9+7 юнитов 1-го типа и приехали.
Вот генерилка теста против модуля m (его можно взять произведением всех модулей).
Если граф получится больше 50 вершин, можно увеличить базу k. Правда, твой модуль она всё равно не берёт — либо граф великоват, либо строки, — но своё решение я валить умею ;) .
Мое решение такое: Сперва определяем на бесконечность: есть легкий способ это определить Запускаем Флойд, далее перебираем все пары вершин если они образуют цикл, и если у одного есть > 1 выходящее ребро и есть путь от 1-го до любого из них то ответ -1.
Теперь мы поняли что ответ не бесконечность. Делаем имитацию. Умножение матриц. Смотрим сколько остается после 1000000000 ходов. Это и будет ответом.
Клевые задачи: сперва тупишь, а потом пишешь коротенький код. Респект writer'у
В итоге -25 очков. -323 рейтинга. Такое возможно? (див. 1)
судя по всему, да
я спрашивал на счет того, что может ли это быть багом?
А сколько было? У меня было 1308, получил -183.
1202 было, стало 879.
problems?
всмысле?
Просто не понимаю, чего вы ожидали от раунда, написанного на отрицательное число очков
я ожидал не такой большой минус.
Привыкай, за отрицательные баллы на TC всегда очень жестко падаешь, особенно при большом Volatility.
Несмотря на то, что мой результат в этом матче весьма печален, я считаю, что раунд заслуживает оценки 5+. Проблемсет сбалансированный и образцово показательный. Многим авторам, на чьи контесты были жалобы (не только на TopCoder, но и на CodeForces) стоит взять на заметку этот раунд Mimino.
Как в арене подключать плагины и что они делают?
Так