Всем привет!
7 марта в 18:00 начнется первый квалификационный раунд чемпионата VK Cup 2015!
Раунд продлится 24 часа, такая продолжительность выбрана для того, чтобы все нашли себе удобное время для участия. Квалификационный раунд, как и все предстоящие раунды, требует отдельной регистрации. Регистрация станет доступна 7 марта в 00:00, она будет открыта на протяжении всего раунда.
При регистрации на любой из квалификационных раундов состав вашей команды фиксируется и не подлежит дальнейшей модификации. Вы не сможете в будущем добавить или удалить члена команды. Пожалуйста, перед регистрацией убедитесь, что у вас нет желания изменить состав. Состав команды не сможет быть изменен, даже если вы отмените регистрацию на квалификационный раунд.
Если вы пока не уверены в текущем составе команды, то не регистрируйтесь на предстоящий раунд. Если вы не будете участвовать в первой квалификации или не пройдете по ее результатам в Раунд 1, то вы сможете попробовать свои силы во второй квалификации.
Чтобы пройти в Раунд 1, вам надо принять участие хотя бы в одной из квалификаций. Из каждой квалификации в Раунд 1 проходят все команды с положительным числом баллов, которые набрали не меньше баллов, чем команда на 500-ом месте.
Пользуясь случаем поздравляем всех девушек-участниц с праздником. Спасибо вам за весну!
Во время квалификации задачи тестируются системой только на претестах, а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! Взломов, падения стоимости задач во время квалификации не будет. Время сдачи задач не будет учитываться, однако будут учитываться штрафные попытки.
Категорически запрещается публиковать где-либо условия задач/решения/какие-либо мысли и соображения о них до окончания раунда. Запрещено обсуждать задачи с кем-либо кроме вашего сокомандника. Будьте честны, пусть в Раунд 1 пройдут сильнейшие!
Результаты раунда не будут влиять на рейтинг, внеконкурсное участие в раунде не разрешается. Однако, после окончания раунд станет доступен всем для дорешивания, а его задачи попадут в архив в том числе и на английском языке.
Если вы впервые участвуете в соревнованиях подобного рода, ознакомьтесь с одной из задач 158A - Next Round квалификационного раунда чемпионата VK Cup 2012, а также примерами ее решения на разных языках программирования:
- C++: 8130525
- C#: 3794163
- D: 2060057
- Go: 7573616
- Haskell: 1265143
- Java: 4244817
- JavaScript: 5743720
- Ocaml: 2698642
- Pascal: 5832593
- Perl: 9483942
- PHP: 4475965
- Python: 2475538
- Ruby: 7939472
- Scala: 2456025
Желаем удачи и удовольствия от решения задач!
UPD 1: Ура! Квалификация 1 закончена, все решения протестированы. В Раунд 1 квалифицированы все те команды, которые набрали 1500 баллов или больше. Таких команд оказалось 789, поздравляем их всех! Те из вас, кто не набрал 1500 баллов могут не расстраиваться, ведь 14 марта стартует Квалификация 2.
UPD 2: Опубликован разбор задач.
Пользуясь случаем поздравляем всех девушек-участниц. Спасибо вам за весну!
А название потом менять можно будет?
Ответ — нет :(
Хотя это явно нигде не указано.
а можно пожалуйста ссылку на правила соревнований? а точнее список языков=)
Клик
чуть подробнее
Другие раунды будут рейтинговыми?
Вроде бы будут рейтинговыми, кроме уайлд-карт.
"7 марта в 18:00 начнется первый квалификационный раунд чемпионата VK Cup 2015! Раунд продлится 24 часа, такая продолжительность выбрана для того, чтобы все нашли себе удобное время для участия." Очень странно выбрали время старта. Вот очень странно, но кажется что 8 марта днем писать квалификацию мало кто захочет. Лучше б в 9 утра стартовали.
Зато 8 у всех выходной, а 7 и 9 — не у всех. В выходной проще время найти, даже если часть дня вы собираетесь заниматься чем-то связанным с праздником.
спешу не согласиться: 1. в России 9-е у всех выходной. 2. Я студент, мои друзья, участвующие в VK CUP, как и вообще многие участники тоже. Праздник он на то и праздник. Не знаю кто как, но я собираюсь его провести с девушкой, а не в компании дебагера. И многие мои знакомые тоже.
Ну у меня не выходной, например. (Я в России, да)
Ну я в этом не виноват. http://calendar.yoip.ru/work/2015-proizvodstvennyj-calendar.html
Нам в институте так пояснили: 9ое марта выходной, но учебный день. Т.е. студенты учатся, а всякие структурные подразделения института вроде деканатов и подобного отдыхают...
профком не торт. У нас выходной.
Отлично, одним конкурентом меньше)
Зачем тебе контест, если у тебя уже есть девушка?
А как связаны контест и девушка? Почему если есть девушка, то контест не нужен?
Что не так с моим комментарием?
Он не смешной
То есть "Зачем тебе контест, если у тебя уже есть девушка?" было шуткой?
попробуй догадаться:)
Ну, если девушка занимается программированием, то можно писать вместе в команде VK cup.(вместе проведете время, за полезным занятием:D)
как я понял, писать можно обе квалификации.
т.е. есть если одну команда напишет скверно( или очень скверно), но при этом ьаллов во второй наберет достаточно чтобы пройти в первый раунд, она проходит? и аналогично в том случае, если завалит вторую квалификацию, но затащит первую?
Да, если завалил первую, то можно будет поучаствовать во второй. Если прошел из первой, то официально во второй поучаствовать точно не выйдет. Возможно, будем пускать вне конкурса. Удачи!
А текст при регистрации уже сейчас говорит, что участие во втором квале будет вне конкурса
Значит так и будет.
спасибо
За задачу начисляются баллы, только если пройдены все тесты?
Да
В текущий момент — если пройдёт претесты. После завершения будет еще системное тестирование, и тогда баллы начисляются уже только за все тесты.
Регистрация команды — это и есть регистрация в первом Раунде? Или нужно дополнительно регистрироваться?
Сначала регистрируете команду в Чемпионат. Затем, если хотите участвовать в Квалификации 1, то на нее. При регистрации на Квалификацию команда "замораживается" и не подлежит редактированию в дальнейшем.
а можно ссылку на регестрацию в Квалификацию 1? Что-то не получается найти.
уже не требуется, нашел.
Можете, пожалуйста, скинуть ссылку на регистрацию в Квалификацию 1?
До какого момента времени доступна регистрация команды?
Скорее всего до окончания второй квалификации.
А если мне больше 23 лет, могу я написать раунд вне конкурса?
Нет, но я не думаю, что внеконкурсное участие в Квалификации носит существенную ценность. Большая часть раундов Чемпионата будет открыта для внеконкурсного участия. Ждем!
Сколько времени на решение?
Можно решать хоть всю продолжительность раунда — 24 часа. Надеемся, что многие команды потратят значительно меньше времени.
Создала команду из 1 человека (себя :)), но почему-то не могу зарегистрироваться. При регистрации в выпадающем списке "Выберите команду" не вижу моей команды. :(
Это только у меня такая проблема? Как ее решить?
Вы, видимо, просто создали команду в интерфейсе создания команд. Надо было создать ее в рамках VK Cup — для этого нажмите "Зарегистрировать команду" в меню раздела справа или в крупную ссылку-кнопку "Зарегистрироваться" в посте-анонсе Чемпионата.
Да, теперь все получилось, спасибо :)
Сделайте раунд рейтинговым!
Емае, что с задачей А не так? UPD: проверилось
распроверилось)
Сказано, что регистрация открыта в течении всего раунда. Где она?
It's so similar :) link Table shows accepted problems as wrong answer.
У нас у единственных нет доступа к соревнованию? UPD: всё работает
У нас тоже нет.
Ни обещанной возможности зарегистрироваться, ни доступа
Регистрация станет доступна 7 марта в 00:00, она будет открыта на протяжении всего раунда.
Почему нельзя зарегистрироваться на раунд с момента его начала, т.е. с шести часов?
Регистрация открыта, регистрируйтесь на раунд в любое время вплоть до его окончания.
А регистрации то нет. Может это часть соревнования :D?
Почему выдаёт "Нет доступа на просмотр соревнования?", при клике на "Квалификация 1" ?
Регистрация открыта, регистрируйтесь на раунд в любое время вплоть до его окончания.
Да вы не одни
Регистрация открыта, регистрируйтесь на раунд в любое время вплоть до его окончания.
Доступ открылся, регистрация где?
В моем профиле ссылка на соревнование со словами "соревнование уже идит"
В самой квалификации задачи отсылать нельзя, т.к. команда не зарегистрирована.
Я б принт скрин приложила, да не могу загрузить его. Где регистрироваться на квалификацию?
Сначала регистрируете команду в Чемпионат. Затем, если хотите участвовать в Квалификации 1, то и на нее. При регистрации на Квалификацию команда "замораживается" и не подлежит редактированию в дальнейшем.
Приглашение зарегистрироваться на Квалификацию 1 есть на странице сорвенований http://codeforces.me/contests, выделенное красным. Для регистрации на раунд необходимо уже иметь команду для участия в VK Cup 2015.
Проверка задачи в разделе "Запуск" не влияет на количество баллов ?
Нет, не влияет.
как регистрироватся на раунд?
Из моего ответа выше:
Чисто из любопытства, по какому параметру сортируются в таблице команды с одинаковыми баллами и местом?
Подозреваю, что никак. По таблице прыгают то вверх, то вниз с одинаковым местом.
В том в котором база данных их отдает.
Я помоему зарегистрировалься на VK CUP (команда — 3,14) но на соревнование 1 на дает отослать решение , можете помочь ?
Прочтите мои ответы по теме выше.
Системное тестирование случится сразу по окончанию квалификации или же через некоторый (возможно, очень большой) период времени?
Извините, но почему мы не можем отправлять решение задач? У нас выходит такая надпись. Хоть и мы сделали регистрацию.. => ("Для просмотра страницы вы должны быть зарегистрированы на соревнование");
_1_ _2_ _3_ _4_ _5_
I've registered the team, but when I'm trying to register on contest, it isn't listed. What should I do ?
Разбалловка: 500-1000-1500-2000
Кол. команд, которые решили(10:35 мск): 808-864-155-207
Вот так устроен наш мир :)
Все логично, это же квал. Зачем решать 1, если умеешь 2. Зачем решать 3, если можешь 4.
Может быть, но на мой вкус второй намного легче чем первый. Каждый человек, который знает, что такое if и for, может решить В, но не А.
А задачу D вообще на чём-то кроме С++ и Java реально сделать? Что-то складывается ощущение, что ограничение времени там выставлено исключительно под компилируемые языки.
Это нормальная практика в соревнованиях по программированию. Если ставить ограничения так, чтоб на всяких Python и Ruby можно было сделать, то на C++, возможно, будут проходить по времени неоптимальные решения. А под каждый язык делать свои ограничения довольно утомительно.
Из раздела про языки программирования:
Да ладно, а на C#, хасекле, Go, Scala и паскале не заходит? Кроме того, наверняка можно упихнуть на PyPy. Или под "чём-то кроме С++ и Java" понимаются всякие php и javascript'ы? (при этом не удивлюсь, если на js тоже впихивается)
Ну на PyPy не пробовал, а на Python3 у меня не уталкивается и до сих пор ниодного решения на Python не вижу. Хотя не исключаю неоптимальность моего кода, просто напрягает, что у всех остальных тоже оптимальности на питоне не хватает, а на плюсах что-то у многих влетает.
Это потому что большинство опытных участников пишут на C++ или Java. Возможно, упихивающие на питоне просто упихивают что-то не то. Отправлять решения на Python3, когда есть PyPy, — довольно странно, он же сделан как раз для улучшения производительности.
Когда контест будет в дорешивании (и если у меня будет время) — попробую впихнуть на PyPy, посмотрим, зайдёт ли.
Это было непросто, но я таки впихнул на питоне, даже с двукратным запасом: 10210744
Из интересных наблюдений: дерево интервалов слишком тормозное, надо использовать дерево Фенвика (не ожидал, что в Питоне оно будет настолько быстрее); встроенная сортировка питона ооочень тормозная.
Что же касается ваших решений, которые показываются на вкладке "Статус", — то они просто неправильные (потому что работают за 5000002 операций, такое ни на каком языке даже близко не зайдёт).
Это вообще огонь) Решение почти один в один, как у меня, но на питоне, а работает с такой же скоростью
Результаты сразу будут (в пределах пары часов)? Или через длительное время?
Результаты появятся быстро.
Судя по скорости системного тестирования, всё было уже частично оттестировано заранее?
Нафига до последнего надо было тянуть? :) извиняюсь за большой размер
Я бы посмотрел на них, если какая-нибудь задача не прошла бы претесты :)
Может в поезде ехали без инета.
А условия задач скачали из астрала
Эм. Ну я просто по опыту написал возможный вариант.
Почему из астрала? можно на посадке, например. Потом инета не было, послать никак не могли
Веселый коммент который даже заминусовать не получается :D
Запятые ставить тоже не получается?
Стресс-тесты гоняли, возможно
Матушку Вашу гоняли, возможно
Интересно, сколько бы плюсов набрал бы этот пост, если бы его автором был бы Bredor?
Вот они, двойные стандарты...
Предчувствую, что много решений D упадет
у все, у кого cin/cout должно упасть
Почему?
Потому что он не слышал про ios_base::sync_with_stdio(false); очевидно :)
Не, это, а также cin.tie(0) я применил :3
но предсказание было неудачным, это да
UPD: xотя нет, половина упала
на макс тесте у меня с этими фишками работает 4-5 сек
У меня локально столько же работает, но замеры в запуске говорят, что сервера кф примерно раза в 3 быстрее моего ноута. Так оно и вышло в итоге
тесты слабые! или у меня решение странное)) оно зашло в дорешку, время 2 сек; в то время на домашнем компе (4ГГц) работает не меньше 4 сек.
-02?включен, без него около 6 сек
Так как вы решаете C и D
(извините мой русский)
после считывания входных данных уменьшим количество порций по тем заказам, которые Поликарп смог разобрать.
Арррргх, отдебажил D через 40 секунд после окончания раунда... Когда откроют задачи для посылок?
мне одному хочется расчленить авторов задачи С?
Нормальная задача))
Жестче будет стереть им память и заставить решить свою же задачу
А есть какая-нибудь возможность посмотреть или скачать тест на котором завалилась эта задача?)
да . дважды щелкните по посылке и там под кодом будут тесты
Я попробовал в этом тесте найти 29955 строчку, но к сожалению там было только многоточие :(
Большие тесты на CodeForces не отображаются. Можешь только надеяться, что организаторы сами захотят выложить.
У меня первое решение прошло претесты, но я нашел антитест для него, поэтому ресабмитил. Засылал первое решение в дорешку, падает как раз на 29955 строчке. Вот мой антитест:
Ответ: NNYN. Ну а у вас, как и у меня YYYN.
Расскажите пожалуйста идею в D... Надо ли там строить дерево отрезков и если надо, то как?
да, я строил, дерево минимумов.
очевидно, что для отрезка [l1,r] ответ не превышает ответ для [l2,r] пр условии l1<=l2 поэтому заведем структуру данных (дерево отрезков минимумов), в которой будем хранить для i-го элемента расстояние до ближайшего равного ему справа (до которого мы уже дошли) тогда ответ на запрос будет минимум на отрезке [l,r] мы будем идти по массиву слева на право обновляя структуру, пусть мы сейчас на i-ой позиции проверим, может ли текущее число улучшить результат для какого-нибудь отрезка, при условии, что оно правое равное для этого смотрим индекс предыдущего равного данному пусть он равен j, тогда ближайшее правое равное j-му находится в i-ой позиции, значит нужно обновить элемент а для вывода ответа на входной запрос проверяем, не находимся ли мы в крайней точке какого-нибудь запроса, если да, то выводим минимум на отрезке этого запроса
UPD: есть более краткие решения, но я их не знаю))
Можно используя то же ДО на минимум написать так: Обработка запроса [l, r]:
Возьмем минимум на всем отрезке.
Если минимум(min1) больше длины отрезка -> ответ = -1, иначе перейдем к шагу 3.
Возьмем минимум(min2) на отрезке [l, r — min1].
Если min2 == min1 — это ответ. Иначе вернемся к шагу 2, присвоив min1 = min2
Сложность : m * log^2(n)
Как интуитивно можно доказать, что отрезок [l, r] будет каждый раз уменьшаться в 2 раза?
на каждом шаге либо отрезок уменьшается в 2 раза, либо минимум увеличивается в 2 раза. То есть всего может быть максимум
шагов. Классная идея, надо ее запомнить.
Худший тест для такого алгоритма:
соответственно минимумы начиная от центра слева направо :
Если суть алгоритма перенести на этот массив, то он становится таким: берем
cur = a[0];подходит — круто, не подходит, беремcur = a[cur];и проверяем снова. Соответственно, проверим мы только 1, 3, 7, 15, 31, 63 .. ячейки, из-за нечетности минимумов.Я решал бинпоиск + спарстейбл))
А можно корневую. Подсчитаем для каждой пары блоков i, j лучшую пару чисел, в которой первое число входит в блок i, второй в j. Получим для каждого блока (i) массив A, где A[j] -- лучшая пара из чисел, которые лежат в блоках i и i + j соответственно. Далее построим для каждого массива массив минимумов на префиксах, чтобы узнавать лучшую пару на нескольких подряд идущих блоках. После всего этого останется выделить последовательные блоки в каждом запросе, на них отвечать за O(sqrt(n)), пробежавшись по ним всем и раздвинуть границы, добавляя по 1 элементу (это очень просто, если для каждого элемента подсчитать ближайший слева и справа такой же).
Я решил двумя sparsetable на минимумы. Сначала на всем отрезке L;R ищем пару с самым левым правым концом (пусть L1;R1), потом на отрезке R1;R ищем правый конец пары с минимальной длиной, он и есть ответ. Обе пары наверное надо проверять на то, что они внутри запрашиваемого.
У кого-нибудь D по памяти падала? и почему?
У меня падала. Из-за того что в массиве изначально не было одинаковых элементов и построение дерева отрезков рекурсивно уходила вглубь бесконечно.
Ну, можно было поизвращаться. Сперва для каждой позиции найдем r — минимальное расстояние до такого же элемента слева. Потом выпишем все пары (r, pos) в возрастающем порядке. Считаем все запросы [left, right]. Далее фиксированная пара (r, pos) является "хорошей" (ответ r) для всех запросов с условиями left <= pos — r, right >= pos. На такие запросы можно дать ответ r и выкинуть их из рассмотрения. По сути нужно удалять прямоугольные интервалы. Для этого заведем дерево отрезков с подмассивами в вершинах (строим по запросам). Получится очень похоже на сжатое двумерное дерево. Всего точек будет O(nlogn), удаление каждой за O(logn). Итого: O(n*logn) по памяти, O(n*logn*logn) по времени. ЭТО ПРИМЕР КАК НЕ НАДО ДЕЛАТЬ. По памяти падает. Даже построить дерево не получается на макстестах.
Неправда. Ровно это решение у нас зашло "всего" за 2.25 секунды и 190 мб на плюсах (на джаве даже не пытался это отправлять на контесте)
На самом деле можно поддерживать массив min_left, в котором на i-й позиции находится запрос с самой левой границей среди тех, у кого правая граница равна i, а вместо "удаления прямоугольных интервалов" каждый раз делать итеративно так:
1) пусть left — минимум на отрезке [r;n] в массиве min_left.
2) если left > pos - r, закончить с текущей парой (r, pos).
3) иначе узнать, какой отрезок мы только что нашли, удалить его, и обновить min_left в соответствующей позиции.
4) вернуться к шагу 1)
Поиск минимума и обновление можно делать с помощью дерева отрезков. Это работает за O((n + m)logn) времени и O(n + m) памяти.
deleted
Я правильно понял, что все, кто решил первые две задачи с первого раза прошли квалификацию?) UPD: Уже прочитал=)
Именно так.
Забавнее будет, когда во второй квалификации (ввиду отсутствия сильных команд) достаточно будет решить одну вторую (а может быть и одну первую) задачу с первого раза.
задача В сама перезасылалась 2 раза, хотя мы ничего не делали, у кого-нибудь еще было такое?
deleted
Посылка на контесте: 10197994 TL28
Такой же код под GNU C++11 после контеста:10209490 АС
Такой же код под GNU после контеста: 10209797 AC
Тот же код переписанный на сканф/принтф после контеста: 10209570 АС
Тот же код с cin.tie(0) после контеста: 10209660 AC
теперь понимаешь
А кто-то и рад позлорадствовать?
Ну сам себе злой Буратино. sync_with_stdio(0) не работает так под MS C++. Ну и чередовать ввод-вывод без cin.tie(0) тоже весьма дерзко.
Прога работает на 28 тесте на грани , а при проверке нагрузка на сервер больше так что вполне понятно почему она слетела .
PS . За что этот коммент минусовать то?
Не, ресабмит под MS тоже упал по времени на 28 тесте
может кто-то объяснить идею этого краткого решения
http://codeforces.me/contest/522/submission/10201772
Сортим запросы по R, для каждого храним prev[i], когда идем по r-ам обновляем prev[r] на величину r — prev[r], таким образом у нас выходить за правую границу не будет.
Ответ находим деревом отрезков
А когда будет разбор? И будет ли вообще?
в комментах довольно подробно расписали задачи C и D. На счет A и B: A решается с помощью map<string, int> как два пальца об асфальт, из условия вытекает, что репосты будут в форме дерева. Достаточно хранить для каждого человека глубину в дереве. B — нахождение двух максимумов. С шириной фотографии все понятно, когда iый фотографирует, то ширина будет равняться sumw — w_i, где sumw суммарная ширина. А для высоты фотографии требуется хранить два максимума, т.к. высота при фотографировании iым человеком будет равняться hmax1 если iый человек не максимального роста и hmax2 в ином случае. Допускается что hmax1 == hmax2.
Хы точно, а я monotonic queue для максимума использовал.
deleted
А как будет проходить не квалификационные раунды? Интересует именно временной промежуток, т.к. живу на часовом поясе МСК + 6
Вероятно, в 8 утра, специально для наших восточных соседей
Ну хотелось бы хотя бы в 21 — 22 часа по моему времени начать :D
Можно ли посмотреть полный набор тестов? В тесте №6 задачи 3 у меня неверно считает строку 309 выходного файла... Вот тут
вот такой тест
Это не может быть он. Тут 3 блюда, а правильный ответ в 309-ой строке "YY"
Вот на этот тест выдаёт YYNN.
Я не понимаю Зачем некоторым людям таким, как Progmeistars, участвовать на кф раундах, если каждый такой раунд сводится к попрошайничеству решений у других участников (в основном из Казахстана). В этот раз я не поленился и думаю нашел доказательство его катания. До этого иногда я тоже находил, но решил отписаться впервые. Вот решение, которое он выпросил, 10204660. Удалив все #define и изменив название нескольких переменных, у него получилось такое решение 10205743. Сохранив при этом почерк. К счастью решение у обоих упало :) Народ Хватит ему давать катать!
Progmeistars: Progmeistars
Германия: e-maxx.ru, Cucazek
Одинаковые решения
B — 10198840, 10200077
D — 10202466, 10202444
C — 10206078, 10204660
Спасибо, эти пользователи уже несколько дней как забанены.
Дальше прошли 791 команд вместо 500. Это очень много. Будет интереснее.
Можно ли посмотреть полный набор тестов? В тесте №6 задачи 3 у меня неверно считает строку 309 выходного файла... Вот тут
В задаче C в условии сказано, что 2 ≤ m ≤ 100 000. Но в тесте №6 присутствует такой тестовый случай:
Спасибо, есть такое. Тесты исправил, пореджаджил все попытки. Теперь в Раунд 1 проходит 789 команд, а не 788 :) Справедливость восстановлена!
tqven deda sheveci me C s piroba normalurad dadevit bozishvileboo tqvena
"VK Cup 2015 — Round 1 (online mirror, Div. 1 only)" — втором дивизиону участвовать нельзя? Даже при условии, что в команде есть человек из первого дивизиона?