Всем привет!
Одним из авторов Codeforces Round #152 являюсь я.
Также авторами Codeforces Round #152 являются студенты Национального исследовательского Томского политехнического университета: am-real и max777alex.
Задачи Codeforces Round #152 будут посвящены литературным произведениям, отечественным кинематографу и мультипликации.
После всего вышесказанного авторы раундов обычно рассказывают о себе или пишут о том, что это — их первый раунд. Я не буду заниматься тем же самым, ведь существенной части сообщества Codeforces и без того известно, кто я такой. И мне даже интересно отношение количества смешлявых репризок в комментариях до и после раунда. Они только приветствуются.
Стоит, как обычно, поблагодарить тех, кто помогал нам готовить этот раунд. Спасибо Gerald за помощь в подготовке раунда. Спасибо Delinur за перевод задач на английский язык. И особенное спасибо Seyaua и sdya за то, что они согласились (ценой собственного времени) вычитать и прорешать задачи.
Обратите внимание, что раунд состоится 25 ноября в 19:30 по московскому времени.
Разбалловка div1: 1000 1000 1500 1500 2500
Разбалловка div2: 500 1000 2000 2000 2500
Контест окончен.
Мы приносим свои извинения за двусмысленность, допущенную в условии задачи A. Не было ясно, можно ли касаться штанги в момент, когда мяч пересекает линию ворот. Тем не менее, оба понимания условия проходили. Эти решения отличаются на бесконечно малую величину. Единственное, на что это оказало непосредственное влияние — взломы. Все взломы, которые базировались на утверждении о том, что касание штанги в момент пересечения линии ворот невозможно, будут удалены. Пожалуйста, те, кто делал такие взломы сообщите об этом Геральду Агапову (Gerald).
Мы также приносим свои извинения за перебои в работе сервера и сбои при отображении условий.
Далеко не единогласным решением жюри было решено сделать раунд рейтинговым. Рейтинг будет пересчитан 26.11.2012 после того, как будут удалены все соответствующие взломы.
Опубликован русскоязычный разбор задач раунда.
Разбалловка стандартная?
Понятия не имею. Про разбалловку если и будет что-то известно, то только непосредственно перед раундом. Я всегда был, есть и буду сторонником того, чтобы не расставлять баллы за задачу согласно субъективному мнению кучки людей. Свои соображения о сложности задач я уже сообщил администрации. Администрация проекта сама решит какую разбалловку применить.
В таком случае хотелось бы попросить администрацию разбираться с разбалловкой пораньше, т.к. фан от контеста в зависимости от системы оценки различается.
Да какая вообще разница, что за разбалловка? Ну скажут, что первые 2 задачи будут по 1000 баллов, от этого что-то изменится? Все равно, те, кто собирались писать контест — будут его писать, а те, кто не собирались — не будут.
Разве что, особо ярые противники динамической системы оценки могут забить на контест, узнав об этом. Но я, например, хоть ее тоже терпеть не могу, не стану пропускать контест только из-за этого.
"Разве что, особо ярые противники динамической системы оценки могут забить на контест, узнав об этом." — это и имею ввиду. Даже просто не любители той или иной системы оценки могут предпочесть контесту другие дела.
Лично мне все равно, какая система, но я не вижу причин, по которой о системе оценки надо думать вплоть до последних минут.
Предсказатель :) (A=B=1000)
lets fun :))))
These contest on weekends are better for everyone. Everyone can participate. Good luck :)
open to all users??
Only for Div 1, Div 2 and Unrated users :)
Oh yeah, unfortunately, for only people :/
men. the contest was supposed to be at 12:00 (as i remember), so it is at 30:00 in VN. now it is at
19:30 (22:30 in VN, it means we do it til midnight). Can anyone tell me why the schedule is changed?
There are always some countries where contests start at 1AM, 4AM... While you don't have the ability to create a contest on your own, live with it :)
The main reason is that it is the most convenient time for admins and writers to take care of the contest.
This time it's because Opencup — very popular contest in Russia — will be held tomorrow at 11.00 MSK.
Nope. In Russian branch of discussion I've explained that another popular Russian contest was scheduled for the same time. Many Russian programmers want to have an opportunity to take part in both contests.
ok. i've got it. thanks
so it is at 30:00 in VNhow many hours do you have in Vietnam :P ?how many hours do u want?;)
А почему так рано анонс? Обычно его вывешивают-то за 5-6 часов до раунда.
Я считаю, что так ещё лучше.
Мне кажется, что из-за изменения во времени
Я тебя даже плюсанул за сообразительность. Сразу напишу причину переноса, чтобы по сто раз не спрашивали. Соревнование было запланировано давно, и время было строго определено как 12:00 по Москве. Но тут вмешался OpenCup со своими переносами и испортил нам все планы. Теперь имеем то, что имеем.
Достаточно ранний анонс с:
Хорошо, не та ветка
Мне почему-то кажется, что этот вопрос:
А левый аккаунт для таких коментов создавать зачем?
Вы конечно молодцы что перенесли раунд, но я уже второй раз попадаю из-за позднего оглашения окончательного времени проведения раунда. Можно быть немного независимыми и проводить соревнования одновременно с другими. Вы ведь всем угодить не сможете? А кф пишут и за пределами Росии, где даже не знают о существовании опенкапов!
В общем-то время ставит организатор контеста. Когда ему удобно, тогда и раунд, а если что-то не устраивает с временем, то кто мешает создать своей раунд?
свой раунд сам не порешаешь
Что б там не говорили, любой контест — это классно!Всем удачи
ints 00:55:00 before start :)
Такое впечатление, что люди пишут претензии лишь потому, что они должны быть) Вот пусть есть некоторое процентное соотношение придирок к каждому пункту. Обычно — ко времени, можно еще на систему оценивания маленько посетовать, на сложность задач, на плохие комменты к анонсу. Народ заполняет пустующие места с потрясающей стабильностью) Как на зарплате емае) Может кто возьмется подсчитать статистику недовольства по раундам, вдруг моя теория подтвердится?
Если их не писать, начнется хаос вроде "пишу в анонсе, что хочу", "обновляю рейтинг, когда хочу" и "другие переносят начало контеста, значит и мне можно".
Why do people have to post such useless comments? If don't have anything good to write just don't do it.
Dont do it yourself!
Captain Obvious
Keep doing your own work we will do our own!
Кто-то смог понять, что за мат. ожидание нужно вывести в задаче C?
huge problem statement.. :( (except B).
As a non-native speaker of English. It took me a lot of time to understand the problem.
kakaya raznica, 4tovi dobavili vserevno u mena o4ki u6li, t.k. sdal na 15 minut pozje 4em xotel...
How terrible the contest is!
terrible system testing too...
The hardest questions came. Almost everyone got zero
The contest is a disaster
wow!!! yeputons did the impossible!!! congratulation yeputons
Задачи интересные, но тяжелые. Читал как книжку.
Странно, автор вроде не Ripatti, а задачи подставные.
Не подскажешь, что за подстава в задаче В на 4 тесте?
У меня была какая-то лажа, не угадывала ответ на 1. Изменил в бинпоиске условие со строгого на нестрогое, прошло тест.
Точно та же фигня, на четвертом! Почти сдал, черт ее побери >(
я идиот(
В этой задаче нужно вывести (в общем случае) единичку, потом (N-4) нулей, потом в трехзначном формате 210 — (10^(N-1) mod 210)
да я уже понял, спасибо)
А почему "210 — (10^(N-4) mod 210)" ?
НОК(2,3,5,7) = 210. Значит, нужно найти минимальное N-значное число, которое делится на 210. То есть, если "на пальцах", нужно прибавлять 210 до тех пор, пока не превысим 10^(N-1). Получается, ответ = 10^(N-1) + 210 — (10^(N-1) mod 210).
А насчет 10^(N-4) это я да, погорячился...
Эхххх...зря я решил сначала за Конфеты засесть, надо было геометрию делать :( Минуты не хватило, чтоб сдать!
Спасибо авторам! Задачки очень понравились, а время чтения историй скомпенсировалось продлением контеста :)
Сегодня 44% DivI опоздали...
Кто вообще придумал выводить 10 цифр в последней задаче? Я считаю, это полный идиотизм. У меня ушло куча времени чтобы нормально заставить свое решение следовать формату вывода, закончил за минуту до конца, посылаю — оказалось, я ведущие нули не вывожу. И так и не успел добавить.
Ага, в итоге Java в плюсе — считаем себе в BigInteger'ах и выводим substr'ом...
For some reason I couldn't use scanf("%lf") to read doubles in problem A (div1), neither use printf("%Lf") to print long doubles. Both approaches gave me WA in pretest 1. It didn't count as wrong submissions, but annoyed me a bit.
Also, the sentence "_A goal is scored when the center of the ball crosses the OY axis in the given coordinate system between (0, y1) and (0, y2)._" is not really true, since the ball should not touch the posts (so (0, y1+r) for instance, is not a valid goal).
For some reason, (0, y1+r) is a valid goal. I tried to hack a guy, who had the target there, but the hack wasn't successful :(
Really? I asked about this during the contest and they said me (0, y1+r) is not a valid goal.
Now I think they should make the round unrated if this point is important in some test case.
I dont think its a valid goal, since it will touch the post before crossing (or in the exact moment) in that sense I believe the problem statement is right, I had the same doubt and had to check it.
Well, the answer is a bit subtle. The point itself is not a valid goal, but! if the problem has a solution at all, then the value of xw that hits this goal is within 1e-8 of a valid solution, so it should be accepted :-)
I don't know if it's my misunderstanding for problem A. I think the output for test case "1 99 100 9 90 9", where xb = r, should be "-1". But when I attempted to hack supergobble's solution, the system returned "Unsuccessful hacking attempt — Answer: 8.8902439024". Then, I successfully hacked hlwt's solution with the same test case. @,@
Is x = 11.3333333 in example case 3 correct? the corresponding y is coming to be 5, right ? But 5 = 3 + radius, then why the answer is 11.3333333 ?
Oh got it, 'the 1e-8 allowed error.'
_/\_Oops, I got it.
I totally misunderstood the meaning of goal =.=
For example case 1 4 5 2 2 1 the line that aims at y1+r would definitely touch y2 so the answer should be -1, but your code outputs 1.11111111
I also don't understand problem A. In the test case 4 9 24 10 3 1 the judge says the answer is 4.7368421053, but my calculations show that the ball will pass through the lower goalpost.
Never mind, I'd missed that it was the centre of the ball that had to pass the line.
Actually I got tricked by the same thing (as well as many others, as far as I saw, Neal Wu also fails this test for example). The problem statements (at least the English versions) weren't the clearest ever xD
Additionally confusing was that in real soccer rules the whole ball has to be inside :)
Yes, I was also tricked by the fact that the ball is somehow allowed to touch the lower goalpost after the center has crossed the Y-axis. I assumed the logical aiming point was the centre of the goal.
awesome speed of servers :) that's already rly annoying
своевременный вопрос по А: правда, что всем было очевидно что если мяч задевает штангу ровно в момент прохождения Оу, то это гол? я весь контест считал это это не гол, благодаря великолепному условию (мы вроде заденем штангу а значит это не гол, как следует из " Если мяч отскакивает от стены не в створ ворот, то есть задевает другую стену или штангу" и "Будем считать, что мяч задевает объект, если расстояние от центра мяча до объекта не более радиуса мяча r").. более того когда я это выяснил неудачным челенджем, то перечитал условие и оно показалось еще более бредовым))) а именно: "Гол считается забитым, если центр мяча пересекает ось OY в заданной системе координат между точками (0, y1) и (0, y2)" противоречит здравому смыслу (ибо он может задеть штану до пересечения линии ворот с отскоком в поле). это вроде правда для нижней штанги так как удар пойдет сверху, но НИ РАЗУ не правда для двух штанг. А в условии не написано, что подразумевалась только нижняя штанга. Надеюсь примерно ясно о чем я) итак повторю вопрос — я один такой кривой? или это косяк автора? И надеюсь, Паша мне разъяснит что же в итоге имелось в виду
UPD: Что происходит!??!?! почему у меня решение прошло все тесты, если я в корне не понимаю условия????? если я все таки правильно понимаю, то верните мне мой второй челендж!!!)))))
UPD2: Еще есть негласное правило, что Accepted не снимают!!!=)
Я задал вопрос "Если мяч с радиусом 1 окажется в точке (0,3) а штанги находятся в координатах 1 и 4, считается ли что гол забит? Или тогда считается что он отскакивает от штанги не в ворота?" мне ответили "Если мяч задевает штангу, то гол не засчитывается в любом случае." И я стал думать что в описанном тобой случае гол не считается.
см мой апдейт, я перестал понимать что происходит))
Моё решение прошло, я считал, что это не гол.
ну и я тоже так считал.. вот мой челендж — 40 80 100 48 51 15. правильно построил тест? система сказала что на него ответ 22.50, а я считаю (и мое решение) что -1. что скажешь?)
У меня тоже ответ -1 :)
А у меня 22.5 и тоже проходит. Я в начале тоже считал, что это не гол, но из-за каких-то глюков с эпсилоном мое решение давало ВА на претесте 7. Я поменял строгие неравенства на нестрогие и оно прошло претесты, а потом и систест.
В Вашем случае можно целиться мячем не в точку (0, 3), а в точку (0, 3 — eps) — и тогда всё нормально. Случай 2*r >= y2 — y1 исключен, а так как ответ выводится с точностью 1e-8, то 3 = 3-eps, и гол засчитывается. (по крайней мере я так рассуждал)
Это понятно. Я так и сделал, но мне было важно именно понять считается ли это голом, потому что в таком случае я бы просто целился в эту точку и всё, а если это не гол, то я так и сделал — вычитал 1e-8.
Просто это какое-то тупое решение. Почему-бы не подобрать такой тест, что мяч будет лететь почти параллельно Oy и этот 1e-8 сыграет сильную роль на попадании.
Я имел в виду брать eps < 1e-8, то есть вообще ничего не отнимать. Тест наверное нельзя подобрать, потому что инпут целочисленный.
В контестах таких правил, то есть когда систесты после сдачи, я думаю сразу после контеста снимать Accepted это норм :)
И ещё: я считаю условие задачи A сформулировано плохо в связи с такими вопросами. И я очень удивлён этому, понимая как Павел хотел провести контест на хорошем уровне, при этом задействовал ещё и двоих сильных кодеров для тестирования. И все пропустили такие непонятки в условии. А ещё, Паш, разве не ты ругался на длинные условия (я может путаю, если так, то прошу прощения)? :)
Как вы считаете: если мяч точно вписывается в ворота, касаясь обеих штанг, но проходя в них, это должно считаться голом?
А там сказано, что y2-y1<2*r, так что это невозможно.
Спасибо за разъяснение, упустил этот момент. Значит мое решение, которое било в центр ворот, упало на чем-то другом..
Это неправильно, потому что если бить в центр ворот можно задеть одну из штанг, а если ударить в другое место, то не заденешь.
Мне после контеста разъяснили, что лучше целиться так, чтобы мяч прошёл около штанги на y2, поскольку тогда мяч «задевает» меньшую часть оси OY.
Я целился в точку (y1+r), если целиться выше, то может случиться, что пока мы будем лететь до этой точки, зацепим штангу в точке y2.
такого не бывает по условию "2·r < y2 - y1" но мне кажется авторы сами не знают гол это или не гол)
Раз уж пошло такое дело, то проверьте на всякий случай решение по С)) Я понимаю, что скорее я облажался, но на всякий случай, удостоверьтесь что у авторов верны формулы перехода когда мы перебираем сколько же из k горшков мы берем хороших и делаем переход (например, что иногда вероятность 0, когда нам тупо не хватает горшков какого нить типа (еще хороших, или уже попробованых))
Egor96 must banned he have 6 succesful hacks to same person please read his code.
All hacked answers differ by only one line ( if(n==x) print(-1); ) and so the hacked case would simply be x.... lol
Same strategy than for the previous contest. Not very original :/
Same story of lohoped ( with even greater this time: 9)
lohoped is as same as Egor96.
No, You are cheater.
This reply display you are genius or cheater :D
Можете кто нибудь объяснить почему такое произошло? http://codeforces.com/contest/248/submission/2642856 http://codeforces.com/contest/248/submission/2642815 P.S. единственное отличие это язык
У Вас массив в 10 раз меньше, чем надо. А в C++ при несоблюдении размеров массива может произойти всё, что угодно, вплоть до звонка Вашей бабушке.
Поведение в том числе зависит от компилятора.
Круто я облажался)
I dont know what type of mocking is this ... after finishin contest 10 minutes later suddenly it shows my B submission hacked .... so is it some ghost or admin self hacked my submission after contest ending ?
If one of my solutions was hacked, will this solution be tested on the final tests? Thank you in advance!
No, but I think that the results aren't final yet. I used testcase: 6 11 H..SSH The correct answer for this testcase is 0 (they can simply go from left to right and back), but your solution and also admins solution answered 1. When I realized this I let admins know and they rejudged these hacks, but there might be other similar testcases. Have any of you experienced similar problems?
Did you get AC though? My program produces 0 as well — could that be a reason I was getting WA all the time?
non-algorithmic problems huge problem statements worst contest ever :|
Do you expect one liners?
Sometimes the problem can't be expressed in lesser words.
Can you try and reduce the length of problem C, without losing any detail?
(and don't forget to add a legend. )
I prefer delete problem C
a problem with geometric O(1) solution
So can you suggest another problem to replace it?
According to the Status page, it seems that the server is doing Final Tests in batches of 20 submissions at the same time, because of that the speed of testing has become faster. Also the "Pending system testing" phase was very short for this contest. Thanks to the sysadmins for the lovely speed optimizations!
looks like Div 1 system test exploded .
Nightmare.
At DIV-1 Problem B. 18 35 HHSSHHSSHHSSHHSSSH Some Accpet Code get 1 as result.
Should be 0
This submission 2650173 of mine outputs 1, but got accepted. I think problem B should be rejudged.
BJIAJL взломал 9 раз одного и того же человека!!!
Всё бы хорошо, если бы в коде взламываемого не было таких палевных ветвлений на вывод неверного ответа. Хитрее надо быть что-ли, а то читеры совсем разленились.
Very tough problem set.. It appeared to me as if I was trying to solve A ,B ,E, E, E .. Add to that the server problems
"25000 700000 1000000 1000000 325000 300000" can hack some Accepted codes for DIV1A.
And what's correct answer? Mine is -1
Nope, the answer is 500000 in fact. It depends on how you define "the center of the ball crosses the OY axis". This is an edge test. When I hacked others, I succeeded if the defender outputted "-1".
My accepted solution outputs 500000. After all, in real life it's a goal :)
I think everyone understood "the center of the ball crosses the OY axis" as "there should be a point in time when the ball's x<0 and it should not have hit any object before reaching this point"
If so, then the judge solution would be wrong if it outputted 50000 for that case. Isn't it?
No I'm Pretty Sure The Answer Is -1 Because In the Middle Of The Way The Distance Of The Ball with the upper Point(y=700000) is exactly 300000 and by the definition of the question : "We assume that the ball touches an object, if the distance from the center of the ball to the object is no greater than the ball radius r." 300000 is not greater than 300000 so it touches the upper point. here is the picture of the situation: http://bayanbox.ir/user/amin.moghaddamv/Untitled.jpg?view
It depends on how you define "the center of the ball crosses the OY axis". If you have crossed the OY axis, it doesn't matter whether the ball touches anything.
actually it doesn't depend on that definition if you look at my picture in the point H the distance between ball and the upper post is exactly 300000.so the ball hit the post BEFORE crossing the OY axis.
Hi, sorry for the off topic question, but what is the name of the software that you used to draw that picture? Thanks :)
It always took me infinite amount of time to draw pictures for complicated geometry problem :(
It looks like Geogebra
Check out Asymptote, it's very nice.
It is Geogebra
and what answer of this test? My solution get 500000.0000000
(10^6)^4 is lager than every unsigned long long number. I don't know whether high-precision is a must. I have to compare two number which may as large as 10^24 in my solution.
Here's my ACCEPT very short code. yw -= r; yb = 2*yw — yb; y1 += r; double d2 = (double)(- xb * y2 + xb * y1) * (- xb * y2 + xb * y1) / (xb * xb + (yb — y1) * (yb — y1)); if(d2/r/r>=1-1e-11) printf("%.11f\n",(double)(xb * yw — xb * y1) / (yb — y1)); else cout<<-1<<endl;
What is going on??
Very slow judging. :(
also Rating update speed is slow :(
and in both division
Прикольная история с б-шкой получилась) Я подозревал решение где надо что-то вывести, но не дошел до него -> написал перебор с длинкой -> AC на систестах.
А что разве не способ? Очень даже, работает ведь. Жаль только что компилятор C# тут Mono)) А так бы мне осталось написать using System.Numerics и считай решил)) BigInteger там вообще мощная штука. Был у меня даже соблазн написать переборчик с ним и забить массив констант) Но, видать, эстет от природы, не стал)
дык длинка то не встроенная, а с руки написанная) Хорошо хоть додумался я до нее, а то мог затупить и забить.
Куда тебе смочь. Я вот смог, и не стал длинку делать, хотя она у меня паскалевская где-то завалялась)
А я таки поддался соблазну — написал тупое возведение 10 в (n-1)-ую с доплясыванием на Haskell. Длинка втроенная, работает быстро (python-вариант не прошел по времени, спасибо взломавшему, а то так бы и не узнал)
эээ не, у меня оказывается все не так сложно) возведение 10 в n-1 степень у меня делается так:
a[n - 1] = 1:D.А у меня так:
10 ^ (n - 1)Вопрос еще, у кого сложно :)Hard contest but without question which nobody solve it. :D
Div 2. Problem C. Can someone explain why for second test 1 4 6 2 2 1 xw = 0.75 is not correct answer?
Cause in your case ball will hit the goalstop. "We assume that the ball touches an object, if the distance from the center of the ball to the object is no greater than the ball radius r."
Can you show where I make mistake? But I do not pay attention to how the ball bounces off the wall. It depends somehow on its radius?
0.75 / pos = (2 — 0.75) / (yw — yb);
pos = 2.4; pos >= y1 + r && pos <= y2 — r;
Hm... Your ball will intersect Oy below y1. How you are calculating pos?
I considering the similarity of two triangles. That to fractions is tangents for angle of reflection. I consider the ball as a point in the reflection? Is that ok?
you should consider the ball touch the OY axis(above the y2 or below the y1).
BJIAJL got 9 Successful hacking attempt of theRed, I think it's not normal things. One of the Submission is 2648987
In a proble B, i lost that than n==3 answer isn't corect...
if(n<=2){ cout<<-1; return 0; } for(i=0;i<n-3;i++){ k*=10; m*=10; m=m%210; //cout<<m; } cout<<1; for(i=1;i<n-3;i++){ cout<<0; } k=210-m; if(k<100){ cout<<0; } if(k<10){ cout<<0; }
cout<<k; system("pause");
Is it just me, or was problem D not available in English until the end of the contest? I think I would have found it a lot easier than some of the others.
Problem B was also not available for like 15 min in the middle of the contest. The web page said: Unable to parse markup [type=CF_TEX] That was annoying.
I had the same problem. I could not open for 20 minutes problem D(about the houses and shops) — Unable to parse markup [type=CF_TEX]. I nearly solved it during the contest(I needed 5-10 minutes more). Maybe I could have solved it, if I could have managed to open it earlier.
how soon would the rating updated?
How soon will the rating updated?
DIV2 C Why is 4 9 30 3 3 1 result -1.
Because you touch the right rod (the ball flies in ~0.136 of it) (I am sorry for my English)
What is rod?
goalpost, sorry. Right goalpost
Goal wide is 5. Ball wide is 2. Why ball can't get to the goal?
Think of it like playing real football. The center of the ball passing through doesn't mean anything. If any part of the ball touches the goalpost, it will bounce off (thus not counting as a goal). So it must always be at least 'r' away from either goalpost, otherwise, it will bounce off.
Goal wide is 5. Ball wide is 2. r+2r+r=1+2+1=4 4 is less then 5. Can you explain better?
Refer to the diagram. The ball has to be at least 'r' units away from the 'Y2' goalpost AT ALL TIMES.
I mean "red" distance.
My submission in Div2 — A is still judging ! 5 minutes above it judged "Accepted" , now I refresh the standing page and it say "running on test 57 — final test" . Anyone please tell me why ?
In the link to the submission, it say "Accepted". http://codeforces.com/contest/248/submission/2642358
But in the result page it say "running on test 57" and the standing is not updated correctly.
Very unusual contest
terrible
let me think of an adjective, mmmmm ...., ha Excruciating!
BALListic contest!
I think this round should be unrated, because of technical issues, rejudges and very unbalanced problemset
God.I get a high rank that I never get before .So I hope this round should be rated.After all,it is ok.
Same as you
Yep, I know that there're people like you. So, I think, it'll be okay, if this round will be rated. I only want to know what other contestants think about this.
P.S. Congratulations!
Как уже указывал SergeyLazarev в своём блоге "Кажется, на Codeforces введено новое правило, позволяющее решать контесты командно с нескольких аккаунтов." У тех же самых пользователей посылки почти идентичны (отличаются на cin/scanf).
Задача A:
2643713 и 2643545
Задача B:
2645747 и 2645372
Задача С:
2647503 и 2646628
подскажите как решалась задача D,E(div2) и почему вот такое решение по С даёт ва 12? http://codeforces.com/contest/248/submission/2648230
По задаче C. Мяч в полете, что явствует из условия, не должен коснуться какой-либо штанги или передней стены (той, в которой "прорублены" ворота). Реальна, как я полагаю (мое решение прошло все тесты), только опасность коснуться правой штанги, поскольку самое разумное — целить центр мяча в точку (0, y1 + r + k*eps), где eps = 1.0e-8 (по условию), а k — что-то между 0.1 и 1.0, как вам подскажет интуиция. Почему так? В этом случае вы гарантировано (с оглядкой на интуицию :)) не касаетесь левой штанги и более того, можете не проверять касание передней стены — если вы НЕ коснетесь правой штанги, то точно не заденете и переднюю стену. В 12 тесте же вы при таком подходе проводите мяч на расстоянии ~2.83 от правой штанги — задеваете, как видно.
вроде бы вот в таком решении я целюсь в такую точку как вы сказали. И проверяю касаюсь ли я верхней(правой) штанги. Однако это всеравно даёт ва 12. http://codeforces.com/contest/249/submission/2650895
Ну как вам сказать. Я пока не вникал в то, что вы делаете, но поверхностный взгляд позволяет заметить, что в вашем решении есть только одно место, где вы выводите -1 — и там вы проверяете что-то странное. Нужно, уже после того, как вы рассчитаете xw, прицеливая в оговоренную точку, рассчитать "красное расстояние" и проверить, не меньше ли оно радиуса.
спасибо) Стоило поменять только 1 значение. Я там просто брал как бы точку с координатой у2 и смотрел какой отрезок соединяет её и прямую нашего полёта. А надо было просто кратчайшее растояние(тоесть высоту) Печально что так тупнал и упала таска
hello Admin,
My submission for Problem B (Chilly Willy) with submission id 2648986 has been judged "wrong answer on test 11". For test 11, n = 3 and correct answer is 210. My code is giving the correct answer 210 for n = 3, on my local machine. But judgement protocol shows my o/p is 119 for n=3. Could you please help me to understand this. Thank you
The output must be divisible (mod must be equal to 0) by 2, 3, 5 and 7 at same time.
I think the problem is the precision of pow(). pow(10,2) returns 99 in CF system, though pow(10,2) returns 100 in your local machine. (99+20 = 119 = 7*17, then your method return 119) This is because the pow() function is only for float and double, not integer.
:)
please someone help me how to avoid this problem my submission
try:
cout << fixed << sol << endl;
cout.setf(ios::fixed);
I think you'd better to use
printf("%.13lf", sol);One of the quirks of printf is that "%lf" is not always defined — "%f" is supposed to be for both float and double (float is promoted), while "%Lf" is for long double. All of this, of course, can be avoided by using cout :)
But there's more problems with
coutthan withprintfcout.setf(ios::fixed);
cout.precision(13);
cout<<sol<<endl;
I got this problem too... this is suck... 11.3333 vs 11.3333333333 ( diff = 0.00003 ) is ok but 4.66667 vs 4.6666666667 is not ( diff= 0.00001 ).
Actually, I think this is mostly judge problem. Getting WA with correct answer is totally unfair.
When checking the correctness of the answer, all comparisons are made with the permissible absolute error, equal to 10^(-8).
Absolute error? Really? You do realize that if the answer has 6 digits before the decimal point (as in this case) and 8 after, that's 14 digits, which is exactly on the edge of the 64-bit floating point precision (assuming the standard 52-bits for the mantissa).
Damn it. My eggs get pained while waiting for the rated result. God.It is 3:30 am now,get to the bed and have a sleep.
Final standings keep changing. Why call it Final standings? :)
Div. 2 C — гробище, а не задача! =)
Всё из-за не очень понятных условий...
Павел мстит за описываемое здесь =)
Здесь-таки картинка всё же способствует пониманию, а не как в 103B - Ктулху
I think final standings is not correct. For example, Div.1 winner yeputons submitted two wrong solutions on problem A, but it doesn't affect his score. Why is it?
Get Wrong Answer on pretest 1 will not affect the score
Thank you, I didn't know this.
That's because he got WA on first pretest. You don't get penalty if you fail on the 1st test case!
Контест выдался, конечно, неоднозначный :D
Лично мне все условия были понятны с первого прочтения. Они очень длинные и в них надо вникать, это плохо, но тем не менее они были понятными.
По поводу задачи A: не знаю, как все ее поняли, но в задаче по сути было написано следующее: надо забить гол, ударив мячом в стенку так, чтобы мяч, находясь правее линии ворот, не ударился в штанги. Проблемы были с крайним случаем, о котором тут все говорят, когда мяч попадает ровно в точку (0, y1+r). Я его считал голом. Но лучше было пояснить это в условии или дать на это семпл, а лучше и то и другое.
По ходу контеста авторское решение по задаче A было заменено (это было заметно: поменялись ответы на семплы). Я предполагаю, что это произошло из-за жалобы на некоторые взломы как раз на таких крайних случаях. И действительно, не очень понятно, какой ответ в этом случае считать верным, а какой — нет.
Про точность: может быть, авторам следовало попросить вывести ответ в виде несократимой дроби? Тогда, чтобы не заставлять использовать длинку, надо было порезать ограничения в инпуте где-нибудь до 100, наверное. Но даже если и нет: в чекере проверку на существование ответа в этой задаче можно было сделать в целых числах, пусть и в BigInteger. А если ответ существует, то можно было использовать текущий чекер.
С остальными задачами, я так понимаю, проблем не было.
Жаль, что я на протяжении первых двух часов решал эту задачу неправильно, упустив из виду один случай. Потом, как все осознал, сдал. После систестов внезапно оказался на 98 месте с одной задачей, решенной с +5 на 1:42. Но, судя по результатам, со сложностью задач и правда был перебор...
Спасибо за отзыв. Проблема была не столько в сложности задач, сколько в неприятной для такого формата задачей A, которая у многих отобрала много времени. Мы хотели отвести от нее взгляды, уравняв ее по баллам с задачей B — не получилось :( Многие участники не успели прочитать и половины всех предложенных задач. Тут еще эти технические сбои. Решение по задаче A мы не меняли, мы просто убрали из авторского решения заглушки на сэмплы, которые выводили ровные ответы для отображения в сэмплах.
На самом деле я не ожидал увидеть от тебя подобный косяк — насколько я тебя знаю, ты вроде как всегда фанатично стремился убирать все двусмысленности в условиях. Плюс условия были действительно трудноватыми, хоть я их и понял с первого раза.
Но две вещи, конечно, сделать было нужно обязательно: разъяснить, что происходит, если мяч попадает ровно в (0, y1+r), и чекать на -1 в длинке. Если ответ не -1, то вроде бы обычный чекер адекватен.
А планируется ли в таком случае реджадж по задаче А тех решений, что получали WA1 до перемены ? Например мой первый сабмит 2643872 получил WA1, хотя совпадает с нынешним семплом и в дорешивании теперь проходит. Насколько я вижу, такая же 10-15 минутная потеря времени имеется довольно у многих, что может, хоть и немного, повлиять на итоговое положение.
Ввод 4 9 24 10 3 1 Вывод -1 Ответ 4.7368421053 Протокол тестирования wrong answer Jury has found point, participant hasn't
У меня вышло, что в таком случае мяч попадает в штангу, разве это не так? Сработало условие, что пролетает на меньшем расстоянии чем r от Y2
Мое решение пишет, что пролетаю на расстоянии 1.01797, так что все ок.
значит буду думать дальше, спасибо )
А вы в какую точку центр мяча целите?
в y1+r
удалось получить расстояние до правой штанги 0.970143 следующим образом: убрал строку
yw -= r;Вы уверены, что отражение мяча от стены считаете с учетом его радиуса?Именно! Когда проверяла, встретится ли мяч со штангой, заложила неправильное условие, что когда y=yw (вместо yw-r), x=xw.
Why answer for test 7 is 4.5? What i'm getting wrong? https://www.dropbox.com/s/qjm3mcvpbq2mqwr/IMAG0050.jpg (sorry for darkness)
Submission is here http://codeforces.com/contest/249/submission/2651233
Though I haven't analyzed your code, but I expect that the failure in test 7 may happen in the case you consider the ball as a point when it is reflected on the wall.
Thanks, I solved.
Я так и не понял, в чем неоднозначность в условии задачи А? Вот, например, тест, в котором мяч касается штанги еще не долетев до линии ворот:
В условии ясно сказано, что если он находится на расстоянии не более r от штанги, то он отскакивает и гол не засчитывается. Авторское же решение считает, что мяч отскакивает от штанги только если расстояние строго меньше r.
Ну у меня была не столько проблема с пониманием, сколько понять, действительно ли авторы имели ввиду то, что написали, чтобы не засылать неправильных решений. Как позже выяснилось, я был не зря насторожен и куча людей получила минусы по взломам пытаясь сломать решения, которые касаются штанги в момент нахождения центра на оси Oy.
I'm not shure, if I understand the rating process wright, but I read, that it depends an your estimated ranking (namely the list, of registered people before the contest) und your real ranking. I was around 600th place before the contest in Div1. In this competition(due to missunderstood statements and small mistakes) I did not even solve a single problem, but most of the others also don't. So I got around place 100 -> does that mean, that my rating would increase, without solving a problem... (If it is so, it would be rather strange)
1) Expected place is calculated using only participated people, so it's about 340, as far as I remember
2) Your place is divided from 100 to 340, so you place seems to be used as 220
BTW, as far as I remember there is fix now: if people with score <= 0 can't get rating icrease, but I'm not sure. There were discussions here, you can try to find it
4 9 20 10 3 1
Вывод 4.66667
Ответ 4.6666666667
Протокол тестирования wrong answer Participant's ball doesn't bounce into the gates
Test #11 : 2 9 10 4 6 3 Why answer is 2.6666666667 < 3 ???
The answer must lie in the range 0 < x < xb = 4. What is the problem?
The broblem is answer < r
Hmm.. I found no problem. The answer is not limited by r.
As of problem A, how can there be an answer with x < r?
In the statement, we have:
"...so the gate of Robo-Wallace's rivals may be not in the middle of the left WALL"
In a case where we aim to x , when x < r, the ball would bounce off the left wall first , am I correct?
No, you are. The situation you and Zero_sharp are discussing may be below.
I decided to simplify the task this way: yw-=r; y1+=r; After this all we need is to calculate position of the center of the ball. Then via school geometry you solve easy proportion. And the last calculation is to check a distance between left straight of the trajectory and y2. If the distance is lower than r then return the solution. Else return "-1". If somebody needs more detiles, I can draw some picture or watch the code.
the rating change should be reflected asap
Can jst ne1 clear my doubt on the compiler's absolutely different processing than the Ideone online compiler because my code worked correctly there and not here.... and yes i know my code would have any way produced wrong output further but it did nt even work on the 2nd preset of the div 2 problem B.....
The CF system doesn't support "%lld" specification. Please use "%I64d", instead. BTW, the pow() function may return unexpected value. For the integer problem, you shouldn't use the function for float and double (, like pow()). pow(10, 4) returns 9999. Please make sure with custom test.
The
pow()function operates on floating point arguments and may return imprecise results. You should implement an integer power function yourself. Also, Codeforces officially recommends to use the non-standard%I64d/%I64uinstead of%lld/%llu.In Div2.C(Div1.A)problem,I got Wrong Answer on test case 8. My answer was 4.375000・・・. I can't understand "wrong answer Participant's ball hits left wall before goal". Please teach me what's wrong...
You needed to check a distance between left straight of the trajectory and y2. If the distance is lower than r then return the solution. Else return "-1".
Little update
По-моему, это первый случай в истории Div1, когда 229 человек поделили между собой 108-е место. Мне одному кажется, что 7 задач (полученных добавлением Div2A и Div2B) могли бы сделать результаты более адеквадными?
Думаю, что не могли бы: те задачи были слишком простыми.
Да, они не сравнимы с Div1A. Решили бы, скорей всего, все упомянутые 229 человек. Но в этом случае время сдачи и очки были бы различны.
Rating has already updated!
Удалено, приношу свои извинения.
Удалено, приношу свои извинения.
link to editorial (English preferred) when it's published, please?
My rank in this contest is 514 : http://codeforces.com/contest/248/standings/page/6 . But in my profile page, it says 750 , and my rating go down for 51 points.
Admins, why you don't respond to this?
Почему у меня на нетбуке в задаче В див2 длинка (BigInteger) на Java для n = 99995..100000 работает стабильно за 1.5 — 1.6 секунды а на сервере TLE получает( >2000 мс) ?
Когда же будет разбор...?
Could someone please tell me how to solve Problem B? I understand the binary search bit, but how do you find the minimum possible time for a fixed k?
разбор — http://codeforces.com/blog/entry/5979
No editorial this time?
You can find it in russian, unfortunately google translates it pretty bad this time (sometimes it's more readable than others).
http://codeforces.com/blog/entry/5979
I don't think anybody got the Robo Footballer problem right. I just tested several people's accepted code and none of them worked.
Example 1: 5 24 25 6 9 4
A correct answer is xw = 3.00000. None of the programs get this right. They all answered -1. The problem is that if you aim at 3.0000, the ball never gets near goal post 2. However, using the reflection method, which most people seem to have used, it falsely says that the path hits goal post 2.
Example 2: 1400 2499 2500 1200 900 500
Once you've fixed your code to handle the first example, then you have to make it recognize that example 2 has answer -1.
Unless you're careful, your program will think that xw = 100 is a solution. But it's not, because when you aim at that, you'll hit goal post 1 before the reflection.
A completely correct solution has to partition the path into two segments -- before and after the reflection -- and then make sure that both segments are free of collisions with the goal posts. To find xw, you have to intersect the ranges of xw that are collision free in both of the parts of the path.
--- Danny Sleator [email protected]
I think another possible approach would be reflecting on yw , get the max angle where the top part goes in, then reflect on yw-2*r, get the min angle where the bottom part goes in, and if min<=max return the average.
How the %^* is this possible !?!?!?! Problem D — Wrong answer on test 95 Expected answer 130, found 131 -.- .....
Looks like correct solution needed this: if(wynik!=132) { cout<<wynik-1<<endl; } else { cout<<"130"<<endl; }
xD
Я понял, что с задачей A возникли какие-то проблемы. Но мне совершенно неясно, как вы писали чекер. Очевидно, что ответ к задаче, это либо пустое множество, либо открытый интервал. Логично было бы найти границы интервала и проверить, что ответ находится внутри этого интервала с некой погрешностью. Я, решая эту задачу, придумал немного другое решение: я приближал не к верхней штанге после переворота, а делал сложнее: к нижней. Соответственно, мне пришлось поворачивать вектор на угол... Но все же, мой ответ, получающий wa1, увеличивается на 1e-9 и получает ок на этом тесте. Да, и задача вполне себе строгая, так как ее можно решить в лонгах (сравнить r с расстоянием от прямой, порожденной двумя целыми точками, до целой точки). Поэтому проблемы с точностью у участника могут возникать только по его вине и только в случае, когда интервал получается равным (a..a) и он выводит a +- eps, а должен -1.
no editorials ?
Can someone explain how to solve the problem Chilly Willy please ?
Let's look at numeric strings of length <= 3.
The smallest number that fulfils this criteria and is divisible by 2, 3, 5 and 7 is lcm(2, 3, 5, 7) = 210. Hence, we can conclude that the answer for n <= 2 is -1 and the answer for n = 3 is 210.
Now let's analyse the case where n > 3.
From here, I assume that the answer string that we are generating is indexed from 0.
The smallest numeric string of length n > 3 without leading zeros is 100... (i.e. A single 1 followed by n-1 zeros).
Basic math tells us that any number that is divisible by both 2 and 5 must end with 0. So character n-1 (the last character) must be 0.
That leaves us to check divisibility by 3 and 7. We can easily do so by long division and keeping track of the remainder. This works in O(n).
Up till now our answer string is 1 {n -2 zeros} 0. Since lcm(2, 3, 5, 7) = 210, we know that in every 210 consecutive numbers, there is at least 1 number that is divisible by all four divisors.
With this in mind, we can use 2 for-loops to manipulate characters n-2 and n-3 in our answer string.
Let's look at the sample run of this algorithm for n = 5.
Our answer string is initially "10000".
Notice that we will run the 2 for-loops at most 21 times because we "add" 10 to our answer on each iteration. That means we don't iterate through all 210 consecutive numbers. Rather, we just have to check numbers in steps of 10 because the answer has to be divisible by 2 and 5.
Hence, overall time complexity is O(21 * 2 * n) which fits well within the time limit for this problem.
In case you have problems with the implementation, here is my solution (which uses this approach).
Wow. I finally understood this today. Be greedy and find the smallest number of length n that satisfies the condition. The last digit is fixed.
We want a number that's divisible by 3 and 7 since 2 and 5 are already guaranteed. This means we will check at most 21 numbers. (By the Chinese Remainder Theorem)
Thanks a lot, Lance !
You are most welcome! Actually, I think that you can pass the time limit for this problem even if you check divisibility by 2, 3, 5 and 7 since you just need to check at most 210 numbers (using the greedy strategy).
I was just being a little picky by introducing that optimization. In fact, you can even do much faster than my optimized implementation.