Здравствуйте!
Кто ещё не участвовал или не прошёл с QR 1 приглашаются на QR 2, который состоится в эту субботу (2 июня, в 11:00 по Московскому времени). Будет весело. Присоединяйтесь.
Мы постарались учесть полученные замечания. (Но я всё равно в жюри — значит, не все. :-)!)
Забыл. Предоставляю ссылку — http://russiancodecup.ru. И будьте точно уверены, что вы зарегистрированы...
До свидания!
P.S.: А первым 200 участникам полагается футболочка. Заметьте, вторую получить нельзя, если вы уже квалифицировались, так как Вы не можете участвовать в этом раунде.
P.S.: А вот и разбор: http://russiancodecup.ru/round/7/analysis.
**P.S.: Я попробовал ввести инновации и модернизации пока не совсем официально, спасибо спонсорам pashka и andrewzta за предоставленные айфоны для съёмки. Собственно, видео-разборы: http://www.youtube.com/channel/UCjum2OyCTe4wt_fkldljOrw?feature=mhee. **
Может быть, мы постарались учесть полученные замечания?
Спасибо за замечание.
Тяжело в личку написать?
А внеконкурсное участие почему нельзя? Обидка, могли бы и побаловать:(
В тренировках потом напишешь
Написать-то напишу потом, но пропадет половина интереса. Когда знаешь что 1000 человек по стране читает те же самые задачи что и ты — интерес совершенно другой. Ну вот почему нельзя сделать кнопку "вне конкурса"? Разве это сложно?
Нагрузка на сервер, и КФ с его мощными серваками так поступал на квалах, ибо очень много участников.
Ага, конечно. 200 человек, которые прошли квал в прошлый раз, + не сильно много сотрудников компании mail.ru, которые захотят писать этот турнир, разумеется, создадут гигантскую дополнительную нагрузку на сервер.
ну отборы GCJ и TCO проходят так же. видимо, какие-то причины на то есть.
На КФ по моему народу было 3-5 тыщ на квал(vk-cup) , а это необычно много для КФ.
Думаю 200 прошедших создадут сравнимую нагрузку с последними 1000-1500 участниками, ибо они сдадут задач по 5, не понятно с какой попытки, а не 0, с двумя попытками.
Ждем тренировку на Codeforces, чтобы тренироваться к отбору и финалу.
А можно ли провести зеркало соревнований на Codeforces для тех, кто уже прошел?
P.S.
Удачи всем, кто хочет квалифицироваться, но еще не квалифицировался.
Кажется, нет, так как тогда тут можно будет грязно отлаживать, ACM же.
Ваш Копетан.
Вань я добавлю тренировку и поставлю на какое-нибудь время чтобы было похоже на зеркало) (наверное сам тоже напишу)
Только давай после IPSC
И после TCO 2C ;)
Давай после сессии ))
В 1 задаче будет ошибка и раунд признают нерейтинговым?
Ну да. Вон прошлый квалификационный уже признали нерейтинговым.
wtf?
Рейтинг изменили? Не изменили.
True story
У меня сайт не грузится. Похоже, у других всё в порядке...
пост про то, что тестирование любой задачи в 6 минут — это очень плохо и что хорошо было бы заиметь больше тестирующих машинок
AFAIK это проблема веб морды — andrewzta говорил, что в самой системе все работает быстро и очередей почти нет
Тогда огромное спасибо mailru за unfriendly тормозную веб-морду
У меня так со всем задачами, по которым отправлял решения, кроме D. По D вердикт не приходил аж 25 минут... (это после сообщения о том, что "По задаче D на тестирование может уходить до 5 минут. Все прочие задачи тестируются быстрее")
В этот раз проблемы действительно были с очередью — в задаче D у нас было 89 тестов и многие решения работали довольно долго.
Мы уменьшили число тестов, но очередь так и не догнала real time.
Как насчет того, чтобы сделать pop-up окно, которое сообщает вердикт? Очень неудобно постоянно обновлять страницу в ожидании.
А еще лучше, чтобы 2 раза не вставать, просто разрешить пользоваться отличным клиентом
думаю это вопрос к представителям не итмо, а к трешхолдинга
Думаю, уже можно спросить, осталось меньше минуты.
Как решать C?
Я перебирал все перестановки сторон и делал следующее: строил на одной из сторон два треугольника, смотрел полученные координаты вершин (два варианта — вершины треугольников по одну сторону от общего основания или по разные), смотрел расстояния между вершинами полученных треугольников и требовал чтобы оставшаяся 6я сторона лежала строго в промежутке между этими расстояниями. (потому что их максимум — это случай когда две вершины по разные стороны, и двугранный угол между треугольниками 180, а минимум — когда 0)
Перебираем все перестановки сторон, проверяем для каждой грани неравенство треугольника, считаем квадрат объёма, проверяем, что он положителен.
Как это? Квадрат — он же должен быть всегда положительный? Или каким образом вы это проверяли?
Квадрат еще может быть нулем.
Точно, спасибо :) А то все перебрал, неравенство проверил, но про объем не подумал
Формула может выдавать отрицательное значение, т.е. получается точно не тетраэдр.
А объём как-то красиво считается?
Я использовал огромную формулу, в книжке она выводится из матрицы (точнее, её определителя).
пф, т.е. вы её не выводили, а откуда-то списали? )
Да, я её честно списал из книжки.
http://en.wikipedia.org/wiki/Tartaglia%27s_formula#Volume_of_a_tetrahedron
Как найти квадрат объема?
UPD. Воспрос снят
Формула достаточно громоздкая, чтобы писать её здесь, dalex скинул ссылку, где можно о ней прочитать: http://www.mccme.ru/free-books/mmmf-lectures/book.21.pdf
Самое печальное то, что эта книга у меня есть. D:
+1))
не читайте
В Е верно такое:
1. ( -> + 1, ) -> - 1 (баланс);
2. Бинпоиском находим отрезок минимальной длины с минимальное суммой на нём 0 (с помошью дерева отрезков, которое возвращает подотрезок с минимальной суммой с хотя бы одним элементом из массива).
Не успел дописать, чтобы с хотя бы 1 элементом возвращало. :)
UPD: не проходит по TL :(
Я писал sqrt-декомпозицию, на мой взгляд, такая реализация проще, чем за O(n log n).
У меня sqrt выдавала ТЛЕ.
В задаче D выдавало WA 6, когда поставил условие
if (d > m) { cout << "Impossible"; return 0; }Разве это неправильно?
Задача может не затрагивать ни одной темы
Неправильно. Некоторые задачи не содержат никаких тем.
Ну и зачем такие подставы надо было делать?
Ну почему же подставы? Об этом же написано в условии.
ki (0 ≤ ki ≤ m) — количество тем
в чем подстава то?
В том что такое условие неочевидно, а раз оно неочевидно, надо где нибудь жирно об этом написать. Или в семпл дать.
...или читать внимательно условие.
Че вам все жирно-то надо. Читайте внимательнее.
Ну если в задаче 3 параграфа бессодержательного по большей части текста, то можно и выделить. Это же просто пожелание, не требование.
В задаче B ведь бинпоиск + хэши? Если нет то как?
Как решать D?
Отсортил задачи по сложности, и сделал dp[максимальная сложность][маска взятых тем].
До сих пор не понимаю почему во втором тестовом примере ответ Impossible =(
В В да. D — динамика на битовых масках(состояние — маска и число обработанных уровней).
B: Перевернём строку, далее находим самый длинную общую подстроку, которая начинается ещё и с одного и того же места в обеих строках (при равенстве самую близкую к началу).
O(n) + простейшая реализация.
Нет. Просто для каждой позиции записываем совпадает ли этот символ и симметричный ему, если да, то максимальная длина ответа, которая может достигаться в этом символе — значение в предыдущем + 1, иначе 0. После этого просто выводим максимальный ответ и то, где он достигается.
Вот черт. А у нашей команды сразу рефлекс: хеши+бинпоиск. Спортивное программирование головного мозга.
По-моему, нормальный рефлекс. Хеши не сильно сложнее пишутся.
Ну я 20 минут писал. А такое решение за 7 минут бы написал.
Я своё решение меньше писал, чем читал условие :)
Пожалел, что сначала взялся за С.
Я тоже писал минут 20. Но более простое решение еще придумать надо, а на это может уйти очень много времени.
Черт, я слепой, не заметил, что и справа и слева дописывают одинаковое количество символов. Поэтому я пока и зеленый...
Не, там всё проще... обычный перебор. :) Перебираем все возможные начала искомой строки, для каждого находим конец строки из расчёта, что искомая строка должен быть максимальным. Каждый раз счётчик начала строки увеличиваем на длину найденной строки + 1 (без этого будет O(n^2), и оно не уложится в TL). Из этого всего находим первый максимум.
B я делал так.
В D просто будем вести динамику dp[i][msk], где i — сколько мы уже взяли сложностей, msk — маска взятых тем. Переход простой: просто перебираем те задачи, у которых сложность i + 1 и у которых маска тем не пересекается с маской в состоянии. Казалось бы, все. Решение работает за O(2^m * (n + d)).
Я так сдал.
Идём с двух сторон
--пропускаем разные символы.
--собираем одинаковые
--если пересеклись указатели
----да-берём весь большой палиндром, конец
----нет-берём что нашли, идём в начало цикла
и так до конца строки
может помочь тест axlolya
ох уж это форматирование кодефорсес
axlolya — так и задумано?
Атож!
В задаче В я просто писал 2 указателя :) Коротко и быстро.
В B намного проще. Просто сравниваем символы i и n — i — 1 и увеличиваем текущую длину если равны, если не равны — обнуляем. Проход за линию.
B — одна итерация по строке...
Я вроде тоже задачу В за O(N) делал, но у меня был ТЛ3. почему? вот код
u = s[j] + u; работает за линию
итого квадрат
Так и хочется сделать с собой что-то нехорошее =_=...Криво прочитал условие 2-ой...Думал, что слева и справа может дописываться разное количество символов...И вместо элементарной задачи, писал суффиксный автомат(Точнее, не писал, а пытался понять, где криво скопипастил с емакса)....
Я так же прочитал. По-моему, такие вещи нужно выделять жирным шрифтом. Или КАПСОМ. Или ЖИРНЫМ КАПСОМ.
Я тот случай задачи решал за N * log^2 N — хеши и бинпоиск. Лишь когда тестировал, до меня дошло, что условие криво прочитал.
)))))ааааааа, ну если одинаковое то все ясно)
а решение с бинпоиском детальнее можно?(неплохо бы на pastebin)
Заметим, что если длина ключа — K, то всегда найдется ключ длиной меньше K. Снаружи бинпоиск по K.
Ну и внутри проверяем — найдутся ли в исходной и перевернутой строке две одинаковые подстроки длины K — для этого выписываем хеши всех подстрок длины K, сортируем и идем 2 указателями.
Зная длину ключа, несложно его восстановить.
Я тоже сначала неправильно прочитал, но написал просто за n*log^2(n). Ну то есть бин. поиск + хеши (в проверке бин. поиска мы перебираем подстроку этой длины, а потом ищем самое правое вхождение хеша перевернутой строки)
Вообще то бинпоиск+хеши за NlogN пишутся...
Перебираем строку без добавленных по краям символов (N), внутри бинпоиск по длине ответа (logN). Сравнения за O(1) делаются
мужики, я с вами
так и не сдал B :D
Я буду внимательно читать условия, я буду внимательно читать условия. Несколько раз. Медленно и вдумчиво. Вслух и с выражением. Слитый экзамен + слитый контест — это уже слишком.
кстати, я вот минут 10 пытался понять, что такое развёрнутая строка
всё-таки "развёрнутый" можно понять ещё как "расширенный", а вот "перевёрнутый" никак иначе понять нельзя
Ха-ха, я тоже судорожно искал поиском по странице определение термина "развернутая".
Опечатался в одной переменной в E. К сожалению, вердикт пришел только после завершения контеста. А посылал задачу за 5 минут до конца. Печально...
Я в Д забыл один break поставить, вердикт пришел минуты через 3 после окончания. хотя отправлял за 8 минут. Админам явно нужно поставить доп. компы для тестирований)
Что писать в месте учебы, если я выпустился со школы и не поступил еще в университет?
Почему в С не работает такое: перебираем перестановки, строим 4 треугольника(из 1 2 3, 1 4 5, 2 5 6, 3 6 4), смотрим что-бы они были положительной площади, и что-бы сумма площадей трех любых была больше площади 4го?
Потому что вместо тетраэдра может получиться выпуклый четырехугольник с диагоналями.
А как правильно ее решать?
Где-то выше уже написано. Можно проверить существование ненулевого объема. Для этого можно использовать формулу объема тетраэдра по длинам сторон.
Надо еще объем проверить на то что он положительный.
Первая же ссылка в гугле: http://www.mccme.ru/free-books/mmmf-lectures/book.21.pdf
Я делал так. Проверяем для каждой перестановки. Строим 2 грани с общим ребром (естественно проверяя для них неравенство треугольника) и смотрим, какое минимальное и максимальное расстояние может быть между их вершинами, не принадлежащими общей стороне (в первом случае они будут лежать в одной полуплоскости относительно общей стороны, во втором — в разных). Если последнее оставшееся ребро попадает в этот интервал, то ОК.
Мне одному показалось, что сегодня задачи были проще в несколько раз (в 3.5 примерно :), чем на первом квале?
сложнее или проще?
Проще :) Самое главное умудрился пропустить.
Нет, как по мне такой-же.
.
Имхо, это вполне кореллирует с тем, что и конкуренция упала на порядок. Достаточно было расторопно две легкие задачи решить. Собственно, что я и сделал, отлаживая весь контест параллельно C и D (хорошо что на RCC код не видно — за идиотские баги даже стыдно :-) ).
Выложат ли контест в тренировки CF?
Да
2012 Russian Code Cup, квалификация 2
А дорешивание не предусмотрено?
Дорешивание, скорее всего, выложат в тренировки CF, как после предыдущего раунда.
Ясно, спасибо. Не решал первую квалу, поэтому не знал)
Спасибо Aksenov239 за видеоразбор. Особенно мне понравился разбор задачи А — все четко, понятно, я смог разобраться во всех деталях реализации, хотя до этого не имел понятия, как решить эту задачу.
Объяснишь?
На правах К.О.
По задаче А действительно очень прохладный разбор.
я уж не знаю, о каком видеоразборе идёт речь (на сайте RCC есть только текстовый), но это — редкостное свинство в плане отношения к человеку
Aksenov239 помогал готовить этот и предыдущий раунд и, пусть у него были разногласия с сообществом во мнении "как должен выглядеть разбор", он согласился с большинством и в этот раз устроил разбор своей задачи такой, что должен устроить всех
что ж вам, блин, надо ещё? нравится подойти к побитому и пнуть его ногой?
яростно минусую
UPD: посмотрел разбор, теперь не понимаю вдвойне, какого фига вам от парня надо =/
я уж не знаю, о каком видеоразборе идёт речь
в посте ссылка на YouTube, там видео разбор
Ты сначала посмотри разбор по задаче А, потом скажи что он не веселый. Тогда и минусуй.
Веселый. Ну и что?
Видеоразбор для меня уместно дополняет текстовый. Например, я не понял текст разбора С, а авторское решение (ну, которое "честное", без гугления) в видео вроде слегка другое, простое и понятное. Спасибо Aksenov239.
Не за что. Спасибо.
Александр, спасибо, что вступились.
Что случилось с Alex_KPR? То про паленую водку затирает, то обвиняет непонятно в чем. Я написал — "спасибо Aksenov239 за разбор". Что в этой фразе тебе не нравится?
Александр, полностью с тобой согласен!
Спасибо всем кто участвовал... И поздравляю всех, кто прошёл в следующий раунд...
А можно узнать, почему я пропал из рейтинга? У меня было 2 задачи, штраф 21. Где-то около 130 места. Я обрадовался футболке, зашел в настройки, указал данные.
А сейчас в профиле, в строчке 2-го квал раунда у меня пусто, а в рейтинге по второму квалу меня тоже нет?
спасибо за видео-разбор, продвигайте эту тему далее!