Рада пригласить всех принять участие в очередном раунде.
Автором задач сегодня являюсь я. Мы с Артемом Раховым, Марией Беловой и Дмитрием Матовым постарались приложить все усилия, чтобы сделать задачи как можно более надежно.
Надеюсь, задачи окажутся для вас интересными, соревнование динамичным, а сильные участники быстро справятся с задачами и помогут новичкам отловить все баги своими взломами :)
Удачи!
P.S. Фраза "сильные участники быстро справятся с задачами" ни в коем случае не означает, что все задачи будут простыми. Не забывайте читать условия и тестировать свои решения!
UPD. Соревнование завершено. Поздравляю Kenny_HORROR с победой!
UPD2. Добавлен разбор задач. Несмотря на рекордное число участников, система во время раунда работала без сбоев. Спасибо команде Codeforces! Всем, кто принял участие в раунде, тоже спасибо.
Таки побили.
"Не забывайте читать условия"
=)
Так, надо запомнить, а лучше записать, кто это сказал, на случай, если окажемся в одной комнате.
Ещё раз браво!
По скорее бы разбор
две задачи и 34 взлома больше, чем 4 задача и 4 взлома
Каюсь =). Не смог преодолеть соблазн...
PS: Еще 1 довод в пользу того что синие должны быть в Div. 2 =).
Поздравляю с покраснением.
А мне теперь даже стыдно - в итоге не прошла ни одна задача, а я на 70 месте и +88 рейтинга...
320560 05.03.2011 20:59:59 Romka
на последней секунде успел =)
int ron = -1;
int val[] = {e, f, a, b, c, d};
for (int i = 5; ron == -1 && i >= 0; i--)
if (val[i] == 0)
ron = (i & 1) == 0;
if (ron == -1)
ron = b * d * f > a * c * e;
printf("%s\n", ron ? "Ron" : "Hermione");
I don't know if it is easy,but my last idea (which got accepted) was just to simulate the process of transformations:
double process(double x,int a,int b)
{
if(a==0 && b==0)return 0;
if(a!=0 && b!=0)return x*b/a;
if(a==0 && b!=0)return 1e+100;
if(a!=0 && b==0)return 0;
}
t0=c,c>0
then t1=process(t0,a,b);t2=process(t1,c,d);t3=process(t2,e,f).
if we have a lot of gold after 2-nd step(t2>1e+50),or more sand then it was before after the 3-rd step(t3>t0),then Output=Ron
double p=1e20,ng,pg;
for(i=0;i<5;i++) {
j=i%3;
if(fm[j]==0) {
if(to[j]) {p=pow(10,k);k+=20;}
else p=0;
}
else p=(p*to[j])/fm[j];
if(i==1) pg=p;
else if(i==4) ng=p;
}
if(ng>(pg+1e-6)) puts("Ron");
else puts("Hermione");
UPD. Хотя нет, зря я так резко. Контесты с такой задачей A ведь редко бывают. Вот и на TopCoder тоже - я точно знаю - они такую веселуху устраивают раз в полгода. Так что в среднем-то ничего страшного.
А качаться когда? :-D
И, по-моему, тут ему повезло. Это был, возможно, самый интересный контест на CF, если наблюдать за ним со стороны. Но потерять сотню баллов рейтинга
в такой лотерее, например, потому что решал, а не взламывал, было бы неприятно."1000 999 1 1 998 999"
Или я пропустила.
Я им ломала решение, которое много (10^7) раз симулирует процесс (начиная с одной песчинки) и проверяет в конце, что получилось много золота (10^5).
А на взломах решения все еще не тестируются?
Необычно большое число челленджей для контеста codeforces. Я даже слегка удивлен почему люди которых я челленджил по задаче А умудрялись только залатывать 1 дырку и даже сильно тратить время на то чтобы подумать все ли они учли.
Жаль над D и E нормально подумать не успел.
Все задачи на всех контестах всегда на интуицию.
?!(всмысле как идея так и фактически само решение) не проходит 66 тестведет себя так же, как и описано в разборе.Но все же _такими_ задачи делать не следует, под 40 взломов у некоторых людей - можно ни одной задачи не решать и быть высоко вверху.
В задаче C очень хитрый 5-ый претест. Что-то вроде
1
-1 2 0
1 2 0
2 1
0 0 0
Т.е. на краях он не дойдет, а в центре дойдет. Поэтому я делил каждый отрезок на 2 части, а потом бинпоиск.
Жаль, что лишь за 10 минут до конца мне это пришло в голову. Там может и D сделал бы...Ой, похоже, что такого действительно не бывает. Неужели тогда из-за точности не прошло первое решение?
Ничего себе "очень хитрый". Если б он только на краях догонял с минимальным временем, то задача б легче чем А была =)Мы же за олимпиадную карьеру изучаем сотни алгоритмов; почему бы один раз не запомнить вместо очередного алгоритма, например, как хранится вещественное число, и не прорешать на это несколько тренировочных задач?
Считаю, что среди перечисленных ниже примеров нет сильно более или менее важных для (спортивного) программиста:
1. Как эффективно реализовать суффиксное дерево или min-cost-max-flow.
2. Как вещественные числа хранятся в памяти.
3. Почему, если какой-то простой перебор делать циклом вместо рекурсии, программа работает в разы быстрее.
Лотерея разве что в распределении по комнатам. От него, в общем, зависят и баллы за взломы, и насколько быстро вам помогут найти тупой баг в своём решении.
UPD: С 1e-9 у меня все тоже прекрасно проходит.
Действительно, когда мы догоняем на длинном отрезке, почти параллельном нашему отрезку из начала пути, с точностью нужно быть очень аккуратным.
YatsukoYin, только без обид, ничего личного :)
Или Вы это про успешно сданное недоказанное решение?
А я всегда говорил, говорю и буду говорить, что гордиться тем, что ты чего-то не умеешь, - нелепо. (Другое дело, что можно сказать, что считаешь более целесообразным тратить время на раскачку других скиллов.) Вот я не умею читать по-древнегречески. Мне стыдно.
Блин, в следующий раз нужно внимательнее читать условие.
Почему-то подумал, что превращение в золото-3 пара чисел=((
2. Submit A.
3. Lock A.
4. Realize A is wrong.
5. Hack all the wrong submissions of A.
6. Don't be able to write even B!
7. Solve 0 probs, make some hacks, ... +24 to global rating. o_O
8. ????????
9. PROFIT
Fuck Yeah)))
(P.S. My algorithm is a little bit different; I employed equation-solving approach whereas many others used binary search.)
To my understanding, the point is that, different quantities (e.g., parameter in segment, time, angle in radiance, length, area, ...etc) have DIFFERENT ORDER of magnitudes. If the test data are sensitive to precision, making a "correct" choice of EPSILON could be difficult. (Or even, I would say, it requires luck.)
Some problems (in various contests) will state explicitly that, you may assume that small precision problem will not affect the solution. But it seems not the case here...
I guess (and I hope) problem setters do not intend to include estimating good values of EPSILON as a part in Problem C. I am not blaming the problem/test setters, and in fact this problem is well set and interesting. But I hope that next time they could take care of this issue.
Please share with us if you have any insights. I suspect quite many algorithm coders, including me, find precision problem annoying before...
1
0 0 0
0 100 0
100 100
0 0 0
Приблизительно как семплы на топкодере.
1. Я не знаю, как полностью решать задачу, но знаю к ней хорошие тесты. Сейчас, чтобы получить возможность её ломать, нужно преодолеть претесты — неизвестно какой набор тестов. Для большей определённости хорошо бы либо сделать такое поведение вообще невыгодным (например, снимать все положительные баллы за взломы упавших задач), либо пояснить, что содержится в претестах.
2. Я сдал и заблокировал задачу, а потом придумал к ней хороший тест (крайний случай) и пытаюсь найти соответствующий баг, читая чужие решения. Если этот крайний случай есть в претестах, окажется, что я зря теряю время.
Угадать, какие тесты в претестах есть, а каких нет — навык существенно отличный от обычно применяемых (решение и тестирование задач).
вообщеиногда невыгодным.Т.е. либо самому нужно написать TL чтобы взламывать себе подобных, либо писать правильное решение.
А ещё тот, кто первый на 00:01
пройдёт претестыотправит чушь по всем задачам, нехило получит, когда на 00:02 и далее кто-то подобный тоже отошлёт такую же чушь, как и первый.Ну думаю идея ясна.
UPD. Codeforces формат и в том числе претесты на мой взгляд сделаны для большего количества fun'а на контестах, поэтому всё нормально. :-)
Думаю, достаточно будет запретить повторный взлом участника по той же задаче.
Хотя, так CodeForces потеряет некоторую "изюминку"...
Наверное пусть участник, который послал палево по задаче и залочил его, получит возможность хоть на хаках отыграться - не зря же он лочил? Иначе слишком большой дисбаланс в сторону тех, кто изначально правильно решил задачу.
Те, кто сдал задачу правильно с первого раза получают нехилый профит в очках. ;-)
«Что TopCoder, что CodeForces - оба учат быстро и правильно писать с первого раза. Надо с молоду запоминать чему равна цена ошибки.» - Ну так и GCJ тоже. И ежу понятно, что это ближе к промышленному программированию, чем ACM формат.
UPD.
Кстати насчет смолоду. Школьные олимпиады точно не учат писать правильно. Часто бывает достаточно хорошей заглушки с парой костылей - плохой способ для прививания молодёжи. Впрочем они ещё школьники, может с ними можно и помягче (да простит меня Ферлон).
У студентов же формат ACM: послал палево система сразу тебе пальчиком погрозит.
А вот TC, GCJ, CF (HC) - вот они учат думать правильно и сразу. Порадуемся же этому.
TopCoder forgives NO mistakes ]:->
Я на TopCoder однажды ACRush'а чуть не свалил - не хватило двух секунд буквально на кнопочку нажать, челлендж-фаза закончилась. А челлендж-то был правильным, я его тут же в чате попросил проверить.
Мне очень интересно, кто после этого чувствовал себя большим неудачником - я или он...
На школьных тоже непонятно, какую задачу насколько решать, но там хотя бы можно не задумываться, в каком порядке это делать.
Ну так да, правильнее будет разбиться головой об стену и застрять на первой задаче. :-)
</irony>
Спасибо автору за раунд!
First examine the second rule, then the first and the third ones.
If c is 0 but d isn't, it means you can gain gold by no cost. => R
If d is 0, no matter what c is, it means you can never gain gold. => H
If c and d aren't 0, in the same way to think about first and third rules.
If a is 0 but b isn't / e is 0 but f isn't, it means we have infinite resource. => R
If b / f is 0, no matter what a / e is, it means that our resource will be exhausted. => H
Finally, if no number is 0, it's just an easy math problem.
It seems that many people gain lots of hacking score by problem A.
It contains some basic consideration in our daily life.
We should just calm down to think about it, instead of being nervous or careless and then promiscuously guessing the answer.
Input Mine Answer
5
1901 1001
1166 1066
1308 1108
1037 1137
1808 1208
Correct Output:
No solution
интересно кто не поленится все это читать???
=)
По поводу задач.
Cпасибо!
tl;dr: great job, organizers! I definitely look forward to the next match.