13-го апреля в 12:00 вас ждет не совсем обычный раунд. Дело в том, что впервые за долгое время Gerald почти не принимает участие в подготовке контеста. Раунд подготовлен мной (как же приятно сделать раунд!), Nerevar-ом, не обошлось без помощи Gerald-а и Fefer_Ivan-а. Маша, спасибо за переводы!
Вас ждут классические баллы за задачи: 500 — 1000 — 1500 — 2000 — 2500.
А он же пересекается с опенкапом?
Да, я уже отвечал в другой теме. Скопирую ответ:
Этот раунд проводится по мотивам студенческой олимпиады г. Саратова и не может быть куда-то сдвинут. Типичный D2 раунд привлекает ~2500 участников — большинство из них не участвует в соревнованиях Открытого Кубка.
Мне кажется, если у вас есть команда и возможность написать Кубок — пишите Кубок. Если вы хотите поучаствовать лично или у вас нет возможности участвовать 5 часов — пишите раунд. Напомню, что раунд будет доступен в виде виртуального ACM-ICPC контеста, как и другие раунда Codeforces.
Ну а так как вы из Div1 — то уж точно вам лучше выбрать кубок, чем этот раунд.
sounds cool! Good luck
Good luck everyone
This round is writen by MikeMirzayanov.Sounds very good!Good luck to everyone!
MikeMirzayanov's round.... sounds nice! GL&&HF
I'm sure there will be nice questions :)
А где же традиционное: Спасибо Михаилу Расиховичу за систему?)
Мне кажется, самого себя благодарить как-то не очень)
Мне кажется, глупо комментировать шутки как-то не очень)
I new people join, What is hack?
Please help me?
**Just click here and you'll see.
Как решать задачу D?
Я написал жадник. Если пройдет, напишу.
UPD: Не прошла =)
В E предполагалось решение за O(n4)?
O(n3)
O(n4) / 30 проходит кстати.
Как решать D и E?
У меня была такая идея по Е — посчитаем матрицу кратчайших путей алгоритмом Флойда. После этого перебирая пары вершин для ответа, будем также перебирать все дороги из графа. Суммарно выходит O(n4). Судя по ограничениям, такое вполне могло влезть, если написать оптимально...
Или нет...
UPD: Конечно, не должно. Не умею я 500 в четвёртую степень возводить :(
Можете объяснить сэмпл в Е, пожалуйста? Я немного не понял условия.
Вот-вот. Я так сэмпл и не понял. Написал Флойда с возможностью восстанавливать пути. Затем перебирал s, t и для них считал количество дорог, восстанавливая путь от s до t. Итого О(n ^ 3), но в сэмпле я не разобрался.
I don't know, if I'm the only one, but really, it seems that problem B and Problem C are easier than problem A... :/
That was really funny round. Especially hacks for problem A. Also really nice tasks.
For C, I sorted the groups in descending order of the amount of money they paid and then the tables by their size — my soln didn't get accepted. What's the right way of solving it?
Your way is right. Sort groups in descending order of money, sort tables in ascending order by size.
Here is my code: http://pastebin.com/JD9AZmsb
What is the proof that Greedy works well for Problem C? I just assumed that Greedy was the right method, by intuition.
Roughly because of the fact that you cant split groups or give a table to more than 1 group.
Because, 1. You can't split the groups 2. A group holds the table till the very end
In problem A , I made 10 successful hacks , however my solution is wrong itself , but no one in my room hacked mine .. :D
hehe =_=#
It was a very good contest.............I enjoyed.........
this round trolled me: 46 place before pretests and 542 after )
At least I'm not the only one :-).
Прибежал на страницу отправки D в 14:00:10. Надеюсь, решение не получит AC, а то я расстроюсь :)
upd. Ураа, TL20 :) Хотя странно, вроде O(nlogn). Но, видимо, как обычно, руки кривые, что ж поделать.
Задачи средние, что-то понравилось, что-то было так себе, в любом случае, спасибо авторам, было достаточно интересно)
А также традиционная рубрика "поноем после контеста". И сегодня у нас в программе "о боже, какая бага!".
Решаю С первой. Достаточно долго — пятнадцать минут. Но тем не менее. Отправляю, получаю WA8. Долго ищу багу. Безрезультатно. Откладываю на потом. ... И вот я с нова её дебагаю. В программе была строчка
Table cur = set.ceiling(new Table(g[i].c, Integer.MIN_VALUE));
. В ней я ищу первый стол из оставшихся, на котором как минимумg[i].c
свободных мест, а если таких несколько, то с минимальным айдишником (для этого второй параметр и стоитInteger.MIN_VALUE
). Думаю, люди, знающие, как работают компараторы в Java, а также примерно по мне представляющие, какой я раздолбай, уже поняли, в чём суть. А кто не понял, поясняю. Вот код компаратора для классаTable
:Что же здесь не так? Когда сравниваются два объекта, у которых равны первые поля, а также у первого из которых в поле id стоит
Integer.MIN_VALUE
, происходит переполнение, которое приводит к неверному сравнению объектов.Заменил
Integer.MIN_VALUE
на-1
, которое тоже отлично справляется с ролью "минимального возможного, но несуществующего айдишника" и получил AC на 55 минуте. Иии... -400 баллов из-за такой вот чепухи.И, пожалуй, на сегодня всё с рубрикой "поноем после контеста"! Будьте внимательней при написании своего кода, не допускайте баг, как у дурачка автора поста, и удачных вам контестов ;)
upd2. Хм, странно, E получила WA, хотя решение весьма тупое и прямолинейное. То есть оно могло бы получать TL или ML, но никак не WA. Эх, и снова руки-крюки в деле, да что ж ты будешь делать.
Когда будет разбор?
Как обычно — никогда. Здесь таких слов не знают.
а почему минусуем? Майк обычно разборы не пишет, что правда, то правда
Вообще-то это не так. Мой комментарий на самом деле был неприкрытым сарказмом, т.к. сейчас публикуют разборы ко всем раундам на кф. Очевидно, что и в этот раз разбор должен появиться, следует только подождать.
Видимо ты прав
Сам не ожидал Оо
Can anyone give me a hint for Prob E ?
Floyd-Warshall?
If we have 2 sets — a, b is it possible to insert all elements of b into a faster then b.size() * log(a.size()) ?
Расскажите жадник в С. Я писал дпшку.
Ну идем по заявкам в порядке уменьшения прибыли, пытаемся посадить компанию за еще не занятый столик, если это можно сделать, занимаем подходящий с наименьшим количеством мест.
И правда, действительно все просто) Как-то я до этого не додумался.
Is this possible to see what input a participant used to hack?
Yes, open http://mirror.codeforces.com/contest/416/hacks. find the row for you and double click on verdict column.
Is there any way to limit the hacks to certain user? I was trying to find the ones I used for a friend (I eventually found them all by scrolling down the page, but wondering if there's an easier way).
Try clicking on the arrow on the upper-right corner and typing "bli0042".
sneaky :) thanks
Here
Thanks a lot. My bad for not seeing it
Round stats
Как решать D,E?
Я решил D, стараясь жадно набирать прогрессии.
Пусть мы в начале новой прогрессии. Идем, пока не наберем последовательность вида
-1 … -1 a -1 … -1 b
, где-1
может быть и нулевое количество. Если вдруг не наберем, то все хорошо, заменяем все-1
наa
или на произвольное число (в случае отсутствияa
). Если наберем, то понятно, что заменить минус единицы, чтоб получилась прогрессия можно единственным образом.Тогда если эта прогрессия плохая, т.е. знаменатель нецелый или минус единицы придется заменять на
<=0
, то беремb
, как начало следующей прогрессии (а всё предшествующееb
будем считать стационарной последовательностью).Если все ок, то тогда мы знаем все последующие члены этой прогрессии. Идем дальше, как только встретим несовпадение (или члены вдруг станут
<=0
), берем первый неподходящий элемент, как начало новой прогрессии.good contest! I did today.
My greedy approach for D didn't work. Can you tell me why? 6357863
Because on the test #53 we need at least 5 sequences, but your program has written 4.
Surely it's obvious. Maybe you can fix it for few so that it can be right
Editorials??
Since there are not any tutorial.Can anybody explain the method to solve problem D.
Here it is