Здравствуйте!
И вот ОН грядёт! В эту субботу — 16 июня в 11-00 по московскому времени состоится эпическая битва, которая должна всем надолго запомниться — 550 человек падут, и останется только 50. Может быть, это будете вы?
Приглашаются все, кто прошёл квалификационные раунды. А также болельщикам вход не запрещается...
P.S.: Опубликован официальный разбор.
P.S.: Видео-разбор — от него iPhone andrewzta раскалился.
До свидания.
глупость мой комментарий!
Ну что за несправедливость, 16 у меня экзамен. Придется сдавать с другой группой, потому что отборочный пропускать нельзя.
А у меня защита диплома :)
И что ты выберешь?
Ну диплом каждый день защищаешь, а отборочный тур RCC — один такой.
Да ну, ты успеешь после защиты, если результаты не будешь ждать :)
Не знаю, как в ТГУ, а у нас на защите вполне реально спокойно порешать контест :) Выступил, ответил на вопросы, поблагодарил всех, сел на самые Богом забытые места в конце аудитории и решай сколько влезет, главное не сильно бурно радуйся Accepted'ам.
Ну а нам остается надеяться только на то, чтобы успеть сдать до 11.
Опять в субботу вставать черт знает во сколько ((((
Я не очень понимаю зачем соревнование, в котором участвует море студентов, ставить в 11 утра в самый разгар сессии. Лично я уже договорился с преподавателем, но, право, некомильфо...
Более того, об этом еще в прошлом году говорилось. Неужели пожелания участников нельзя учесть?
А еще болельщики ездили в этот день на футбол. Хотя кажется надо было выбрать RCC
У кого-нибудь открывается сайт RCC?
У меня открывается.
Попутать индексы в 2 задачах — это уже перебор как-то
Спасибо за задачи, было интересно!
Расскажите пожалуйста, как решать B не тупым разбором случаев и как упихать D в TL?
А что в D пихать? Там N * N * 10000 легко заходит.
А где там разбор случаев? Находишь простой поток из вершины s1 в s2, все ребра от s1 до s2 релаксишь на велечину потока, далее находишь предка вершины s1 с максимальной величиной ребра и аналогично s2. Ответ flow + min(ans(s1), ans(s2))/
Ну дело в том, что я не знаю потоков... :(
Там не нужен поток. Заметим, что у нас дерево, путь всегда один, следовательно, можно "поток" просто посчитать тупым обходом в глубину.
Ну так это и есть обычное решение, просто назвали его потоком.
Так, как дано дерево, то просто нужно найти min из прочности дорого пути между s1 и s2 вместо потока.
Потоки в любом случае нужны, так что учить их рано или поздно придется.
Поток в дереве — это минимум пропускных способоностей на пути. Никаких специальных алгоритмов знать не надо.
А в B у меня 4 случая: оба смежных со столицами ребра входят в путь между ними, оба не входят, одно входит, другое — нет. По-моему 4 случая — это немного.
У меня без проблем D зашла (асимптотика — O(N2 * T)).
Если S > T, то поменяем их местами (несложно доказать, что ответ от этого не поменяется), т.е. мы утверждаем, что всегда путаем монеты большего номинала с монетами меньшего номинала. Сортируем монеты по возрастанию номинала (для удобства).
Далее динамика dp[i][sum] — можем ли мы набрать монетами сумму sum, не используя монеты типа i. Наверное, как её считать — очевидно. В самой динамике храним boolean значения — можем мы добраться до такого состояния или нет.
Потом перебираем все пары монет, пусть C1 — номинал первой монеты, C2 — номинал второй монеты, C1 > C2. Заметим, что мы могли их спутать, только если (T - S) делится на (C1 - C2). Отсюда получаем количество спутанных монет:
. Надо не забыть отсечь случаи, когда C1 > T или C2 > S. Проверим теперь, можем ли мы набрать сумму (S - count × C2), не используя монету C2, и можем ли мы набрать сумму (T - count × C1), не используя монету C1 (для проверки мы и считали динамику в начале). Если всё получилось, то прибавляем к ответу единичку.
Да уж, мне тоже надо руки выпрямлять.
Спасибо!
Ок, поправлено.
Так и есть, я изначально ошибся.
Я посчитал динамику dp при помощи битовых масок: ) А второй этап я оптимизировал перебирая count только как делитель T — S. Таким образом получается не больше 107 операций.
можно считать одномерную динамику dpsum, перебирая i в цикле...
B решается так: находишь путь из s1 в s2, уменьшаешь все рёбра на нём на величину минимального из них (пусть она равна cm), тогда ответ равен cm + min(maxai = s1ci, maxai = s2ci) (здесь ai и bi — концы i-го ребра, ci — пропускная способность, каждое ребро можно рассматривать в любую сторону, s1 и s2 — номера столиц).
это неловкое чувство, когда проспал полраунда...
А как решать С нормально? Я писал с 50000 сетами, деревом отрезков и кучей кода, который так и не заработал =(
Ну по-моему, это было нормально. В сетах храним состояние вагонов, в дереве отрезков — кол-во человек в каждом вагоне, при этом дереву достаточно искать минимум и максимум. Чтобы найти наиближайший максимум, можно сделать бин. поиск по удалению от купе, из которого только что высадили человека.
Понятно, спасибо. Ну да, я это и писал. Надо, значит, руки выпрямлять.
Я вот написал
scanf("%x", &x)вместоscanf("%d", &x). А это 16-ричные числа)Отменный баг =)
Я слышал, что scanf вообще магический. Например, %x читает шестнадцатеричные числа. Там еще как-то подобие регексов можно использовать, но я не знаю как.
Если кто-то уже знает, напишите пост на Codeforces про магия scanf. Все будут очень благодарны.
регекспов это сильно сказано. Там можно считать пока множество символов и читать пока не множество символов. Еще есть можно как-то резать число прочитанных символов вроде. И еще есть несколько плюшек для ввода чисел, вроде этого
%x.Подобные вещи для printf более полезны. Впрочем, если будет время я как-нибудь что-то подобное напишу. Взял на заметку. Можно заодно попробовать на этом инвайт на хабр получить.
ничего регекспного там нет, тем более статей по scanf море
Пример хорошей статьи про scanf/printf с уклоном в олимпиадное программирование?
google->scanf printf
1 и 3 ссылка — исчерпывающее объяснение
Спасибо
Есть в
scanfрегулярные выражения, только слабенькие. Например, такой код:Будет считывать строку как обычно, пока не встретит в ней символ, отличающийся от латинской буквы.
Если написать
scanf("%[^0-9]", s);, то считается строка до первого вхождения цифры.Вот только считывать так строки в цикле не получилось — не переходит к новой. Возможно, намудрил где-то.
Думаю, строки
stringболее удобные, но и это может пригодиться."слабые регулярные выражения" — такие слабые, что можно не писать, что это регулярные выражения
Можно без дерева отрезков. Храним два сета: список вагонов, где K чуваков и где K+1 чуваков. Когда какой-то опустошается, меняем местами. K можно и не хранить. Кода мало.
А можно тупо завести еще 50к сетов (купе, где 0 чуваков, купе, где 1 чувак и т.д.), и еще поддерживать минимальный индекс, где есть хоть 1 купе и максимальный, где есть хоть 1. Избавляет от кучи гемора
При желании можно обойтись одними лишь стандартными структурами:
http://pastebin.com/y828AhRQ
Вообще, кажется пора начинать набирать скилл в STL. Привычка с Pascal/C — всё писать самому. На олимпиадах по формату IOI ещё катит, на формате ACM, начинает сильно чуствоваться необходимость в STL. Даже если дерево отрезков пишешь достаточно быстро, всё равно какое-то время тратится. Здесь же, когда я понял что надо писать кучу с динамическим выделением памяти, сразу пришлось лезть в мануал сета.
Вообще интересно, есть ли контесты, где STL запрещён? :)
А как ты себе это представляешь технически? Удалить файлы из папки компилятора или следить руками? Мне кажется за такое....
Естественно везде разрешена стандартная поставка компилятора. Другой вопрос что нестандартные расширения, а так же фичи с++11 могут не везде поддерживать.
Ну можно просто запретить C++ и оставить С, например) Есть ещё существенные отличия C и С++, реально применяемые в спортивном программировании, кроме STL?
Нормальные структуры (с методами и конструкторами), перегрузка операторов, объявление переменных не в начале функции (в том числе в заголовке цикла for), наверно куча всего еще.
UPD: говорят, в новом стандарте все-таки можно объявлять переменные где попало.
Можно, -std=c99
Да, пожалуй достаточно для невозможности такого варианта. В С уже можно объявлять переменные не в начале функции, но в for'е всё ещё нельзя, last time I checked.
в fore можно если c99
Тогда значит, объявлять переменные не в начале можно было ещё до С99, потому что я когда года 3 кодил в С, в for'е было нельзя (не ставил специально С99), а вот переменные не в начале — спокойно.
Раньше было много разных индусских контестов, на которых можно было получить вердикт Restricted Function и потом двоичным поиском выяснять, что же так не понравилось системе проверки. Ещё и оказывается потом, что это какой-нибудь memset... конкретно насчёт STL не помню.
Артур, я сдал такое после исправления нескольких багов
Я полчаса просидел за поиском багов и решил попытаться придумать, как избавиться от ДО, но так и не придумал.
Жалко :(
исправлять час косяк со вторым тестом в первой задаче — это уже перебор как-то...
а почему в D во 2м семпле нельзя взять монеты 2,2,3,4 и Ринсвинд принял монету 4 за монету 3, тогда получается что он отдал 2+2+3+4=11, а сумма была 2+2+3+3=10 или я что-то не понимаю в условии?
У меня таже проблема была. Я написал клар и они изменили немного условие(зделали новое обяснение первого семпла).
Никакого оповещения не приходило. Я полчаса думал, что происходит. Тоже писал клар, потом кое-как сдал, обновил страницу — и, конечно же, условие обновлено!
У них оповещение — ето колонка справа(Russian Code Cup в Твиттере). Там появилось, что условие обновлено. И на клары ответ приходит только на почту(или я не нашол), а ето как-то странно.
Твиттер это конечно круто, но мне делать больше нечего, чем твиттер смотреть? Надо сделать нормальную систему оповещения, чтобы alert вылезал.
Он заменил все монеты номинала 3 на монеты номинала 4
Да, но в текстовом пояснении первого сэмпла, единственный вариант который подходил, это что заменялись все монеты, из того, как он в итоге заплатил, а не как он хотел заплатить.
У меня в коде изменений было минимально, но кого-то могло сильнее затормозить.
Почему работает такое решение на задачу А? http://pastebin.com/Divpphx2
Может рёбра нужно сделать неориентированными?
Перестановка — это набор циклов. Внутри цикла мы любое число можем поставить на любое место за некоторое кол-во шагов. Проверяем, находятся ли 2 числа в одной компоненте связности, т.е. цикле.
Потому что, каждое произведение перестановок соответствует некоторому пути в этом графе, дополненном петлями, и наоброт.
Потому что каждая перестановка происходит по циклу, отсюда, переходя к графу, легко следует, что если из вершины v1 можно добраться до v2, то и из вершины v2 можно добраться в v1. Следовательно, нужно найти все компоненты сильной связности, и, если две вершины из запроса принадлежат одной и той же КСС, ответ yes, иначе no
мне вот больше интересно, почему такое решение НЕ работало первые почти полтора часа, в связи с магическим рантаймом на 2м тесте...
Потому что оно правильное:)
А можно не работавший код? Мне просто интересно как можно читать числа, так чтобы на что-то влияли лишние пробелы. Или там что-то более существенное было?
http://pastebin.com/yXNMPjFu
понятия не имею что там было. сначала это не работало, потом сделали реджадж.
Интересно. Не представляю как это может не работать из-за "неправильного форматирования"
не туда
В тренировках есть дорешивание и виртуальный контест — 2012 Russian Code Cup, отборочный раунд.
Супер! Спасибо!
Не модно больше быть Аладдином... (proof)
Мои решения, если кому интересно
Очень сильно напоминает F: http://acm.sgu.ru/problem.php?contest=0&problem=526
А откуда эта задача?
Наш четвертьфинал.
С перетестированием задачи А не очень понятно. После того, как исправили тесты, теперь заходит моё первое решение. Однако при перетестировании засчитали только последнее, то есть штрафные минуты не отминусовали почему-то.
UPD: уже оперативно пофиксили
Не знаю про эпическую битву, но эпический слив "не сделать В за 50+ минут реального времени и не пройти" у меня получился.
У меня тоже получился слив на В — "случайно написать в В в DFS вместо минимального участка пути его длину, не заметить, и получить +4". С +3 — уже 52е место.
У меня ACDF в итоге, просто)
Причем такой "герой" я один, похоже)
Еще есть Gassa c ABDF.
Ну, ABDF ещё можно объяснить, а ACDF это просто "не судьба". Бывает и такое иногда...
Я, как выяснилось через 20 минут после конца контеста, не заметил, что по "старому пути" из C1 в C2 еще можно немного потока толкнуть %)
Ответ, оказывается, 97 %)
А, ну да.
Не сделать С за 100+ минут и не пройти покруче
Ну, не совсем. Тебе её и так надо было сдавать со штрафным временем не больше чем 100 минут.
а ты специально пишешь, чтобы тебя заминусовали?)
Саша, я это пишу только потому что считаю что так и есть. И еще потому что считаю что я должен был пройти на финал, и в очередной раз запорол свой шанс.
Странно. Получил на С WA5, тупо забыл добавить проверку на выход итератора за пределы, но по логике должен был быть Runtime Error. Здесь, в тренировках, рантайм как и положено. Печально, увидел бы рантайм — успел бы найти косяк.
Ну, не могу сказать, что выходы за пределы чего-либо больно детерминированные. Как-то раз было Memory Limit Exceeded, на таком же случае, только за пределы ещё что-то писалось.
Разные версии компилятора скорее всего. В c++ разные выходы за границу не всегда ловятся. Даже в контейнерах.
Сейчас прибегут сторонники Java и начнут тебя агитировать вступать в их клуб :)
А почему не Паскаля? :) Там есть вполне нормальный Range Check Error.
в Паскале меньше встроенных плюшек, а возможности Java и С++ примерно одинаковы (даже в Java побольше будет, например, BigInteger, StringTokenizer и прочее)
В Java нет swapа)))) Это огромный минус для олимпиадного кода
И еще там есть extended, который круче сишного long double. И меньше конструкций, которые при маленьком изменении скомпилируются с неадекватным результатом. Это все плюсы Delphi, которые знаю лично я.
Гена не в счет. :)
Да ладно, можно писать на том же C++, но везде вместо массива vector и вместо [i] использовать .at(i) =)
Можно, конечно :) Но ходят слухи (сам не проверял), что это в несколько раз замедляет работу программы
Интересно, я один сдал D за O(S*n)? :)
наверно:D а как?)
У меня Sn + n2. Думаю это и имелось ввиду. А там то заходит Sn2?
Да, у меня тоже.
Ага, все сдавали S*n^2 и в разборе тоже S*n^2.
Ну ок. А зачем Sn2 Это чтоли тоже самое, только делать один и тот же рюкзак n раз?
Почему же, n разных рюкзаков
А как делать за O(Sn)?
O(Sn2) это n динамик вида можно ли набрать число x, не используя число a[i]. Вроде бы это нельзя сжать в n раз...
На самом деле можно хитрым образом сделать (мне Петя рассказал) Будем в динамике число способов искать вместо того, достижимо ли. Тогда чтобы понять, достижимо ли без данной, надо просто посмотреть кол-во способов с данной (ans[v-c]) и сравнить с ans[v]. Если равны, то без данной нельзя
Классно. А количество способов не может вылезать за int/long long типа? Или по модулю считать можно?
По случайному модулю
А что здесь ans[v], c?
c — цена исключаемой монеты, ans[v] — количество способов набрать сумму v
Имеется в виду (ans[v-c]+ans[v-2c]+ans[v-3c]+...+ans[v%c])?
Да, забыл троеточие
я наверно туплю, но почему именно сумма, а не просто ans[v-c]?
Ну да, я туплю
Можно поделить на 64 при помощи битовых масок. Хранить для каждого числа 4 unsigned long long. i-й бит — можно ли получить это число без i-й монеты. Переходы делаются при помощи оператора побитового or и xor.
Я так сдал, потому что мне 4·108 показалось слишком много.
А как обойтись одним рюкзаком?
Так. я видимо чушь написал выше.
Ну вот посчитаем рюкзак на всех суффиксах и на всех префиксах. Это O(Sn). Тогда проверка для одного значения суммы и одной запрещённой монеты делается за O(s). Заметим, что при фиксированной запрещённой у нас для второй монеты вариантов не 200, а количество делителей S — T, что существенно меньше; вроде выходит быстрее, чем S n^2.
Да, заходит.
Потому, что 142 место резко затупило))))
Не затупило бы — было бы у 23го пять задач.
Появились галочки — проходят по 53 место (которое, между прочим, разделено) включительно
А добирают, если кто отказывается? 56-57-й :D
Вопрос тоже интересует. Шансов конечно мало, 60й, но начало учебного года, мало ли :)
В прошлом году брали по 53-е включительно.
То есть нас таких только трое? Я думал больше.
Если знаешь кого-то еще в топ-50, кому нет 18, лучше скажи)
Без заключительной скобочки звучало бы, как угроза.
На 55 месте OlgaSob. Никто не желает уступить даме место?)
При этом уступить должны двое. Прошли то 53.
Если уступят двое, тогда два места осободятся, кому второе?
Сейчас проходит 51 человек. Мне, tourist , yeputons нет 18 лет. Поэтому проходит 53 место. Но оно поделенное.
Никто. Проходят первые 50 человек, трое из топ 50 проехать не смогут, поэтому последнее место, которое едет — 53е. А там делёное место. Поэтому взяли обоих, и галками отмечен 51, а не 50 человек. При отказе только одного, их станет 50, и никого дозывать почти наверняка не будут.
Пони на 85-ом!!!
whatever