Напоминаю, что в 20:00 по Москве состоится Round 2C TCO 2013. Топ 50 проходят дальше. Топ 117 гарантированно получают майку. Все, кто уже прошли могут поучавствовать в параллельном раунде. Удачи!
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
30:15:31
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
30:15:31
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 11:19:29 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
Контест — говно. Я до клара считал количество танцев, а не количество песен. Пришлось ресабмитить. Думаю, у многих была такая проблема.
В итоге c примерно 150 места упал на примерно 400-ое. Реквестирую анрейт.
А анрейта нету. Карма топкодера скатывается в минус бесконечность.
Что за клар? Что за песни? Что за танцы? oO Такое ощущение, что 2C Parallel был каким-то другим...
В 250 лисички танцуют и знакомятся друг с другом. Может, и правда другой был.
Ну да, в 250 в графе можно было за 1 шаг добавлять паросочетания, удовлетворяющие каким-то свойствам, и надо было вернуть минимальное число паросочетаний; никакого клара не приходило. Неужели там что-то другое надо вернуть?
По крайней мере все не упавшие на челленджах решения у меня в комнате считают точно так же. Так что присоединяюсь к вопросу — что за клар? Что за песни?
Клар пришёл в 20:41:
You need to count the minimum number of dances. A dance in the context of this problem is an event when a single song plays and 0, 1 or more pairs dance at the same time.
Аааа, забавно, нам такое не приходило:) Но, имхо, это как-то совсем очевидно.
Я решал такую задачу: "найдите кратчайший путь, а потом посчитайте ответ следующим циклом":
Как это доказывается?
Рисуем на бумажке, понимаем что так оптимально
1) Докажем, что после добавления одного паросочетания кратчайший путь будет не короче. Действительно, рассмотрим кратчайший путь в получившемся графе, некоторые из его рёбер были из добавленного паросочетания, аккуратно всё распишем — получается то что надо (я это проделывал на контесте :( ).
2) Заметим, что эта оценка достигается тривиальными преобразованиями кратчайшего путя.
В клинических случаях, как у меня — сначала решал для песен (ведь логично, вроде бы, что для них спрашивают... хотя бы потому, что слишком просто в случае танцев), написал бажное решение, не мог найти баг, посмотрел, что все отлично сдают — переписал на решение для танцев, с радостью заслал... И как раз получил клар)
Согласен, очень у многих было такое. Из тех, кто был в топе в начале контеста, очень многие упали (следовательно, решали не то), и многие сделали ресабмит (следовательно, тоже решали не то).
Какой процент Passed по первой задаче должен быть, по нормам ТС? Сегодня что-то явно не вписались)
"что слишком просто в случае танцев" "Какой процент Passed по первой задаче должен быть, по нормам ТС? Сегодня что-то явно не вписались)"
На лицо противоречивые параграфы:)
На мой взгляд, самая сложная 250ка за 3 вторых раунда.
Противоречия нету. Если бы надо было найти число танцев, а не число песен, то задача, вроде бы, слишком простая даже для 250 SRM DIV1, не говоря уже о ТСО. Вот и "слишком просто".
А так и задача более сложная, и едва ли не половина участников решали не то, поэтому Passed кот наплакал. Вот и "явно не вписались".
Да уж... Или у вас прямые руки, и вы решаете хотя бы две задачи, или же играете в рулетку, которую довольно эмоционально описал pkhaustov вот здесь. Интересно, так и задумывалось?..
Что за рулетка? Что-то мне подсказывает, что (почти) все 1000 попадают. Рулетка там скорее на челленджах :)
То, что pkhaustov "числом дебилов в комнате" — вот о какой рулетке я говорю.
Сегодня она для очень многих решала, в какую сторону у них рейтинг изменится, и, как показали результаты тестирования, некоторым она даже подарила место в следующем раунде.
Число дебилов в комнате — всегда очень важный показатель на TC (точнее, отношение числа дебилов к числу папок, которые их челленджат). Так что это скорее претензии к алгоритму разбития на комнаты.
Да, согласен. Но в обычные дни он менее важен. Посмотрел последние 2 SRM и стату по div1 easy. В прошлом матче на челленджах упало менее 10% изи, в позапрошлом — менее 5%. А сегодня что? Даже если учесть статистику по всем задачам, а не только по easy — все равно перекос дикий.
Хорошо еще, если в задаче есть какой-то хитрый особенный случай, о котором все забыли, и некоторым он приходит в голову, как следствие — эти некоторые ломают едва ли не всю комнату. Они заслужили на это. Но когда матч превращается в соревнование между 10 пользователями, которые понимают, как выглядит правильное решение, за право взломать 10 пользователей, которые этого не понимают, но заслали решение, проходящее претесты — это бред. Хотя бы потому, что я уже знаю минимум одного человека, который сегодня потерял 1 или 2 челленджа из-за того, что у него была очень плохая связь с интернетом, и он не успевал на 2-3 секунды.
И я его отлично понимаю, так как и сам раньше бывал в таких условиях.
Мне сейчас на самом деле интересна позиция автора и организаторов — планировалось именно такое, или же планировалось, что все будет не так страшно, или же все испортило недопонимание разницы между танцем и песней...
Мне кажется тут проявилась специфика задачи. Ответ это какой-то странный логарифм от маленького числа. Плюс не очень сильные претесты, поэтому многие просто подогнали свое не работающее решение, дописав ифы.
ЧСВ over 9000
Я один думал, что в 550 ограничение 0 <= кол-во заполненных клеток <= max(50, N*M) играет важную роль и поэтому кинулся O(N^2 * 50^2), сжимая поле после выбора A и B (ведь кол-во значимых колонн/строк <= 50, остальное простая арифм. прогрессия)?
Мало участвуете в топкодере. Там всего всегда до 50 по техническим (или историческим?) причинам.
Когда хотят, они могут сделать до 2500 чисел (50 строк по 50 символов).
а для того чтобы запилить четырехзначные числа, 4 таких матрицы. Спасибо им, что делают так нечасто.
Насколько я знаю исторически причина была технической — арена не поддерживала челенджи массивами больше чем 50. Поправили это уже или нет я не знаю, а традиция осталась.
Parallel Round оказался начисто почелленджен, ни одного упавшего на сис.тестах решения. Забавный контест.
550 я умею делать, но это просто ******.
Я придумал решение за O((n + m) * n * m) через мердж четырех динамик, получилось 278 строк копипастного кода, додебажить эту гадость я не успел. Как решать задачу по-человечески?
Реализовать вычисление динамик без копипасты кода?
Именно так и решать. Квадратичный предподсчет можно не копипастить, а засунуть в цикл for, а вот обрабатывать крест я умнее, чем руками разбирая 4 случая не умею. Итого 162 строки с учетом небольшого дебага и пустых строк.
http://pastebin.com/mYsgdddJ
Я лично так и решал.
Только дп написал хитро через dx[i], dy[i], чтобы можно было не копипастить, а просто 4 раза вызвать функцию с нужным параметром.
Получилось довольно компактно.
UPD. http://pastebin.com/c4X8eXwx
Вот ещё вариант обойтись без размножения кода, на этот раз с четырьмя массивами «констант»: http://pastebin.com/1nXDsjfz.
Фиксировать макс. строку или столбец, а дальше мёрж двух динамик , тоже с копипастой.
Кто-то уже посчитал, какое место надо для футболки?
Как только 2C появится здесь, я обновлю таблицу.
UPD: обновил.
Screencast of the parallel round: http://youtu.be/ygaAWm0GMUY?hd=1
Непорядок:
Это видео c ограниченным доступом.
Сожалеем об этом.
Yes, that was stupid :) Should be working now.
Thanks!
Screencast
Everyone who has placed in top 143 in one of three rounds gets a T-Shirt. Round 2C results are not yet final, so it might change later. Table is here.
Number of competitors in Round 2 by country
Кому уже пришла футболка? Мне почтальон принесла примерно полчаса назад.