Здравствуйте дорогие друзья)
Рады приветствовать вас на очередном раунде Codeforces #113 для участников Div. 2. Традиционно, остальные могут поучаствовать в нем вне конкурса.
Задачи для вас были подготовлены уже знакомой группой авторов: Холкин Павел (HolkinPV), Николай Кузнецов (NALP), Артем Рахов (RAD). Мы благодарим Геральда Агапова (Gerald) за помощь в подготовке раунда, Михаила Мирзаянова (MikeMirzayanov) за систему Codeforces и Марию Белову (Delinur) за перевод условий.
В сегодняшнем раунде будет одно нововведение. Распределение баллов по задачам будет динамическим. Более подробно об этом можно узнать здесь)
Надеемся раунд пройдет успешно для всех участников. Желаем вам удачи и высокого рейтинга!
UPD: Соревнование закончено. Надеемся вам понравилось) разбор задач уже здесь
Поздравляем победителей:
ВНЕЗАПНО!)
У меня одного по-английски?
Наверно, у меня всё отлично.
My friend tried to register and got the message "Cannot register user now. Try later or contact the administration.". Why?
And I have registered twice.
help him~~~~~~
Раунд пройдет без взломов?
Почему? По-моему, данная система не отрицает взломов.
А вот пройдет ли раунд без взломов... Это будет зависеть от корректности алгоритмов участников =)
Надеюсь тур будет очень интересным.
А зачем отменили сортировку задач по сложности?
Для чистоты эксперимента. Ваш К.О.
http://codeforces.net/blog/entry/4172
Иногда оказывается, что авторы и тестеры не угадывают сложность задачи с точки зрения массового участника.That wasn't a good idea . At least If you told before I think that would be better . But thank you for your great idea . Hope best for everyone .
а почему начало не в 19:00?
потому что начало в 19:30.
ну ты умник
Насколько я помню 112-ый или 111-ый контест тоже в 19:30 начинался.
ну там просто перенесли в последний момент, потому что сервер упал, а сейчас еще во время написания поста это время было
Нет, не переносили, а было написано:'Начало в 19:30'!!!
Странно, на codeforces.com до начала контеста 10 минут, а на codeforces.ru — 15 минут (на момент написания коммента). Синхронизация времени шалит?
Извините, не подумал...
на .сom показывает время до конца регистрации, ибо вы там типа не онлайн
Ой, посыпаю голову пеплом, что-то я невнимателен.
Раз раунд экспериментальный, тогда может сделать его нерейтинговым?
Я думаю, что если от новой системы оценки ничего не поломается, и твоя бабушка не будет ругаться, то можно и рейтинговым сделать.
Если не будет особых причин, то раунд будет рейтинговым. Надеюсь, он таким и будет.
Подскажите пожалуйста, почему падает на 16 претесте такое решение по задаче B:
Все точки скинем в одну кучу. Построим выпуклую оболочку. Если выпуклая оболочка совпадает с многоугольником А, то все хорошо, иначе плохо. также аккуратно предусматриваем, чтобы вершины многоугольника В не лежали на сторонах многоугольника А(выпуклую оболочку делаем нестрогой).
Кто-нибудь сдал таким способом? Просто интересно, косяк в реализации, или в алгоритме.
Построил выпуклую по B и для каждой точки проверял на принадлежность A за log(A.size()). Тот же 16 претест.
Я проверял на принадлежность все точки B. Претесты проходит.
В смысле? За квадрат?
Нет. Бинпоиском каждую можно проверить за logN
У меня падало по причине, что лежало на стороне А
Думаю в реализации.
Может баг в том что нельзя что-бы точки лежали на многоугольника?
Точки многоугольника B на выпуклой оболочке? Ну мы же делаем ее нестрогой(добавляем и точки, которые лежат на одной прямой).
Ок, тест:
3
0 0
0 1
1 0
3
0 0
0 1
1 0
Ну это же чистая ошибка в реализации — отдельно отсечь точки, которые есть в исходном многоугольнике несложно.
Более чем уверен, что баг именно в этом.
На совпадение вершин у многоугольников, у меня в самом начале стоит отсечение (сетом)
элементарно, ватсон:
4 0 0 0 2 2 2 2 0 1 0 1ваша программа выводит YESя понимаю, что 1 точку нельзя, но можно добавить несколько точек и ваше решение по прежнему выведет YES
Спасибо! А ведь странно, я вроде предусматривала =(
Интересная идея. Бага в алгоритме не вижу. Есть алгоритм попроще: заметим, что B внутри А <=> каждая точка B внутри А. Для быстрой проверки используем выпуклость А: возьмём самую левую и самую правую точку, проведём между ними "верхний купол" А и "нижний купол". Проверяя точку из В, для каждого "купола" найдём бинпоиском отрезок, в котором лежит координата Х этой точки, и проверим, что коорд. Y больше соотв. точки на отрезке для нижнего купола и меньше для верхнего.
Хах. По Е написал динамику за 30 сек до конца и не успел продебажить((
Столько баллов потерял из-за размера массива в С (((( Вот я тупооой...
Can anyone give some hint(s) for problem D? :D
A typical DP problem, but you must record the <shoeId, customerId> pair during the dp loop.
Подскажите, каким мог быть 3-й претест в D? Уже голову сломал, блин :)
И да, советую заменить "Ошибка времени исполнения" На что-то вроде "Ошибка запуска программы", а то пол контеста думал, что у меня тайм-лимит(((
Ошибка времени исполнения это буквальный перевод Runtime error.
Все более или менее опытные программисты Runtime Error называют Ошибкой времени исполнения.
Кстати, "Ошибка во время исполнения", действительно, было бы гораздо понятнее и занимает не сильно больше места.
Я уже это предлагал. Инициативу не поддержали...
Так же, эта тема обсуждалась здесь.
В принципе, с этой проблемой обычно сталкиваются новички и только один раз. Так что, можно оставить всё как есть.
я раунд не писал, но заметил следующий прикол: по задаче С 933 решения, участников див2 2070 (993/2070 < 1/2), почему стоимость ее 500? или из-за взломов?
Потому что учитываются только участники, которые сделали хоть один сабмит. А таковых 1443.
мне кажется, или не стоило делать Б такой боянистой? а то многие умники, как я посмотрю с емахха код содрали
Почти любую задачу можно свести к сдиранию кода с емакса и что?
Да пусть она даже полностью там решена, что дальше-то? Или тупо обидно, что сам не додумался?)
да просто как-то неприкольно, некоторые играют честно: думают сами, а некоторые опа, на 15 минуте быстро скопировал и сдал, толк тогда задачи? мне кажется, надо хотя бы чуть более сложнее давать задачу, чем просто скопировать, не считаете так?
а идею эту я знал, так что мне не обидно
Люди, которые копируют код -- сами себе злые буратины, т.к. не понятно что они получат, решив на 1 задачу больше, но не честно. Сами себя обманывают.
да я это прекрасно понимаю (даже прикол не в этом, а в том, что они будут делать когда емахх не будет — на какой-нибудь олимпиаде)
Они не будут конкурентами, причём возможно, именно Вам! Разве это плохо?
If after the test completed, the number of contestant who can solved the problem change, will it change the problem's score?
Yes, the problems' score can change after system testing.
Контест мне понравился. Единственное, по-моему ограничения в задаче Е надо было делать такими, чтобы тупое последовательное умножение матрицы не проходило, а надо было бы писать быстрое возведение в степень.
Как ты предлагаешь решать без простейшей динамики?
если матрицу переходов возвести в степень k, то в в элементе g[i][j] будет храниться количество путей из вершины i в вершину j длины k
Может еще надо сделать в условии пирамиду с 10^3 вершин в основании, чтоб проходило только решение на листике рекуррентного уравнения?
P.S. Это я к тому, что ответ задачи — (3^n+3*(-1)^n)/4, что вряд ли большой секрет.
не понимаю о чём вы, я всего лишь сказал, что думаю, что умножение матрицы 10^7 раз это плохое решение. Я просто видел такие решения написанные немного по-разному, но некоторые получили AC, а некоторые упали по TL.
P.S. За формулу спасибо, к сожалению, во время контеста ко мне в голову она не пришла.
Как вывел формулу?
Извиняюсь, но не могли бы вы объяснить откуда берется эта формула?
Можно использовать известный метод решения "линейных рекуррентных уравнений". Например, вот тут на слайдах он обосновывается. Метод вам дает общую формулу в виде суммы степеней "частных решений" уравнения. Грубо говоря, вы (1) находите эти самые частные решения, и (2) находите коэффициенты, с которыми они входят в общую формулу. Частные решения не обязаны быть рациональными (пример -- числа Фибоначчи), но в этой конкретной задаче они таковы.
За 10 минут до конца отослал решение 3-й задачи, но до сих пор вижу "В очереди". Это нормально? 1397124
Терпение, терпение. Вы можете открыть вкладку "Статус" и увидеть время посылки последнего решения, которое система начала тестировать.
Да, нормально.
Посылки проходят финальное тестирование в порядке отсылки, т.е. чем раньше отослал, тем раньше протестировалось.
Лол, в D обычный Кун зашел, без всякой фигни с DSU которую я забыл с Петрозаводска
Кун ведь за куб работает, как он зашёл?
Да это я еще оранжевый, вон у tourist он за логарифм от числа вершин будет работать
А на каком тесте Кун валится?
Да вроде за-TL-ить его можно, поиск в глубину у меня идет втупую, а можно как-то не пускать его втупую, а за O(1) переходить (потому что ребер из вершины всего две)
Ага, я в ПТЗ слушал :) Там я не догадался как потом восстанавливать ответ, т.к. мы скипаем некоторое множество вершин, у которых рёбра меняем же.
чёрт, у меня кун тлится. вроде мой рейтинг от dalex не сильно отличается, да и алгоритм вроде тоже. может из-за того, что я в птз не был :(
Мне понравилась новая система оценки.
Во-первых, больше похоже на ACM — надо поискать задачу похалявнее, прежде чем писать. Во-вторых, сложность задач реально отражена в таблице, хотя я считаю, что 3000 по задаче В — это много.
Действительно, B сдало намного меньше участников, чем D. Но при этом обе — меньше 1/32 общего количества. При любом дискретном способе определения очков будут подобные ситуации — одинаковая стоимость при большом разрыве и большая разница в стоимости при маленьком разрыве, но количествах сдач на границе разделения. Думаю, нужно делать это распределение как можно более плавным.
Согласен, D сдало в 6 раз меньше народу, чем B, а стоят они одинаково (и это печально). Лучше вводить более непрерывную шкалу.
Согласен, что планое лучше дискретного. С другой стороны, если будет плавно, то вроде бы одинаковые задачи, отличающиеся в пару решивших человек, будет выводить одну из задач вперед(незначительно, но достаточно, чтобы определить место)
В целом нововведение интересное, но лучше было бы о изменении правил сообщить в письме рассылки
On the Contest page, both of 114 CF contest are for DIV 1 ?
was problem B on today's contest about running the Graham scan after adding the points from both and checking the resulting one is the same as the original convex object?
I was wondering what point distribution the author had thought for the problem set ?
Контест был интересным.Но мне не понравилось то что задача Б была больше на геометрию чем на информатику, а так всё отлично было интересно.
А что в вашем понимании "информатика"? Решение геометрических задач в это понятие не входит?
Any tutorials coming?
There is Russian one
Я сдал задачу А, она прошла у меня все тесты. Но сейчас почему-то у меня осталась только задача С. В чём дело? Кому об этом написать?
Систесты так не думают
Всё понятно. А вот в 13 тесте 22 место занимает кманда решившая 6 задач, с 8 штрафными минутами. Но таких команд 2. Почему ответ 1?
13 тест не проходят решения, которые при равенстве по задачам сортируют штраф по убыванию, а не по возрастанию. Об этом даже в разборе упомянули.
Я сортировал по возрастанию! Можешь посмотреть Я понял почему моя задача не прошла, не понял почему там ответ 1, а не 2!
13 тест виден не полностью, последняя строчка скрыта. Видимо, на последней строчке как раз информация о команде, которая решила больше шести задач, поэтому в действительности у 6/8 не 22-е место, а какое-то бОльшее.
Никому. Читать формат соревнований.
Внезапно на этом тесте ответ 3.
3 3
1 1
1 100
1 1
Please publish the editorial in English, is the second consecutive round that comes only in Russian. If not possible, some better than the google translator.
http://codeforces.net/blog/entry/4173?locale=en
Please provide the Editorial in English..otherwise wont get any benefit by mere participation !!
It's already published. http://codeforces.net/blog/entry/4173?locale=en
Thanks !! Please explain the approach to Problem E ie Tetrahedron.
Okay, the solution is DP. Let's number the vertices A, B, C, D from 0 to 3 instead, and let dp[i] mean how many cyclic paths currently begin and end at i. At first, we only have dp[3] = 1 and dp[0] = dp[1] = dp[2] = 0, and we only are considering paths of length 1. Now, to calculate how many cyclic paths of length n there are, you iterate n times, updating the DP table in the following manner (pseudocode): http://pastebin.com/XyNsyMk6
help!help!I got a WA on test #12,my code is [submission:1403496]，the former 11 tests are all passed, Who can help me find out the problem of my code?
You shouldn't
/4because 3^n is modular (try*(1000000008/4))Thank you for your help! :)
In order to divide on 4 by modulo of 1e9+7 you need to multiply by its inverse (found with extended gcd or basing on Fermat's theorem).
:)thanks a lot!