Всем привет!
Сегодня, 12 июня, в день, когда Россия отмечает день себя, на Евро-2012 стартуют матчи второго круга, а I_love_natalia празднует свой день рождения, мы представляем вам Codeforces Round #124.
К подготовке контеста имеют отношение команда Samara SAU Teddy Bears (craus, dalex, Hohol) и I_love_natalia. Также спасибо Alex_KPR и команде Codeforces (Gerald, Delinur, MikeMirzayanov). Мы думаем, что контест очень легкий, а вам придется за 2 часа доказать или опровергнуть это утверждение :)
Система начисления очков — динамическая (подробнее о динамической стоимости).
Авторы считают, что задачи упорядочены по неубыванию сложности.
Всем полных решений и успешных взломов!
UPD. Контест закончился, поздравляем победителей!
Div-1 (полные результаты):
Div-2 (полные результаты):
UPD 2. Доступен разбор задач.
Это правильно начинать контесты в 17:00 по Москве во время Евро.
Еще бы сессию отменить во время Евро
В Украине обучение закончилось на месяц раньше из-за Евро :)
ну еще бы, он, наверное, и сам смотрит евро)
Will the contest be ranked?
contests are rated normally :-/
vse deleted
Don't even think about that!
С одной стороны, конечно, стрёмно, но, с другой стороны, интересно было бы попробовать динамическую стоимость.
As you wish, my lord.
здесь не любят егэ)
Здесь не любят большие, несмешные, и заезженные картинки.
Держи нас в курсе
В смысле?
ЕГЭ по физике? Не, не слышал.
Почему-то почти всегда в начале анонса раунда есть в конец заминусованные комменты. =)
Теперь пришло моё время. :(
Сейчас все сообщество CF специально вас заплюсует :-)
Всё-таки это была плохая идея во всех смыслах этого выражения.
In ascending order by difficulty?
The authors believe so.
No, non-descending :)
I'm not sure if the smiley indicates irony or that sweet feeling of disagreeing with the master, but for me the order actually seemed descending in difficulty (div2).
так рейтинговый раунд?
Почему нет?
Почему да?
Обычно контесты на CF рейтинговые, или я путаю?
Рейтинговые
The contest doesn't seem to me as very easy :/
контест совсем не нравится =/
Мне тоже... Если я не ошибаюсь, то задача, которая ну очень похожа на С была на каком-то ВКОШПЕ. И вторая баянистая...
А первая была на топкодере :)
http://community.topcoder.com/stat?c=problem_statement&pm=11471
Ужас просто.
Я думал задачи легче будут, прочитал первую... очень сложная задача.
Первая? По Вашему рейтингу могу предположить, что Вы во втором диве, и с уверенностью могу сказать, что первая задача была легкая. Нужно было чуть-чуть подумать и порисовать на листике. А можно и без листика совсем :)
Просто для первой задачи второго дива народ не привык что-то думать и рисовать на листочке. Поэтому если она не решается методом мимолетного взгляда, то она сложная :)
Короткие, понятные условия! Вот все бы контесты были такими!
Subject narrative is a big problem！ It's too fuzzy to read...
wo ca
Думаю, что неплохо было бы разрешить просмотр всех версий решений для каждого участника, которые прошли претесты, по заблокированной задаче. Сейчас эту функциональность можно реализовать самому не нарушая правил ресурса, так что скрывать эту информацию нет смысла.
Хороший проблемсет, спасибо. Как E решается? Быстрее чем за квадрат строить минимальные остовные деревья в графах на кратчайших путях между всеми телепортами не умею :-(
UPD: Крууто! Мой личный рекорд — шестое место)
UPD2: Когда был одиннадцатым, в посте указали топ-10. Когда я шестой, в посте указывают топ-три. :-(
А как это делается хотя бы за квадрат?
Я пускал дейкстру из всех порталов одновременно, когда до какой то вершины уже дошли от другого портала, то добавлял соответствующее ребро в новый граф. А потом в этом новом графе искал миностов. Можно доказать что алгоритм Борувки на таком графе будет выдавать такой же миностов как и на правильном графе (когда все ребра есть).
Сперва идем к ближайшему порталу. Потом поддерживаем расстояние от множества взятых порталов до каждой вершины. Понятно, что каждый раз надо брать ближайший портал (примерно потому же, почему работает Прима). Можно заметить, что при обновлении расстояний каждая вершина срелаксируется не больше двух раз.
Затлилось, но, вроде бы, все равно правда. =)
Да, это Прим+Левитоподобный алгоритм, и он TLит на каком-то там тесте :)
Он работает k*E в худшем, к сожалению.
Запустим дейкстру, подвесив все телепорты за фиктивную вершину ребрами веса 0, из фиктивной вершины. Получим дерево кратчайших путей, если можно начинать из любого телепорта. Утверждается, что в качестве ребер графа, состоящего из телепортов, достаточно взять ребра исходного, концы которого лежат в поддеревьях разных телепортов, а вес положить равным d[u] + d[v] + weight.
Ужас...
Расскажите А Div 2 пожалуйста.
если круг поместится то выигрывает 1, иначе 2: 1-ый всегда сможет сходить симметрично относительно центра после хода 2-ого
Всегда побеждает первый. Второй побеждает только если монета изначально не лезет на стол. Эта задача из книжки "Математикон" задачи Кенгуру.
Вроде, если помещаеться хотя бы одна тарелка, то виигривает 1, потому что он ставит в центр, а дальше ходит по симетрие к ходам 2.
Єдиний коментар, який пояснив, чому так, отримав мінуси, на відміну від інших, які сказали "що виводити, щоб отримати АС". І де логіка?
Первый рисует окружность в центре, а далее ходит центрально симметрично. Понятно, что такая стратегия не работает только тогда, когда нельзя положить ни одной окружности. Т.е. если а и b больше либо равны диаметру, то первый, иначе второй.
Если первый игрок сначала не сможет поставить тарелку, то выигрывает второй. Во всех остальных случаях победитель первый.
а как же вариант с 5 2 1? куда бы первый не поставил всегда будет место для второй тарелки, а для третьей уже никак.
Смотри здесь http://codeforces.net/blog/entry/4708#comment-96221
Ставим тарелку в середину. Справа и слева остается по 1.5. Следовательно второй игрок поставить не сможет
Я первый :-)
Похож на первоапрельский контест :D
Капец задачи.
Скажите 8 тест задачи B(div2)?
Проблема с ответом infinity. Надо проверять не только a[0], а и b[0]. Если их произведение положительно — ответ "Infinity", если же отрицательно — "-Infinity".
Что в четвёртом претесте D div2?
Я думаю что-то вроде этого:
Собрал урожай хаков на задаче B. Хакал все условия, в которых замечал 3*n и 3*m =)
Такая эвристика по отбору решений мне шесть раз дала неудачный взлом вместе с тринадцатью удачными :-)
Не знаю, у меня все 6 из 6 =)
Странно. У меня 3 * n и 3 * m претесты не проходило.
За o(n * m) решается, как я понял. Запускаем обход, если дошли до края, то проверяем, есть ли с противоположной стороны проход. Если да, то Yes, иначе No. Правильно или нет? Если да, то очень печально, буквально пары секунд не хватило
UPD. Лажа
Неправильно, смотри мой пост ниже))
Можно загнать и с 3*Н*3*М:
Делаем волну на увеличенном поле, но добавим ход с краев в другой край, формально: сделаем таблицу цикличной.
Мне кажется, ни одно правильное решение не нуждается в расширении поля и должно прекрасно работать на поле n на m. Если человек сделал поле 3n на 3m, то он (как минимум изначально) писал неправильное решение.
Ой ли? А разве http://codeforces.net/blog/entry/4708#comment-96200 неправильно?
(Я понимаю, что легко быть умным потОм, а сразу можно что-то не так подумать, я вот вообще весь тур пытался спасти принципиально неправильное решение... Но всё же, кажется, Вы не правы.)
Почему данное решение по Д(див 2)/Б(див1) не проходит: Пройдём дфс-ом по лабиринту, пометив в матрице b[][] клетки лабиринта, далее пройдём ещё раз, и попав в точки на границе смотрим, принадлежит ли противоположная точка лабиринту.
Это тест не только против Вашего решения, но и против моего (взломанного).
Да, недодумал немного, а жаль.
Ответ No? А почему тогда 1794033 не проходит? Я даже проверяю, чтоб тот мальчик был в пути через который я иду.
Ответ как раз Yes. По второму столбцу можно уйти бесконечно далеко.
Oh, shi...
Как вы рисуете такие штуки? Я попробовал, у меня получился ужас какой-то с точками и здоровыми S
Я вставил тест в блок, предназначенный для исходного кода. Посмотрите вторую справа кнопку над окошком для набора комментария.
Спасибо, но не получилось :( Посмотрите под спойлером, что вышло
Говорю же, должно быть два перевода строки перед тильдами.
Спасибо
(пустая строка)
(пять тильд)
моноширинный текст
(пять тильд)
Почти час думал, где же меня взломали — потом-таки догадался до этого коварства за 10 минут до конца.:)
Клевая задача С. Но задача, очень похожая на Б была на каком-то COCI, если я ничего не путаю. А как решались Д и Е?
Не на COCI. На одном латышском сайте по программированию.
What was the solution for Div2 problem A? I feel I'm missing something easy.
If at least one circle can be placed in the rectangle, then first wins, because he can place circle in the center and then play symmetrically. In other case second wins.
Wow. So nice! :) (btw, we were in the same room)
Nice questions...Short uncontradictory statements and all requiring to think..Although I did not perform well but still I got to learn a lot :)
Can someone please explain logic behind div 2 — A.
See this: http://codeforces.net/blog/entry/4708#comment-96099
I took few cases , and In every case If FIRST can place the circle inside the rectangle then He can win otherwise , He can not win.
Some idea might be thought like if there are even no of circles possible in the rectangle , then He can just place a circle midway of two circles ,,, Means He can always change the configuration for winning move.
more clearer : if in the optimal path , if there are even no of circles inscribed in rectangle , then First can change the path by placing a circle midway of two circles . otherwise FIRST will win because last movement will be of FIRST , because no of turns are odd .
это неловкое чувство, когда засрал хороший раунд
кст, задача С уже однажны была
Не понял как так произошло: я отправил неверный взлом, а он отправился два раза: 42069 и 42071
for problem D , can anybody tell me whether my idea is correct ?? for grid with position S if you are able to go to another S in it's adjacant 4 grids , Then I can walk infinitely , ans will be YES, other wise No
No.
thank you for your reply , Firstly I had an idea that if an (3 * n ) * (3 * m) grid ,,, We can go from one S to some other S then we can find a infinite cycle ,, But this used too much memory and got memory limit exceeded :(
i used the exactly idea that create an (3*n)*(3*m) maze. and while searching in the 9 times larger maze, i just terminate the process as soon as i find two 'S', then, i got an AC:) I just tried waht happened if i waiting for the searching process until it is finished, then, i got a MLE:(
Do you mean two 'S' including the stating 'S' (in the central block)? In other words, the starting 'S' and at least one another?
Yes. Actually, which 'S' is the starting one does not matter. But when you arrived a "border" of the larger maze, you should transfer your searching position to the oppsite "border" —— it does matter a lot :)
I think if we can go to any of the 'S' of 8 adjacent grids then it "Yes"
only itself is sufficient..
"We think that contest is very easy" You are kidding, aren't you?
Как нормально делать В?
У нас в диве у всех почти попадала...
Я решал по принципу Дирихле. Будем ходить по бесконечному лабиринту, отмечая (в хэш-таблице) те клетки, в которых мы были. Если мы побывали хотя бы в m·n + 1 клетках — значит, две из них соответствуют одной и той же клетке исходного лабиринта, выходим из поиска и говорим, что ответ — Yes. Иначе — No.
Супер!
Я так делал:
Проверим, можно ли двигаться бесконечно далеко вправо.
Сожмем компоненты связности в вершины, рассматривать будем только те, в которые входит хотя бы одна крайняя клетка. Теперь добавим переходы через границы поля (ребра между соответствующими вершинами). Вверх и вниз переходить можно бесплатно, перейти вправо стоит -1, влево 1.
Теперь, если в полученном графе есть цикл отрицательного веса, мы можем уйти сколь угодно далеко вправо, иначе нет.
Точно так же проверяем остальные 3 направления.
Как решать С быстрее, чем за O(n2 * logn)?
А зачем быстрее?
У меня не прошло =( Хотя, наверное, использовать atan2 для сравнения углов не стоило.
У меня WA. Но по времени времени вроде нормально.
Возможно, я где-то набажил, попробую в дорешивании без atan2. А так у меня даже претесты не прошло.
Кстати, никто не знает, как atan2 по точности валить? У нас не получилось :(
Можно дробями вида n число фибоначи поделить на n+1
Да нет, чтобы найти два веткора, atan2 от которых совпадает, не нужно так мудрить — вектор (10^9 + 1, 10^9) и вектор (10^9, 10^9 — 1).
Тяжелее сделать так, чтобы на нём действительно падали решения. Я ниже описал, как это можно сделать.
Ну если продолжать мудрить =) то понятно, что можно генерировать цепные дроби с общим началом... просто тогда разница углов будет маленькая порядка квадрата кординат и запас по кординатам будет большой.
Понятно как. Принципиально бывает четыре направления прохода в обычных решениях — сверху, слева, снизу и справа. Например, если идём сверху, делаете такой тест из четырёх точек: (X, X + 2), (-X, -X), (-X, -X — 1), (-X + 1, -X), где X ~ 10^9 и дерево (1-2), (2-3), (1-4). Тогда три нижних точки слипнутся в одну по точности, и если перебрать их все три перестановки, и перебрать некоторое количество перестановок вершин дерева (в зависимости от того, что подвешивается в решении), на одном из таких тестов точно будет WA.
Я генерил такие тесты: точка (0 0) (туда пойдет корень дерева) и штук 20-30 точек с координатами около (109, 109). Кажется, после первого захода в рекурсию в поддеревьях как раз получается то, что ты говоришь. Это тесты 61-80. Я прогонял стресс, и atan2 не падал...
Как раз atan2(109, 109 - 1) достаточно отличается от atan2(109 + 1, 109). Нужно было ставить корень дерева в ( - 109, - 109), тогда double падает. Но long double вроде бы все равно никак не завалить.
Так смысл не в том. Смысл в том, что atan2(1e9+1, 1e9) == atan2(1e9, 1e9-1). Поэтому если дать в качестве точек эти две, то их если их поменять во входных данных, то они поменяются местами и после сортировки. Поэтому верно и на тесте где они идут в таком порядке, и на тесте, где они идут в обратном программа отработать не сможет — в хотя бы одном из них сортировка окажется некорректной. Осталось только сделать так, чтобы некорректная сортировка повлекла за собой WA. А это можно сделать, как я описал выше.
Неправда. Только что проверил — (atan2(10^9, 10^9 — 1) == atan2(10^9 + 1, 10^9)) == true. На практике atan2 можно использовать до 10^7, потому что double держит порядка 15 значащих цифр.
Действительно, в g++:
(atan2(10^9, 10^9—1) == atan2(10^9+1, 10^9)) == trueв MS C++:(atan2(10^9, 10^9—1) == atan2(10^9+1, 10^9)) == falseМой O(n^2 logn) зашёл, 270 мс на макстесте.
Ну, к примеру, можно отсортить все точки по x, потом написать процедуру solve(l,r,v), которая решает задачу для поддерева вершины v, используя еще неиспользованные точки, лежащие между l и r по иксу (в сжатых координатах). Эта процедура будет разбивать неиспользованные точки на отрезки с кол-вом точек, соответствующем кол-ву вершин в поддереве соответствующего ребенка v, а потом рекурсивно запускаться в этих отрезках.
UPD: упс, не зашло =(
А, собственно, как вообще её решать, раз то, что написал tunyash, неверно?
Будем рекурсивно отдавать точки вершинам дерева. Сначала одним DFS'ом подвесим дерево за вершину 1 и посчитаем размеры поддеревьев.
Сделаем рекурсивную процедуру, которая набор точек будет раздавать поддереву вершины x. Самую высокую точку из набора отдадим корню x поддерева. Относительно неё посортируем по углу все остальные точки набора векторным произведением (так как они ниже), и отдадим по очереди каждому сыну y очередные sz[y] точек. Тем самым мы гарантируем, что всё поддерево окажется целиком внутри угла с вершиной x, причём для разных поддеревьев углы не будут пересекаться. Победа!
Действительно довольно очевидно.
Физика затуманила мой мозг...
Казалось бы, твоё решение опирается на тот факт, что можно изначально положить первую вершину в самую верхнюю точку. Это же неправда.
Почему не правда? У меня такое же решение. Точнее симметричное. Я в нижнюю клал.
Правда. Почему неправда?
Например, потому, что может быть, у нас 5 вершин, граф звёздочка (причем центр звёздочки в вершине 1), а точки расположены так: 4 точки на одной вертикальной прямой и ещё одна справа от них (ниже верхней точки и выше нижней).
Никакие три не лежат на одной прямой. Это принципиально для решения.
Блиииииин =( То есть, я слил контест из-за неумения читать условия, понятно =(
См. ниже. Итого 22 место, вместо 5-го. Ты не одинок сегодня.
Ну, не факт, что оно не верно. Мне, во всяком случае, непонятно, почему, потому что, казалось бы, разбиение на отрезки всегда будет находиться и пересечений не будет. Возможно, я где-то накосячил. Может, кто-нибудь подскажет, где ошибка?
А как ты выбираешь корень для очередного поддерева из точек лежащих в сортировке по x на позициях с l по r?
Если каждый раз корнем выбирать максимум по y, то
Мм, да, действительно. Спасибо.
Да в лоб.
Подвесим дерево за какую-нибудь вершину и обозначим ее R.
Дальше возьмем самую левую и верхнюю точку, сопоставим ей вершину R и отсортируем по углу вокруг нее все оставшиеся точки. Заметим, что так как трех точек на одной прямой не бывает, то "равных" по углу точек тоже не будет.
Дальше у вершины R в дереве есть поддеревья, в которых N1, N2, ..., Nk вершин. Разделим отсортированные точки на группы соответствующих размеров, в каждой группе выберем корень (наименьшую в исходном порядке вершину) и запустимся рекурсивно.
Асимптотика
. Если сортировать по векторным произведениям, то очень быстро.
Есть идеи, как решать эту задачу быстрее? Мы не придумали, хотя кажется, что решение быстрее должно быть.
UPD: лажа!
Можно каждый раз выбирать центр дерева. Точнее вершину, такую что размер самого большого поддерева не очень большой. Это можно сделать за линию. Тогда казалось бы будет Nlog2NЧто значит каждый раз выбирать центр дерева? Ты его можешь только один раз в самом начале выбрать, чтобы за него подвесить, а дальше рекурсивный обход (из решений представленных выше) тебе однозначно восстанавливает, кто будет следующим корнем.
Не получается сделать вторую итерацию. Т.е. первой вершиной выбирается центр дерева, а дальше будет не та же задача, поскольку одно соединение уже фиксировано.
Ну почему, блин, сторого больший??? Ненависть!!! :(
Кто, где?
В задаче D. Там просят найти строго большую хорошую строку.
Можно же перейти к следующей и решать без "строго".
А, посмотрел твои попытки и понял причину негодования)
Ну просто нестандратно. А я как-то на автомате решал для ≥ , и за 5 минут не успел это заметить. А так-то ССЗБ.
150 и 250 место разделяет 10 баллов. Мило.
I wonder how many people just guessed the answer to div2-A, without actually proving it. (I got to a proof, after I finally submitted the guessed one.)
may you explain your proof?
If First player can place even one disc, answer is "First". Since first player can always win by placing first plate at center of board. Then he can copy the moves of second player . (Because there will always a similar space available due to symmetry)
WOW, nice proof :)
brilliant, love it!! so elegant!
за что дают вердикт "Попытка игнорирована"?
При перепосылке.
Этот неловкий момент, когда ответы одинаковые, но уже ничего не сделаешь ( Вывод 9/-2 Ответ -9/2
Happy birthdays dalex and I_love_natalia! The problems are nice. By the way, the start time is unusual, that makes me late for some minutes.
Actually, only I_love_natalia has a birthday today...
1 hour after contest is a football match in group A in Euro2012. In this group is Russia too :)
...I started the contest about 15 minutes later... To my surprise, I was in the top 20...... I had once thought that my rating would have descended dramatically... So strange...
Div1-A is exactly the same as SRM 518's Largest Subsequence, except that the constraint is larger... This might have given unfair advantage to those who have seen it before.
And there's also one task from COCI that's really close to it.
What is the intended algorithm for 196C - Нарисуйте дерево? How about flipping the pairs of intersecting segments and iterate until there are no more? Would this pass the time constraint?
In random order or flipping this makes about O(n2.1) operations, as I remember correctly. Too slow :-(
Кстати, задача похожая на А(Див.2) была на Саратовской командной олимпиаде школьников.
You will have to add a new level above IGM.
I think that the only way is to add 'tourist' level for tourist.
An extra problem, only for tourist... Almost half an hour he was free, after solving the five problems.
Aliens.
Проблема с задачей A(div2). Тест: 5 2 1 Ответ: Second У bmerry выводит First и полное решение. Если я ошибаюсь, напишите в чем.
Ответ верный, 1*2 <= 2 && 1*2 <= 5
Да, согласен. Если посмотрим на полное решение проверяется так.Но, попробуй на тетрадке этот тест написать. Объяснение: 1) Первый игрок на любое место может поставить тарелку. 2) Второй игрок по-любому может поставить тарелку.
3) Хоть куда 2 игрок поставить тарелку 1 игрок не сможет поставить тарелку.
Ставим тарелку в середину. Справа и слева остается по 1.5. Следовательно второй игрок поставить не сможет
Спасибо:) Блин, весь контест думал что кординаты целыми должны быть.
За контест думал над ней минут десять максимум, потом переключился на вторую и третью. А после дебажил почти полтора часа 4ую... А оказалось решение было в корне не верное :) Жалко, что до первой не допер, прикольная
аналогично не понятно, поч. в тесте 11 4 2 ответ First, а не Second int A, B, R; cin >> A >> B >> R; R *= 2; if (A < R || B < R) cout << "Second\n"; else cout << "First\n"; return 0; это AC код Если что в данном тесте можно понять, что тарелки можно ставить по абсциссе 2, и в не зависимости от координаты второй игрок может поставить ещё 1 тарелку
а,все, координаты не обязательно целочисленные.
Видимо, имеется в виду следующее: 1-й ставит тарелку так, чтоб её центр имел координаты (1, 2.5). После чего уже ни одну тарелку поставить нельзя
Все понял. Буду в след. раз тщательнее читать условие) Спасибо всем за ответы.
По условию знаменатель должен быть больше нуля.
Прочитайте условие ещё раз. Знаменатель должен быть положителен!
UPD: я чувствую себя JKeeJ1e30
Читайте внимательно формат вывода
"Иначе выведите несократимую дробь — значение предела , в формате «p/q» (без кавычек), где p — числитель, q (q > 0) — знаменатель дроби."
в задаче сказано, что знаменатель положительный.
UPD. опередили :(
... в формате «p/q» (без кавычек), где p — числитель, q (q > 0) — знаменатель дроби.
slowpoke.jpg
Напомнило: http://2005.novayagazeta.ru/nomer/2005/11n/n11n-s43.shtml
A — баян, была на SRM #никто-не-помнит-когда, B — баян, была на СОСИ-контесте, C — баян, я на нашем закрытом бобруйском сервере решал, D — баян, я в детском саду такими задачами девочек смущал, E — баян, я такое вчера выдумал по пьяни!
F — баян, я после чудо-травы за час до контеста ее решал?
И один лишь tourist решил их все.
А бояны тоже надо уметь решать. Вот на IOI-2011 дали боян на первый тур(17 сотен) и стандартоне упражнение на корневую(6 сотен) на второй тур. Хотя что боянистого, кроме задачи А, я так и не понял. А тупость и в африке тупость, и может быть немного бояном.
Ты еще про попугаев забыл — стандартам задача получения объекта по номеру, разбавленная неточной системой оценки.
Ну да. Это в той же степени упражнение, что и elephants.
Вроде, все более или менее нормальные задачи — бояны с каких-нибудь странных архивов или похожи на задачи с каких-нибудь странных архивов.
Например, на контесте УрГУ в Петрозаводске однажды мы "поймали" боян с городской олимпиады в Самаре 2001 года (вот эта задача)
Я еще помню свой разговор с кем-то, когда мне подряд предлагают 4-5 задач, а я говорю, что это было на таких-то школьных сборах. А то что на тимусе это стандартная гадость, которую понятно как решать, но надо сидеть и пихать.
На сборах пихать не надо было. На Тимусе немного weak tests и другой параметр декомпозиции заходит, вроде.
Upd. в 2009 это была не самая стандартная гадость. Бурундуки не сдали на сборах, вроде.
Не сдали, да... :-) Очень хорошо коррелирует с "На сборах пихать не надо было".
Если что, у нас тогда было решение за 2^{N/2}, просто константа слишком большая.
У меня сразу зашло после фиксов двух идиотских багов с long long.
На тимусе немного не weak tests. Говорю как человек, который сделал полмагистерской на генерации некоторых из этих тестов. (А также как автор единственного честного решения, зашедшего на сборах.)
Да, всё уже было в Симпсонах.
Баян — это типа халявная задача?
Баян — это типа музыкальный инструмент. А вот традиционный боян — сабж.
К сожалению, по возрастанию сложности не получилось :( А когда будет разбор, хотя судя по комментам то он не очень то и нужен?
Говорят, что Никита (Hohol) готовит. В комментариях, вроде, есть все, кроме D-1.
Спасибо за отличный контест)))
thankstosamarasauteddybearsforthiscontest
Спасибо, контест очень понравился и не обнаружила лично для себя ни одного бояна.
Hello, I suppose it's better if you use just ordinary math. not something that like limit. I don't have any information about it. It's better if you would use some algorithmic problem or other problems related to programming instead of pure math. just my recommendation. I'm not a very professional participant. just participating here and don't know about other places. it's just a recommendation. and anyhow I appreciate your hard work for creating such a great contest. thanks.
Actually, the solution was given in the link below the test cases explanation.
really liked the content, although i found it difficult. particularly task A, which in my opinion was rather the hardest than the easiest... good job, guys!! :)
Так всё же, в D неправильно делать так: найти сначала первую позицию, где всё плохо, и сказать, что всё до этой позиции мы оставляем (ну или пробуем максимум ещё один символ удалить — на всякий случай), в эту позицию мы перебираем что ставить, а дальше восстанавливаем минимально-жадно (в некотором роде перебором с откатами)? Нечёткое место тут, кажется, одно — это то, правда ли можно оставлять без изменений всю строку до первого палева.
Иногда в переборе с откатами (если я правильно понял, что это) надо откатываться левее первого палева: 2 ayzy. Но, казалось бы, такая ситуация не может возникнуть больше одного раза, так что все хорошо. Сам я не сдал, могу ошибаться.
А, всё, понятно, где это палится. На таком простом тесте:
"10 azzzzzzzzzza" (буква z повторена 10 раз)
Первое палево случится на последней букве z, однако чтобы получить ответ, надо будет откатиться аж до буквы 'a'. Да, надо было всё решение оформлять в виде этого "перебора", или же как-то умно перескакивать назад к последней не-z-букве.
UPD перебор зашёл, видимо потому, что такие длинные откаты нужны только один раз.
Any idea why my practice solution for div1 E TLEs (http://codeforces.net/contest/196/submission/1798783 ), while RAVEman's (slightly modified version: http://codeforces.net/contest/196/submission/1798819) easily passes? Both use Prim's algorithm in almost the same way. I went over his code line by line and can't find the key improvement.
I found 2 reason. 1. set is slightly slow than priority_queue so you solution take much more time. 2. test case is not strong enough. the way you choose start vertex is different from RAVEman (Reminder : portal might not be in order in input), he's lucky so choose largest portal number pass in time, but choose lastest portal number (in input) not.
After I fix #2 in your code to the same way as RAVEman , it's TLE at test case #39 1799522 and after I fix both #1 and #2 it's pass in 300 ms
UPD. fix font size
That's bad, I was too imprudent :( These solutions get TLE on 'reversed' test 36 where any vertex i is renamed to n - i + 1.
UPD: New tests (76-95) were added. Try to pass them.
Thanks!! I'm surprised set vs priority_queue would make such a big difference. TopCoder's STL tutorial says "the difference is about ~%0.1 of time", yet RAVEman passed test case #39 in only 50 ms. When I tried his code with set 1798838, it failed case #39.
As for the other reason, it seems the problem is that non-portal vertices can be visited multiple times. I haven't thought of a solution for this yet...
Actually, the set vs priority_queue issue might just be another vertex ordering problem in disguise. Submission 1801347 also fails case #39 even though the only change from the "modified RAVEman code" in my first post is changing the priority_queue< pl > to a priority_queue< pl, vector< pl >, greater< pl > >.
Alright, someone explained the real solution so I went ahead and implemented it! The trick is to make a sparse version of the graph of vertices which have portals. The "edges" in the portal MST will be shortest paths between pairs of portals in the original graph. There could be n^2 of these, but we don't actually need them all. MST edges are always minimum weight among edges in some cut of the graph. This solution is guaranteed to include all such edges.
Yeah, I just got lucky. I had just 15 minutes after I submitted D till the end of the round, so I decided to submit the most stupid solution that I could think of...
Usually that strategy works pretty well for me :)
And thanks for noticing the crap I wrote. This made me read the editorial to understand the intended solution.
Defeating the judge in 10 minutes is quite amazing ;)
It's nice to see a growing community around programming competitions; I still have lots to learn from all of you! (this was my first time coding MST)
In Div-2 Problem-B:
Test Case: 8
Why the answer is "-Infinity" instead of "Infinity"?
Look at this: Evaluating limits at infinity for rational functions
Because n > m and a[0] * b[0] < 0
You can simply draw a chart ;-) for example for x in ( 10, 30, 100, 300, 1000 ).
Разбор задач скоро появится?
Input
cantouristsolveitlessthaninoneminute
Output
unfortunately, he can't
but he solved all problems less than 100 minutes
/*found my mistake*/
right