Друзья, привет!
Через несколько часов Вам посчастливится участвовать в знаменательном раунде Codeforces Round #27 для участников Div. 21, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Игорь Кудряшов (Igor_Kudryashov), Павел Холкин (HolkinPV). Как всегда с нами были Геральд Агапов (Gerald), Мария Белова (Delinur) и Михаил Мирзаянов (MikeMirzayanov).
Как вы все прекрасно знаете, только сегодня вы сможете поучаствовать в этом раунде в конкурсе, не упустите такую возможность! Другого раунда Codeforces Round #27 вы не увидите нигде! :)
Традиционно всем удачи, полных решений и удачных взломов!
UPD: Распределение баллов по задачам стандартное: 500, 1000, 1500, 2000, 2500.
UPD: Соревнование закончено, всем спасибо за участие. Надеюсь вам понравилось, но не забывайте, что нас еще ждет системное тестирование.
UPD: Уже опубликована предварительная версия разбора на русском языке
стоимость задач динамическая?
в сообщении, пришедшем мне на e-mail написано, что раунд будет проведен по оригинальным правилам Codeforces. То есть нет, не динамическая система)
I'm predicting most of the problems will have jokes on 2-powers
Good luck to all! :-)
using dymantic score or something else?
can you talk about Score distribution. hope short and clear statements. Finally ,Thanks for preparing this contest.
Судя по номеру будет много математики ;)
Лишь бы реализаций поменьше.
в нашем дивизионе умение четко и остро писать реализацию важнее математики (:
Еще важнее читать условие нормально...
Еще важнее быть хорошим программистом...
А какой конкурс?
Имелось ввиду вне зачёта.
hoping for short and precise statements...
may it b overall a gud cntst..:)
Скучно как-то. Вот на topcoder по поводу power-of-two даже стоимости задач соответствующие делали: 256, 512, 1024...
здесь не цирк, чтобы вас веселить
Не понимаю, зачем его минусовать? он же правду говорит.
Просто dangerous тролль.
кто тут у нас заговорил? этот тот кого обидели, не оценив его понт, этот тот, кто плачится из-за вклада?
видимо вас сильно угнетают мои комментарии, по вашему повод, раз вы не поленилесь написать это в мой адрес
оффтоп. Почему минусуют личностей, желающих всем удачи?
может потому что хотят видеть сообщения по-существу.
У меня обратный вопрос. Почему мне поставили жуткий минус, когда я пожелал всем неудачи? Где хваленая логика?
Потому что это тоже оффтоп.
тут много чего оффтоп. Кстати, этих людей уже заплюсили:)))
Nothing New!!! :P Everything is traditionally traditional!!! :D
Points should be: 512(2^9), 2*512, 3*512, 4*512, 5*512. :)
Смайлик в анонсе принесет всем удачу на контесте :-)
Главный герой первой задачи это Qwerty821 или это совпадение?
Хороший контест, чтобы почувствовать себя умным, но медленным.:(
как решалась Е? аккуратной жадиной?
I cannot understand why this solution does not hack successful on the test case 1000 1 1000 1000 for problem B div 2.
Very dangerous to try a hack like this, using errors about size of the array. Maybe it will fail for system test, but you can't be sure what will be returned by this kind of code. Only hack codes with bigger problem of size.
A similar question has been asked before: http://codeforces.me/blog/entry/2799#comment-57306
Thank You..I learned something on the cost of 2 unsuccessful hacks (-100 points)
but dude in that n can be at max 1000 and he was having bound of 1001 which i think should work fine......
Look carefully what happens if x = n or y = n.
according to me nothing would happen..... if we have A[n+1] then whats the problem with A[n]
The code is running for each value of x and y,two inner loops (x to < x+3) and (y to < y+3)..Now for x=y=1000 , it is incrementing the values at array indices [1002][1002] also ..Thats were I thought it should give runtime error as Array Index out of bounds exception..But As andreyv says it fixes some page memory buffer for its excution , although I am not clear of its concept totally..So I said I would rather not take risk in furthur contests which such hacks
was your hack for the size of the array or because he didn't continue taking the input and returns when solution found?
For the array size..It exceeds 1001 .So Array index out of bounds exception
Спасибо за замечательный контест))))
Е решается бинпоиском по массиву, отсортированному по возрастанию количества затрачиваемого топлива, роботов, которые могут кого то везти и пересчитываем ответ???
Е решается так: вначале мы находим максимальное количество роботов, которое мы можем перевезти, а потом бинпоиском находим минимальное количество топлива, нужное для перевозки такого количества роботов. Но я сам где-то не учел какую-то мелочь.
Как найти число роботов?
ну да по сути, я просто отсортировал всех "претендентов" по увеличению топлива и перебираю границу самого правого которого возьму. функцию проверки не успел сделать =(
у мну не бинпоиск, хотя очень долго слал, но судя по количеству претестов... думаю пройдет. Основа идеи в том, что я могу взять самого малопотребляемого, у которого не нулевая вместимость и вложить в него все остальные роботы по максимум... Да, у меня тоже такая идея не проходила 13 претест... там надо было сообразить, что в некоторый момент времени, того робота которого складывали в другого выгоднее отправить пешком, а на его место положить другого робота, который возможно вообще не дойдет...
вот вот, также решал, какого-то хрена не зашла
Еще можно его не брать, а брать с нулевой вместимостью, но дешевых (как до меня дошло за 10 секунд до конца контеста :)
ну да, я об этом сообразил, исправил, но что-то не прошло... чувствую, так она и решалась
А если у нас есть робот, тратящий S топлива, и 3 робота, в сумме тратящие S, но у этого одного вместимость больше, чем суммарная у этих 3. Тогда если брать каждый раз с мин.потреблением, то вроде неправильно получится.
ну вроде в самом начале выгодно либо напихать всех роботов ненулевой вместимости в робота минимальной стоимости, либо, выгоднее погнать роботов нулевой вместимости, если за такую же стоимость, нулевых будет больше
Можно много где набажить, у меня упадет на таком тесте:
6 1 100
2 0 2
2 0 2
0 1 2
0 1 2
0 1 2
0 1 2
а ты бинпоиском решал?
нет
Нет, я писал подобную жадность как у aropan, но сделал глуповатый баг, попробую в дорешке сдать.
Мне показалось, или контест продлили на пару минут из-за лагов?
I hope next time there'll be more fluent English in the description of problems. I know that many authors aren't native speaker but today's problems are just a bit of difficult to understand. Besides how long will the system test be?
I think I'm not the only one who miss if x = 0 so I failed on preetest 3 :) Edited : On problem A
You're not alone =)
I solved it on the 2nd minute, realized the x=0 after 5 submits and 30minutes passed :( got 240 pts
System test has begun, finally!
But it is going too slow today
в Д, походу, были слабые претесты
Приветствую!
Подскажите пожалуйста как нужно писать ( или где можно об этом прочесть) генератор для взлома на С++ и не получать:
-FAIL Expected EOF (stdin)
-FAIL Expected EOLN (stdin)
Благодарю.
UPD: вопрос решен — моя ошибка, а именно выводил более чем М запросов ( задача В ). Теперь понял почему EOF expected.
Вывести в конце пустую строку?
То есть последние два символа файла имеют вид "\n\n"?
В таком случае я получил
FAIL Input can't finish with empty line, but the last line is empty
Например, если надо вывести одно число, то правильно
1\n, а не1.Совпадает ли это с результатом исполнения кода
cout<<1<<endl;?Да
В таком случае я получал
-FAIL Expected EOF (stdin)в задаче В, что можно сделать?Не перепутать n и m? :)
Если с n и m все прекрасно? (=
UPD: моя ошибка — выводил больше чем М запросов. Теперь понял почему EOF expected.
В конце строк не должно быть пробелов, последний символ файла должен быть
\nСпасибо за классный контест. Задачи интересные, мне понравилось.
Тестирование завершено?
Нет, оно повисло.
Cool contest guys! Imo little bit easier than last ones.
I have to criticize the task description of task A though. It repeatedly uses the term "cost" to describe the score of the problem. If this is not clear... cost has a negative connotation, decreasing the cost with time thus means that we get a higher score with time. Really confused me there.
Комната 22, тестирование по двум решениям задачи С зависло.
I think a system test server is down: http://www.codeforces.com/contest/203/status/page/25?order=BY_JUDGED_DESC
Why does it stuck at 99%
So unlucky. The test size of C is 10^5 but I mistaken it as 10000. I missed my AK this time, such a pity. The good thing is my E is AC.
What does "AK" mean?
accepted all problems.
How to solve Problem D div 2?
Assume there are three balls one going with velocity vx, other with velocity vy, and third with velocity vz. Now at the time of 2nd ball colliding with Door, find where are the two other balls.
Thanks for your help!
First observe that reflection does not change ball's speed in dimensions so you can easily calculate the time that ball gets to y=0, T. Now calculate X and Z of the ball after T seconds. Now you need to find its position inside corridor. Notice that X,Z dimensions are independent. Consider final X of the ball without reflection is X0 and after being reflected once and changing its side, final X of ball without any further reflection is X1. By laws of reflection, X0 and X1 are symmetrical to each other by the wall which ball was reflected by so if it hit X = (a) line then you can calculate X1 as : X1 = 2 * a — X0 and if it hit X = 0 line, X1 will be -X0. And go on from this point until X and Z are inside the corridor. These actions can be done by some easy while loops. I hope this explanation's been helpful for you. If you need further information on this solution, please let me know.
Thank you! I have found my mistake.
D was quite easy today, look at my submission (sorry, no time for comments in contest), only solve() is important...
в комнате 3 задача B повисла, если это поможет
The English seems much less comfortable than SRM.......
As soon as i posted this comment system test ended. really sry.
http://codeforces.me/contest/203/submission/1860447
почему такое решение получает WA7? У друга посмотрел, у него такой же ответ и тест пройден...
Комментарий чекера wrong output format Unexpected end of file — int32 expected
Может быть, дело в этом?
Вывод программы — это не «Ответ», а, собственно, «Вывод», и в данном случае он пустой.
решил 3ю задачу как на разборе. не прошел 37 тест почему? там ограничения должны же вместиться в ИНТ!
Попробуй тест
открой тесты да посмотри, на чем валится твой сабмит. У тебя там именно переполнение, надо было работать с лонгами)
А меня взломали, не прошло по времени. Не подскажешь, почему?)
кажется у тебя квиксорт без оптимизации, в худшем случае работает за квадрат http://codeforces.me/blog/entry/4818#comment-98244
Хорошо на Яве писать Arrays.sort() или Collections.sort() (:
Arrays.sort() для примитивных типов работает за квадрат
в 7й разве?
Исходников не видел, но вроде бы да. Ведь там такой же квиксорт, только разделение на подзадачи более сбалансированное (пруф). Правда, мне кажется, она может влезть в 2 секунды на худшем тесте.
спасибо)
Кстати сказать, в 2 секунды на худшем тесте влезает и на шестой жабе (когда я тестил год назад — на 10^5 отрабатывало за 1.8с).
Не влезает, я успешные взломы делал на Codeforces твоим генератором. Наверное, у тебя компьютер слишком быстрый.
На Java 7 тоже не влезает, 90000 элементов работает в запуске чуть больше 2 секунд.
Если речь про эту задачу, то там ТЛ 1 секунда.
Так значит сортировка в седьмой жабе имеет худшую константу? Просто я те 1.8с получил тоже в запуске.
Например еще 140C - Новогодние снеговики, там TLE 2 секунды. Смотрите тут взлом 30160.
Да, работает за квадрат. Я исходники видел, алгоритм там тоже полностью детерминированный. Надо и под седьмую жабу написать как-нибудь антиквиксорт :).
Можешь не стараться, все уже сделано
Подскажите, откуда может быть такое исключение, где я натупил http://codeforces.me/contest/203/submission/1856933 java.lang.IllegalArgumentException: Comparison method violates its general contract! at java.util.TimSort.mergeLo(Unknown Source) at java.util.TimSort.mergeAt(Unknown Source) at java.util.TimSort.mergeCollapse(Unknown Source) at java.util.TimSort....
compare(a, a) должен возвращать 0
Точно, спасибо.
Finally over. Ranked 31 in official participants. Not so bad, but have mistaken the test size of C is so awful. When'll the Rating be updated?
задача C: на c# ни у кого не прошел тест 53 по TLE. проверил свое решение локально на 100000 строчках — меньше секунды. баг?
Возможно антиквиксорт тест? Когда-то читал, что Petr когда-то получил ТЛЕ из-за того, что квиксорт на C# работает за квадрат, причем получил на онсайте.
Печально. А можно как-нибудь получить полный текст этого теста?
Думаю, нет. Зато можно рандомно перемешать массив, и посортировать уже его.
UPD. 946517 74 тест
Попробуй заюзать метод чтения данных с этой отправки.
Не. точно не чтение. тест 47 тоже на 100тыс строчек: Время: 230 ms. Вердикт: ОК
http://codeforces.me/contest/203/submission/1857631
тогда осталось перед сортом добавить shuffle()
может поможет.
Да уж. Вероятностное программирование. Shuffle действительно помог.
Этот Mono у меня уже в печёнках сидит :E Много контестов я уже завалил из-за его тормозов. А теперь выясняется, что у него еще и сортировка глючная.
Уважаемые авторы Codeforces, поставте нам микрософтовский .NET! Очень просим
А Вы в курсе, что Array.Sort() в официальном(!) майкрософтовском(!!) .NET 4.0(!!!) написан ровно так, как первоначально объясняют квиксорт школьникам из параллели C на ЛКШ, т.е. с выбором опорного элемента через (l + r) / 2? Правда, школьникам в параллели С (в отличие от индусов из майкрософта) сразу же объясняют, что не хрен так делать.
UPD. Насчет того, что в дотнете "школьный" квиксорт, я ошибся (см. мои посты ниже).
У вас ложное представление о том, как реализован Array.Sort() в .NET вообще и в 4.0 в частности...
Смотрите исходники внимательнее. Там выбирается медиана из трёх элементов. Хотя это тоже не гарантия, я в курсе, но хоть что-то.
В любом случае, это всего лишь одно из проблемных мест Mono, с которыми мне пришлось столкнуться. Пожелание остаётся в силе.
Я лично декомпилировал mscorlib.dll и смотрел реализацию квиксорта. Вот как там реализована та самая функция Array.GetMedian():
Если вас обоих это не убедило — возьмите ILSpy и сами проверьте.
UPD. Да, я ошибся, медиана действительно находится (берутся первый, средний и последний элемент). Но такой квиксорт завалить все равно не сложнее, чем обычный.
Я не знаю куда вы там смотрели и при помощи чего. Простой тест. Вы можете написать код метода GetBadArray, который бы вызывал квадратичное время выполнения Array.Sort()? Если там простой квиксорт, которому учат в школе, то вам это не составит труда. Причем можете попробовать как в .NET 2.0 так и 4.0...
Я где-то нагугливал уже готовый антиквиксорт для C#, работает через компараторы, но ладно, сейчас сам напишу, подождите полчасика...
Если там (l+r)/2, то вот вам тест: http://paste.ubuntu.com/1075047/
Писал в два раза дольше, нежели обещал, но вот генератор, работает за линию :).
На 2.0 у меня выдает:
На 4.0:
Странно...
Десктоп (проц P4 640 3.2 GHz, ОЗУ DDR1-400, .NET 4.0 без SP):
Ноут (проц Core i5 430M 2.26 GHz, ОЗУ DDR3-1333, .NET 4.0 SP1):
Codeforces, вкладка "Запуск":
Вы ничто ни с чем не перепутали?
Я кажется понял... У меня стоит .NET Framework 4.5 RC, который патчит сборки 4.0.
Т.е. у меня версия файла mscorlib.dll такая: 4.0.30319.17626. У вас видимо номер билда отличается... Когда я декомпилил mscorlib, то увидел там интросорт, но добавлен он видимо только с этого 4.5 апдэйта...
please somebody tell me whats wrong with my comparator in problem C.I cannot figure out for which values it cannot make a decision..Here the code
a.compareTo(a) should return 0, not -1
Problem E was nice.it has more thinking rather than just coding. thank you all
I agree with you. It has nothing to do with advanced algorithms and data structures, but remains as a challenging problem. In order to solve this problem, one must observed that if a robot with c larger than 0 is chosen then all robots with c larger than 0 can be chosen. It took me over 30 mins to figure out how to solve this problem.
Can Anyone Describe me why I stayed blue in rating?? I became 24th and solved four problems. I ask this because people with lower rank became purple!
The contest was great. Thanks a lot to problems authors! ;)
Because your rating is still below 1700
Are you telling that someone with lower rating at the contest beginning had less point than you in contest and now he/she has greater rating than you? I'd like to see that...
Oh! I got it! You're right. It's because of their rating before the contest! I didn't know the importance. Thanks
Hope that you'll be over 1700 soon ^_^
Thanks dude! ;)
Hello, excuse me for the question but this is my first competition in this website and i kept having wrong answer on 7th pretest in task E. So i tried to find my mistake but i couldn't, so after the competition is over, i was wondering if there is any possible way to check what the pretest was, and see why my program mistaked there. Thank you in advance :)
Hello! Click here and scroll to the bottom of the page. But there is not way to see full test.
I encountered the same problem as yours during the contest, and then I figured out that using long long instead of integer can solve this. Hope this helps.
В задаче С в QuickSort было поставлено x:=m[(l+r) div 2] ТЛ. Просто поменял на x:=m[l+Random (r-l)] все прошло!!!
А в чем проблема? В такой задаче было бы странно не сделать антиквиксорт теста для разбиения пополам.
UPD: господа несогласные, прокомментируйте ваше мнение, минусовать все горазды.
Y U no put small clear problem statements :)
I got a strange result with my code on D, on test case 31:
-1.#IND000 -1.#IND000
On my pc it gives the expected result, I had to add a test to verify if the vz (or vy or vx) is 0 and ignore calculations on them to get accepted, here is my submission:
http://codeforces.me/contest/203/submission/1861627
1861821 Can you tell me why I got a TLE on problem B ?
return a > b ? b : a;is mistake.for(int i = chmax(1, x - 2); i <= x; i++)always runs x times and you got TLE.thanks
rofl @ pretest 3 of task A... this guy boasted he has a score of ZERO? WTF is wrong with him :)
Noone with sense of humour here.
when we can get THE EDITORIAL!!