Всем привет!
Рад пригласить Вас принять участие в раунде #115, который является рейтинговым для участников обоих дивизионов. Как и год назад, в этом раунде Вам предстоит помочь геймеру Васе cориентироваться в виртуальном мире компьютерных игр: похвастаться перед друзьями своими достижениями, определить кто "нуб", а кто "хардкорный" игрок, уничтожить Главного Злодея, сыграть пару раундов в Plane of Tanks и разобраться с толпой очень плохих гномов. В общем, получить массу удовольствия!
Авторами контеста являются Геральд Агапов (Gerald), Евгений Лазарев (undef) и Алексей Шмелев (ashmelev). Помощь при подготовке раунда оказали Владислав Епифанов (vepifanov) и Мария Белова (Delinur).
В этом раунде Вам будет предложено 6 задач, вместо обычных 5, а так же продолжительность увеличена с 2 до 3 часов.
P.S. Вы наверно все заметили странное соревнование под названием: "RazMERiq 2012 (Private Contest)". На базе проекта Codeforces и задачах этого раунда пройдет онсайт-соревнование в Нижнем Новгороде (большое спасибо Михаилу Мирзаянову за предоставленную возможность!). Регистрироваться на "RazMERiq 2012 (Private Contest)" для участников раунда #115 не надо :)
UPD: в этом раунде будет использована динамическая стоимость задач.
UPD2: ввиду неточности условия в задаче 175B - Plane of Tanks: Pro и последующего исправления условия, пожалуйста, сообщите Gerald если Ваше решение упало на 4-ом тесте исключительно из-за поправки условия. В сообщении укажите номера посылки.
UPD3: разбор задач.
А станут ли когда-нибудь private-контесты обычной вещью? Было бы классно создавать свои запароленные контесты/тренировки, чтоб проводить собственные соревнования здесь, на Codeforces.
Это наша идея! Не примазывайтесь ;-)
По-моему, эта идея возникла чуть ли не с момента образования Codeforces. Странно считать ее своей.
Вы договариваетесь о контестах с администрацией, а хотелось бы, чтобы все происходило автоматически; думаю, что добавить функционал запароливания тренировок не должно быть сложно
Это была лишь шутка. Думаю, что смайл в конце на это явно намекает.
Конечно же, возможность проводить контесты на платформе Codeforces очень удобна! И она явно бы поспособствовала развитию олимпиадного движения там, где нет инфраструктуры для проведения соревнований. И я уверен, что такая возможность появится рано или поздно.
А вообще, я был приятно удивлен, что администрация пошла нам на встречу и сделала отдельный контест для онсайта. Удивлен потому, что CF с этого ничего ровным счетом не имеет (кроме лишних проблем с организацией и информированием участников где надо регистрироваться а где нет:) ). А нам позволит провести онсайт по интересным правилам (не достаточно уже приевшимся правилам ACM ICPC), на высоком уровне и при минимальной головной боли связанной с технической составляющей соревнования. Спасибо им еще раз за это!
тык
если не секрет, какой смысл в закрытых тренировках? Или я не так понял "private-контест"?
Закрытые тренировки нужны, чтобы в мониторе для онсайт-участников присутствовали только онсайт-участники. А потом, после проведения, тренировку можно будет сразу же сделать доступной для всех
What is the meaning of private contest?
I mean who can participate in that contest?
It is for onsite participants. You should register on Codeforces Round 115, it will contain exactly the same problemset.
разбалловка задач ???
Разбалловка будет завтра.
Знаю, что, наверное, заминусят, но, блин, 12 часов — это же так рано >_<
Видимо из-за онсайта — их обычно рано проводят.
Причина не важна, важно следствие — контест в 12 часов, из-за чего не смогу в нем участвовать :\
Топкодер в 6 часов — нормально, а КФ-раунд в 12 — рано. Где логика?
А топкодер-то тут причем?) Где логика?
Совпадает со вторым туром РОИ, что, мягко говоря, совсем не удобно для участников :(
Will the problems be ordered by expected difficulty?
Yes.
UPD: Sorry, my initial comment was not true. The decision has not been made yet.
I think its time to make a decision.
Yes, the problems are ordered by difficulty.
По субъективной оценке жюри, задачи будут располагаться в традиционном порядке возрастания сложности или же случайном?
It will be rated round?
Yes.
It is explicitly written in the post.
почему в Б поменяли условие? Если мне кажется, что я сделал плохие попытки из-за этого, виноват остаюсь я?
Пожалуйста, обратите внимание на UPD2 исходного поста.
I cannot DECODE the statement of problem B...
У меня не заходит на турнирную таблицу.
UPD. Уже все ок.
Можно уже говорить "спасибо" авторам за идеально сбалансированный проблемсет, или еще подождать до окончания контеста?
думаю, можно еще за всякие правки в условии по ходу раунда...
Нормальный раунд. D и (особенно) E, на мой взгляд, — очень интересные задачи. +Претесты не очень сильные, а значит все, кто исчерпал свои возможности в решении могли вдоволь ломать других. Что плохого в том, что для 80% участников много решит скорость и взломы?
Для большинства контест превратился в "кто быстрее отрешал три халявы и не облажался по тупости", а это не есть гуд.
Время от времени, и такое имеет место быть, не так ли?
вроде не говорят, что такого не бывает. говорят, что это не совсем хорошо.
Да, такое бывает, впрочем, хорошо бы стремиться, чтобы такого не было.
PS: Я с шашкой наперевес на авторов не бегу.
Что ж, все 3 мои решения уже прошли систесты. Следовательно, "со стороны" выглядит так, будто для меня соревнования закончились на 25 минуте. Есть еще дополнительные условия, мол "я решал четвертую, решил идейно правильно, но не смог отдебажить быстрые переходы в динамике, чтоб проходило 5000-10000 итераций, а не 100-200", и все такое... Но это все уже детали.
Грубо говоря, я прорешал все, что мог, за 25 минут. И у меня, наверное, будет даже плюс к рейтингу.
Если кто-то считает, что это нормально, когда контест длиной 3 часа достаточно решать 25 минут — что же, это его мнение, у него есть на это право...
Юбилейный 88000 комментарий. Мелочь, а приятно:)
А какая итоговая сложность? Ведь вроде быстрее O(HP1 * HP2 * D * (R-L)) нельзя. Итерации уже некуда лепить.
Не знаю верное ли это решение, но можно две динамы и тогда получится
(HP2+HP1)D(R-L)
Я пытался сделать (HP2+HP1)D на динамиках (т.е. считаем для обеих вероятность того, что после a выстрелов у танка остается b жизни) и потом D*D на подсчете ответа (в динамике сразу считаем вероятность убития на определенном шаге, потом перебираем все возможные пары "первый убьет второго выстрелом А (если доживет), второго первого выстрелом В (если доживет)).
Тут D — число итераций.
Я писал что-то такое же, только ответ не за D*D а просто за D.
Что-то типа считаем вероятность убить за k шагов, умноженную на вероятность дожить до k-го выстрела.
Не пропихнул, думаю есть косяки, ибо я сперва думал они в 0 еще не стреляют и потом уже исправлял. Такое решение как минимум на 3 теста дальше пихалось)
А можно и без итераций. Мне, правда, один символ надо было в решении поменять, чтобы прошло. Но у меня сложность O(HP1 * HP2 * 30 * 2 * 30 * 2).
У меня нету итераций. У меня HP1 * HP2 * 30 * 2
Там система за линию решается?
Да, там нужно было выразить один элемент, а потом просто пройтись и почитать все остальные через следующий. Выразить можно просто: постепенно раскрывая скобки.
Код: 1536975
Ясно, я за квадрат делал оптимизированным Гауссом. Работает всего в 2 раза дольше :)
В переводе это означает "_у меня 35 место, самое высокое в моей жизни, ну не могу же я обливать грязью такой контест_".
Мы поняли)))
А тем временем оценка поста о матче тонко намекает на мнение сообщества...
Codeforces Round #114: +207
Codeforces Round #115: +44
feel the difference
Радует, когда узнаешь, что за тобой следят люди. А вообще, думаю, ты понимаешь, что мне не составит труда (довольно логично!) объяснить мотивацию твоих постов, начиная со слов "в переводе это означает...".
Да, к сожалению, таких участников очень много. Авторы контеста считали, что задачи D и E сдаст намного больше народу, а лидеры решат первые 5 задач за 1.10-1.30 и смогут что-нибудь с F сделать. Сложной теории в D и E знать не надо, реализация тоже несложная, поэтому задачи вполне по силам даже некоторым участникам второго дивизиона. Однако, реально сложность этих задач оказалась выше, чем мы полагали.
E — просто зашкаливающе интересная задача, перебор с (!) неасимптотическими оптимизациями. Какая красивая и новая идея, просто rocket science :)
Пожалуй, не буду в очередной раз разводить холивар про идейность задач. Хотя в целом идейность этого контеста выше среднекодфорсовской, но ниже того, что я считаю "правильной" идейностью контеста.
Мне, как любителю ТД, понравилась сама задача:) Плюс ко всему, я реально не знаю как оптимизировать в этом случае перебор. После контста будет разбор, а значит там напишут, как все-таки оптимизировать ее, а значит я научусь чему-то новому. Как это может не радовать участника моего уровня?
Авторское решение задачи E не требует неасимптотических оптимизаций и использует пару идей кроме полного перебора. Собственно, и разбор для этой задачи получился самым большим (из A-E).
Если хочется больше идей в контесте — то как раз можно подумать над более "честным" решением вместо написания перебора, который не гарантируется, что пройдет :)
What's the idea behind problem C?
Just use greedy approach:)
I tried always picking the figure that would give me the smallest number of points if I take only a number of them that would take me to the next p_i. This failed.
UPD: You need choose just the least thing by cost.
Thanks! That was my first thought too, but then sent a solution with that idea and failed. Turns out that I understood the statement wrong: I thought that if p_1 = 1 and p_2 = 2 and I destroy 1 figure then I need another 2 figures to reach p_3. But yeah, they are cumulative.
What is the solution to problem F? I tried to solve it, but i got TLE on pretest 7( I used dijkstra algorithm for every query )
That's way too slow. You'd need something around O(n log n) or O(n log^2 n) or O(n sqrt(n)), not O(n^2 log n) ;)
Ребята, вы не поверите. Мне наконец-то надоело учавствовать в соревнованиях! :-) Объявляю передых.
Забьёшь на GCJ и TCO? ;)
Посажу девушку писать за себя =)
Прознают и зобанют. Обоих.
Все в порядке, это была шутка ;)
Как это может вообще надоесть? :-)
Всё, передохнул. Пойду писать GCJ.
"Don't be a slowpoke" round :),
btw I liked it.
Btw, I hated it :). On an ordinary round there wouldn't be such a huge difference between our places.
There probably should be a medium problem (between C and D in difficulty). Otherwise, for the people who solve ABC, it boils down only to speed.
а что меняла поправка во второй задаче?
прохождение 4 претеста из-за условия. Надо было поменять <= на < или наоборот
да просто у меня получилось, что решения до правки условия и решение после правки проходит все тесты. а я, дурак, делал перепосылку...
There is a bug in standings. I can't view them in each division separately.
хм... странно в ABC Паскале выводит -1, в FPC — WA 1000001
Используйте FPC на своей локальной машине, и да будет Вам счастье :). А еще лучше сразу меняйте язык на что-нибудь более приличное.
P.S. Желающим помянуть про Гену: я это уже сделал за вас.
Другие языки не спасают от толпы компилятров(или вы только ТОТ САМЫЙ язык приличным считаете?)
Намек про смену языка — это уже лирическое отступление, не имеющее никакого отношения к проблемам с компиляторами.
Юзаю ABC потому что там проще копипастить готовый код и сохранять программу, да и загружается он быстрее дельфи. Хотя имеются в наличии все три компилятора.
А рейтинг будет пересчитываться по отдельности для див-1 и див-2? Исходя из расстановки по комнатам, логично предположить, что да. Но всё же...
Несмотря на то, что я слил, контест очень понравился. Спасибо.
P.S.
const int MAX_AMMO = 40000; -> const int MAX_AMMO = 10000;
TL -> AC.
Хоть кому-то понравился :)
Задача C для тебя была проще, чем для большинства остальных участников, не так ли?
А зачем закрывать результаты приватного контеста?
I'm not looking for excuses, but the statements are really hard to understand sometimes. Examples:
Problem A: "In the first example the best result, obtained by artem is ..." (This would make you think that artem obtained the best result) They probably meant "In the first example, the best result obtained by artem is ...". (For me, that comma makes a difference)
Problem C: "The number of figures of type ki and figure cost ci is known for each figure type" (I first thought that ki was a type.) I think it should have said "The number of figures of type i is ki and they all have the cost ci"
Or maybe it's just me and in that case I apologise.
Really love problem E: Tower Defence. I think people who have played it before may figure out the solution very soon -- at least true for me.
Warcraft III rules! :)
One of the unluckiest contests for me happened like this:
Problem D: I did a DP solution plus binary search. Got Wrong Answer for forgetting '<' should be '<='. Even worse, after fixing that, this code got TLE and adding inline optimizations saved the day.
Problem E was even more unfortunate. When I was reading this problem, the Internet connection in my room went down. After trying in 10 minutes but no avail and 3 unsuccessful attempts in finding a wifi connection, I hurried to my university (it is about 500 meters far from my room). Finally, it was 30 seconds too late before I was able to submit my solution (quite close to the expected solution, although it was wrong anyway).
Now I see how difficult it is to reach Grandmaster Level (or red) in Codeforces. Not only do algorithmic skill and coding ability are required, your physical condition must be good as well :)
Anyway, I really like this contest (15 rating loss is not a big deal) because it brought me a memorable day :)
(http://www.codeforces.com/contest/175/submission/1533074) A bit unlucky. In problem A I used atoi to convert string to number and check if it is greater than 1000000 like this atoi(a.c_str()) > 1000000. The problem is if the number is out of range atoi returns INT_MAX or INT_MIN. In my system it was returning INT_MAX, so it passes all test cases, but in codeforces i think it returned INT_MIN and someone hacked my solution. Anyway how do you hack someone's solution if the behavior of some function is undefined?
There is "Custom test" tab
For problem c, my submission is giving the wrong answer for the first test case. But in ideone and my system, it's giving the correct answer. What the problem? (http://www.codeforces.com/contest/175/submission/1535400) (http://ideone.com/dUFwZ)
I'm using Dev C++, and my system also have an incorrect output for that code. It seems that after the second loop, when the p is 6 and the nFigures is 2, the value of i is 1 (i++). Now, i>=SZ(v), but since we're still in the while(p>0) loop, and p is still greater than zero (value of p is still p-nFigures = 4), it won't break the while(t--) loop. So, in would access the value of v[1], which doesn't exist.
Или я слепой, или где разбор?
Мог бы хоть кто то мотивировать, за что минус ставит?
p.s. Или все из за того что все привыкли к хорошему (к разборам в течении 10-15 минут после раунда, иногда даже до систестов).
По-моему, это ты слишком привык к хорошему и все тебе подавай, не?
Вы хотите сказать что это только я к хорошему быстро привыкаю?
Опубликован разбор задач A-E
Are there any editorials for this round?
Editorial for problems A-E.
Thanks very much. :)
Вопрос: теперь все раунды будут проходить с динамической стоимостью задач?
И будет ли в таком случае применяться к задачам random_shuffle?
Вообще, идея хорошая, избавит комменты от бесконечных вопросов вида: "какие баллы за задачи?".
Может, стоит отныне давать автору контеста выбирать способ разбалловки?
Опубликован разбор задачи F
Having a weird behavior with C++0x over here in problem B.
I have submitted those 2 codes: 6314097 & 6314111, one of which got a WA and the other got accepted, the only difference was the line
cerr << better << " " << least << endl;, which should not affect the output, not the variables. I tried to know why that might happen, but seems to hit a dead end.Any clue to what I might be missing over here.
That's probably precision issues.
1.0 / 10.0 != 0.1, at least, you shouldn't assume that and always compare doubles assuming that each number can be stored with some small error only. For example:UPD: usually (un)commenting debug output affects optimizer, which can easily affect precision of floating-point operations.
See this for why this can happen: http://www.parashift.com/c++-faq/floating-point-arith2.html