11-13 октября 2013 года будет проходить южно-восточный европейский полуфинал мира студенческой олимпиады с программирования ACM-ICPC. Уже во второй раз олимпиада пройдет в он-сайт режиме в двух университетах:
- Бухарестский политехнический университет\ Румыния
- Винницкий национально технический университет\ Украина
Олимпиада будет проходить в одно и то же время, на одном и том же наборе задач с общей таблицей результатов.
Так же можно посмотреть онлайн видео-трансляцию здесь
От себя пожелаю командам удачи, и пусть победит сильнейший.
Есть ссылка на работающий монитор? Традиционно для SEERC — тотальное убожество, на сайте правила с 2011 года, неправильный список команд и остальные похожие приколы, и даже в адресе, по которому должны быть онлайн-результаты, ejudge/seerc2011.html тонко намекает... Хотя если поменять на 2013 — все равно не работает.
Ты в самом деле не прошел на SEERC?
Прошел, не смог поехать.
Увы, пока нельзя показать общие результаты. Огромная просьба к тем, у кого уже есть ссылка на результаты не выкладывать ее сюда!
Спасибо, теперь смотреть намного удобней.
Пошли наш контест писать)
http://vntu.edu.ua/webcam/cam3.html
http://acm.ro/
Финальный монитор SEERC-2013
В связи с тем, что на задачах SEERC-2013 будет проведён Гран-При Южной Европы, просьба к участникам не обсуждать задачи до окончания Гран-При.
Если кто-то уже знает, то напишите, пожалуйста, кто прошел.
Если квота 3 команды, как в прошлом году, то SobolevTeam, BZFlags и Phantom Menace.
Подскажите, как решать B?
У меня такое: если старые ребра были дороже — будем искать кратчайший путь в явном виде по новым ребрам — можно просто построить граф, ребер немного ведь. Ну и при необходимости дописываем в конец пути одно старое ребро.
Если новые ребра дороже, то пустим бфс по старым) Ну там очевидно, что если мы отсортим списки смежности для новых ребер, то можно проверять наличие/отсутствие старого ребра в bfs простым указателем. Ну как-то так) Понятно, что если новые ребра дороже, то ответ это минимум из цены минимального пути исключительно по старым ребрам и цены одного нового ребра — лучший ответ будет состоять или исключительно из старых ребер, или из одного прямого нового ребра 1->n.
Навешал туда каких-то костылей и break-ов и оно зашло. Ну еще у нас для N<4000 обычный Дейкстра.
Ну и да, мне тоже интересно услышать авторское решение.
Мы решали так же, только без брейков и костылей :-D
Не зашло по времени :)
Ну там БФС по старым рёбрам нужно ещё уметь за O(n+m) написать, ведь старых рёбер может быть O(n^2), что не заходит.
Видимо это у нас и не удалось, собственно поэтому мы ее и бросили, так как больше идей не было.
Можно подробнее, как его написать за n+m? Я умею только обычный bfs, в котором m — это как раз О(n^2).
Будем поддерживать сет активных вершин. Изначально в нем все вершины.
На полном графе без M ребер когда пробуем пойти по ребру, происходит одно из двух событий — либо удалили вершину из сета, так как мы ее добавили в очередь и не нужно туда приходить второй раз, либо попробовали пойти по одному из тех M ребер. В итоге таких событий N + M, ч.т.д.
Спасибо, красивая идея.
Я как делал:
Заведем множество интересных вершин (которых мы ещё не достигли), положим в него вершины [2,n].
Окей, пустим БФС.
Допустим, мы находимся в какой-то вершине u.
Отметим все вершины, в которые есть ребро из u.
Затем, будем итерироваться по множеству из интересных вершин, и если ребра в графе нет (вершина не отмечена), то мы релаксируем расстояние, закидываем эту вершину в очередь и из множества интересных её выкидываем.
Понятно, что мы посмотрим некоторые вершины из интересного множества несколько раз, причём в сумме ровно столько, сколько было рёбер в нашем изначальном графе.
Код: http://pastie.org/private/nndowmwfhstrmvw6iympgq
Не очень понятно, почему в массиве newRemain суммарно не квадрат элементов за весь бфс.
Ну когда элемент попадает туда? Когда было ребро. Ребер m :)
Мы написали дерево отрезков со следующими операциями: Найти минимальный элемент, удалить элемент, установить значение элемента, для всех элементов на отрезке обновить значение a[i]=min(a[i], val). С помощью такой структуры можно написать честную Дейкстру на заданном графе за O(n * log n).
Какое у вас зашло H? (Red John Game)
Знаю прошедшие решения:
1. если делители только степень двух и степень пятерки;
2. если не делится на три;
3. является степенью двойки или делится на пять.
Есть ли нормальное решение, и как его доказать?
Можно показать, что из прямоугольника 2x3 можно получить 1x3. Этой операцией можно свести к n-3. Для 4 и 5 строится пример. Почему для кратных 3 нельзя, не знаю.
Раскрасьте доску в три цвета по выражению (x+y)%3. Тогда каждый ход меняет четность числа фишек каждого из трех цветов. В конце должны придти к 1-0-0, а изначально при n%3==0 всех трех цветов поровну (т.е. и одной четности в том числе).
Понятно почему нельзя кратные трем, но есть ли доказательство того, что найдется какая-то тактика для остальных чисел?
И интересно сколько же тестов было на задачу если прошли явно неверные решения, такие как описанное у меня третье решение. Да и первое решение тоже должно выдать неверные ответы на числах не кратных 2, 3 или 5.
я же правильно понял, что уже n=7 приводит к различным ответам в 1,3 vs 2 ?
upd: сами сдали n%3 != 0, нашли когда игрались с монетками и пришли к выводу, что ряд, длина которого кратна трем приводит к "выбросу", нестрого, но решили проверить... И вот как реджаджить такое? Нестрого доказали, проверили сабмитом, зашло — ок, верная догадка. Ведь далеко не все есть время доказывать. Особо памятуя прошлый проблемсет с out.println(m*l/n)
Да, есть очень мало чисел, которые дают одинаковый ответ на все три решения. И похоже, что в тестах как раз они и были.
Это задача мне известна в более общем виде — для прямоугольника, а не квадрата, и там единственный инвариант именно такой, как я сказал, за исключением какого-то крайнего случая прямоугольника со стороной 1 и, возможно, 2. Пример стратегии основан на убирании прямоугольников 1на3 до какого-то маленького случая, которые можно разобрать руками. Насколько я помню, эта задача есть на тимусе, а вообще она взята с какого-то древнего всероса по математике.
На контесте тоже не доказал, что для кратных 3 нельзя. Сейчас вроде придумал.
Покрасим все клетки в три цвета по сумме координат по модулю 3. Ясно, что вначале клеток всех типов по 3n, а в конце какого-то типа 1, остальных типов 0. Поймем, что от каждой операции количество клеток каждого типа меняет четность (например, скачем клеткой 0 через клетку 1, получаем клетку 2, тогда для 0 и 1 уменьшается на 1, для 2 увеличивается на 1). Поэтому все количества должны всегда иметь одну четность. Противоречие.
UPD: из этого следует также забавный факт, что для n, кратных 3, нельзя получить меньше трех клеток. При помощи тех же преобразований оценка легко достигается.
Я придумал тоже после контеста (и после разбора, к сожалению) сопоставить цветам корни из 1 третьей степени. Тогда вначале сумма ноль, а в конце должна быть ненулевая. Тут заодно вроде бы строится критерий того, когда можно получить, а когда нельзя
Ах, да — авторы С — за чтение в бинарном формате — горите в аду!
P.S. Мы ее все таки сдали с +11
Лайк. И особенный ад давать такие задачи на онсайты. Интересно, чем думали орги? Да, это невероятно полезный навык — умение читать бинарник. И, безусловно, каждая команда с онсайта этот навык освоила.
Для Румын это нормально давать такое на контест. Год за годом появляются новые места где можно сломать ногу ...
+21, упорно сдавал то на плюсах, то на джаве. В итоге зашло рукописное чтение на джаве(через байтовый буфер и сдвиги) вместо DataInputStream. Просвятите, как на плюсах по-человечески должно быть чтение, а то за 0,5ч поиска не нашел
Такое считывает из бинарного файла один инт в переменную someVar. Подробнее здесь: http://www.cplusplus.com/reference/cstdio/fread/
спасибо, а то ушел гуглить в сторону fopen и fscanf и зарылся
Такой вопрос — там вообще был макстест? Как я понимаю, в этом тесте надо будет считать 10000*10000*4 байт — 400 мб инпута. В моем представлении, скорость доступа к типичному среднестатистическому винчестеру физически не позволяет это сделать за 2 секунды. За 4 — поверю. За 2?.. SSD какие-то?
Более того, мы файл вообще два раза считывали — прошло.
Я тестировал локально на макстесте — чтение отрабатывает за 0.16мс. Винт не ссд.
Upd: но это видимо не совсем честный эксперимент, так как данные в кеше оседают.
Ввод-вывод обычно не учитываются в user-time, по которому выставляется TL. Т.е. реальное время работы скорее всего будет дольше 2 секунд, но от процессорного времени чтение почти ничего не съест.
Да ну? А зачем тогда придумали scanf вместо cin?
придумали scanf вместо cin
шта? О_о
Все тестирующие системы которые я знаю меряют usr+sys время. А считывание это как раз sys.
Мы тоже так пытались, но на контесте в man freopen прочли, что идентификатор "b" игнорируется в UNIX подобных системах.
А как решалась задача G?
Динамика dp[i][q]. Где i-текущий номер цели, а q принимает такие значения:
Вначале d[1][0] = 0, dp[1][1] = a[1], остальные -INF (если нумеровать с 1).
Зная dp[i][q] несложно вычислить dp[i + 1][j] для любого j.
тоже решал dp, чуть по-другому описал сами состояния (может кому понятнее будет корректность)
0 — предыдущая не входит, текущая — свободный выбор
1 — предыдущая входит, текущая — свободный выбор — лишнее состояние, понял только когда дописал этот пост
2 — предыдущая входит, текущую обязаны взять
3 — предыдущая входит, текущую не можем взять
Но было несколько AC очень быстрых, может проще что-то есть?
По-моему, динамика несложная. Есть классическая задача про взрывоопасность, где надо ставить грузы друг на друга, чтобы никакие 2 опасных не были рядом. И количество вариантов этого считать. Чем-то похожи задачи, опытные команды могли накодить быстро.
не спорю, динамика простая, но до этой задачи еще нужно долистать и аккуратно реализовать переходы, вот поэтому решил переспросить.
Классика на взрывоопасность разве не фибоначчи (модифицированные), без дп? Хотя тоже можно дп назвать.
Ну, как-то так. Если просто сказать, что это Фибоначчи, то непонятно, почему. А если сказать, что ДП и объяснить через ДП, то всё понятно становится.
У меня это же написано, дает ВА 3.
У одной команды с нашей площадки тоже было что-то похожее. Не знаю, как сдавали, но сдали потом. Может, при переходах ошибка. Или просто скрытная бага.
Если мы знаем dp[i][q] и хотим посчитать для i+1, то там такие переходы:
Ответ — максимум из dp[n][q] при всех q.
А как догадаться, что очки начисляются по уже настрелянному набору мишеней, а не "online", выдавая баллы за каждую пораженную мишень с учетом текущей позиции?
У нас такая же фигня с пониманием была, долгое время боролись с WA3, пока не перечитали условие)) На самом деле странно, что авторы не прояснили это хотя бы в семплах.
За фразу в формате инпута
Follows the three integers, при том, что речь на самом деле идет не о трех числах, а о N тройках чисел, надо канделябром, простите.А я то думал почему у нас даже полный перебор падал на 3 тесте.
Никак. На наш клар до конца контеста так и не ответили. Мы просто написали еще одно решение.
Какая сложность в І?
Я вспомнил прошлый этап, опять написал обычный
N^3, оно опять прошло)Естественно на плюсах?:)
UPD. Я могу к каждому OpenCup'у такой комментарий писать :)
n^3/32 у нас, если я правильно вспомнил, что за задача
Да все равно как-то больно много) Если подумать, то на самом деле у вас там
N*(M+N)/32, нет? Ведь для запуска апдейта еще нужно, чтобы ребро было. С учетом разреженности графа — это важно.Ну и мои
N*(N+M)— тоже не так уж и много, даже для полсекунды.N*M/32 ведь, откуда там N*(M+N)/32? 4*10^6 операция, все вроде бы четко.
4*10^7. Хотя это не меняет сути дела)
А разница между M и M+N в данном случае не столь значительна, чтобы обращать на нее внимание.
Просто (N+M) — звучит как что-то, что дал нам дфс. Думал, там как-то не так написать можно.
У меня идейно
Если хранить граф матрицей, то как раз и получается N*N+N*M. Да и топсортить ограничения позволяют тоже за квадрат. А если можно работать с матрицей — так зачем что-то придумывать?
Давайте будем реалистами — 5000^3 / 32 == 3906250000 как это может зайти даже на плюсах за полсекунды?
у нас на самом деле O(nm / 32) :)
Не зря там ограничение на число ребер было..:)
Давайте будем внимательнее, и заметим, что у тебя там два лишних нуля.
Могу ошибаться, но N = 5000. Могу скринкаст выложить, где я возвожу это число в куб и делю на 32 :)
UPD. Это все естественно только если сложность O(N^3)
В данной задаче это не совсем правда, так как N^2!=M.
Угу. А что это за алгоритм такой? Просто для I я умею транзитивное замыкание сделать за куб от вершин.
Просто ДФС пускаем и в каждой вершине храним битсет достижимых из неё.
В E есть нормальное решение без рандома, эвристик и прочей ереси? =)
Да. Нужно только доказать факт, что если в какой-то ячейке написано число (ax + by), то (x, y) = 1
Ну, доказали. Разве пар (x, y) не очень много? Как найти среди них хоть одну взаимно простую?
Решим диофантово уравнение, получим решения (x0 - at, y0 + bt). Найдем границы для t так, чтобы оба этих числа были неотрицательными. Дальше запустим алгоритм Евклида, который gcd(x0 - at, y0 + bt) преобразует в gcd(x, y + t). Теперь надо подставить возможные значения t и посчитать этот gcd. Если отрезок возможных значений t достаточно большой (больше, например, 200), то обязательно найдётся t, которое даст взаимно простое решение. Иначе просто переберем все возможные t и посчитаем для них этот gcd.
P.S. бОльшую часть решения писали в BigInteger
Мне кажется именно это Миша и имел ввиду под магией.
Мы сдали следующее. Будем считать, количество таких хороших t в обозначениях Kostroma. Легко посчитать количество комбинаций сnt(s), таких что a и b положительны. А теперь формула обращения мебиуса дает формулу
.
Правда писать не очень приятно — надо раскладывать S на множители. Правда основное время убилось не на это, а на не нужные BigInt'ы с java, на которой мы все пишем в разы медленнее.
А
__int128_tне пробовали? Там просто 64-битный компилятор есть.Расскажите, пожалуйста, как преобразовать? Не совсем понятно.
Запускаем алгоритм Евклида для a и b, попутно преобразовывая x и y. Делаем такие операции:
.
Мы честно перебирали все возможные пары, поверив в то, что если есть много таких пар, то ооочень маловероятно, что все они оказались не взаимно простые. На тестах жюри, видимо, повезло)))
Мы брали миллион пар с самым маленьким x, миллион с самым большим x и миллион случайных. Да и то до конца не были уверены, что зайдет.
Интересно, а почему в таблице OpenCup только одна команда Moscow SU? Остальные не решали?
В Москве сегодня командная олимпиада школьников. Наверняка все ушли проводить.
Как доказать решение J?
UPD. Нагуглил.
Вытекает из
Можно сабмитом.
ок. доказал
А как решать задачу D?
У меня есть предположение, что там ответ небольшой, скажем, не больше 20. Тогда можно безидейное дп писать.
А, то есть от циклов избавляем дополнительным параметром?
Ну да, храним еще кол-во ходов.
Самый что ни на есть стандартный ретроанализ. Граф с 64^3*2 вершинами влезает в память, поэтому можно за O(n+m) было писать. А от циклов ретроанализ сам избавляется.
Я подозреваю, что сложность задачи была не в написании ретроанализа (про ретроанализ есть на e-maxx кстати), а в инициализации графа + выигрышных и проигрышных позиций :) Мы посадили пару багов вида: король рубит ладью уходя от шаха и что-то еще. Было забавно, когда я не смог поставить мат в 2 хода на тест руками, и считал, что у нас есть еще баг, так как наше решение выдавало 2. ОК пришел как раз тогда, когда я увидел этот мат.
Конечно, ясно, что просто BFS написать несложно :) И сам я с этими позициями порядка часа парился. Долгое время, помню, думал, что если на ходе ладьи королю стоит шах, то король еще может убежать. Ну и прочая подобная ересь.
Но я не думаю, что автор вопроса хотел получить в ответ доскональный рассказ о том, как позиции строить :)
Ну скорее всего да :) Просто написал свои ощущения от задачи
Ретроанализ в данном случае действует так: помечаем все известные выигрышные и проигрышные вершины, затем если больше исходящих ребер из вершины нет, то если она проигрышная — выберем максимум кол-ва ходов по всем ребрам, если выигрышная — минимум. Я правильно понял? Почему у нас не возникнет ничейных вершин, ведь есть циклы?
http://e-maxx.ru/algo/games_on_graphs Тут про ретроанализ. Ничейные вершины могут быть, конечно. Но по условию ничья равносильна поражению, так что просто для таких позиций выведем 0.
Спасибо. Там в статье вроде не сказано про количество ходов, вот я и предположил как быть.
В задаче А тысяча запусков Дейкстры с потенциалами должна заходить по времени, или надо что-то хитрее?
У нас не заходило, зато зашла жадность.
оу... спасибо
Мы делали так: смотрим на самую дорогую, пока еще пустую матрешку; допустим мы вложим в нее не самую большую из возможных, тогда что это нам даст? — ничего :) таким образом всегда пихаем в как можно большую матрешку в самую дорогую на текущий момент.
Расскажите, пожалуйста, как решать Дейкстрой с потенциалами.
Построим ориентированный ациклический граф, где вершины — это матрешки, ребра идут между матрешками, если одну можно вложить в другую, а вес ребра — это стоимость вкладывания. Кроме того, добавим по одной фиктивной вершине для каждой матрешки: в нее будет вести ребро из матрешки с весом, равном штрафу, который мы получим, если ничего в эту матрешку не получим.
Ответ на задачу — это покрытие такого графа вершинно-непересекающимися путями минимальной стоимости. Просто покрытие графа путями (минимальным количеством) ищется через максимальное паросочетание (построим двудольный граф с двумя долями размера n, где ребро (i, j) есть тогда и только тогда, когда в исходном графе есть ребро (i -> j) и найдем паросочетание в нем).
Ну а паросочетание минимального веса мы умеем сводить к максимальному потоку минимального веса, который описан, например, здесь.
Спасибо!
Когда-то раньше людям, которые проводят SEERC, вроде бы задавали вопрос про то, зачем ставят ТЛ по 0,5с и ответ был вроде бы в духе "серверов мало, участников много, чтобы все быстро тестировалось". Но я все-таки не могу понять, зачем, например, в задаче D стоял TL 1c, если у нее всего 2 теста?
Меня, например, очень расстраивают контесты, на которых я должен тратить много времени, чтобы запихнуть асимптотически правильное решение только потому, что я использую язык программирования отличный от того, которым пользуются авторы. В итоге не сдаю эту задачу на контесте, прихожу домой, переписываю на плюсы, и о чудо!, оно получает AC:(
UPD. кстати, поделитесь, пожалуйста, кто-нибудь зашедшим по D решением на джаве. Хочется все-таки научится писать быстро работающий код на джаве.
Стратегический вопрос: а почему нельзя переписать на плюсы прямо на контесте, если понятно, что решение на Java пихать и пихать?
На контесте казалось, что на оптмизирование джава кода уйдет меньше времени, чем на переписывание. В итоге он работал где-то 1,2с к концу 5го часа.
Мы переписывали. Я написал на Java и не смог даже нормально запустить у себя :) Переписать на С++ заняло 5-10 минут.
В русских условиях разве не 1 секунда стояла?
Когда мы заполняли анекту Яндекса на регистрации SEERC в Виннице нам обещали дать 250 Gb на Яндекс.Диске. Кто-то получил их?
наивные рабы