Всем привет!
4 марта в 15:00 начнется первый квалификационный раунд чемпионата VK Cup 2017!
Раунд продлится 24 часа, такая продолжительность выбрана для того, чтобы все нашли себе удобное время для участия. Квалификационный раунд, как и все предстоящие раунды, требует отдельной регистрации. Регистрация уже открыта и будет открыта на протяжении всего раунда.
При регистрации на любой из квалификационных раундов состав вашей команды фиксируется и не подлежит дальнейшей модификации. Вы не сможете в будущем добавить или удалить члена команды. Пожалуйста, перед регистрацией убедитесь, что у вас нет желания изменить состав. Состав команды не сможет быть изменен, даже если вы отмените регистрацию на квалификационный раунд.
Если вы пока не уверены в текущем составе команды, то не регистрируйтесь на предстоящий раунд. Если вы не будете участвовать в первой квалификации или не пройдете по ее результатам в Раунд 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: Ваши решения будут протестированы после раунда 403.
UPD 2: Решения протестированы! Поздравляем всех тех, кто набрал баллов не менее чем 500 место.
UPD 3: Разбор
Ждём с нетерпением!
Добавьте пример на Kotlin! 25204556
Registration for non Russians is not allowed?
I think it is not prohibited, but contest will be only on russian language
Sorry, this round is only for Russians. We have plans to open other rounds of VK Cup for everyone as rated rounds.
Почему я не могу зарегистрироваться?
Это этап чемпионата. Сначала зарегистрируйтесь на чемпионат VK Cup (если удовлетворяете правилам участия).
Насколько я помню по прошлым годам, в квалификациях количество получаемых баллов за задачу не зависело от времени, прошедшего после начала раунда. Это такая новая фишка что люди оказывается в невыгодных условиях: "такая продолжительность выбрана для того, чтобы все нашли себе удобное время для участия", или же бага-фича, которая будет исправлена?
Мне одному кажется странным делать time discount в суточном раунде?
почему стоимость задач падает?
Парочка багов с регистрацией:
Куда обращаться с вопросами по системе регистрации? Может быть, я где-то не там ищу, но мне не удалось найти секции с контактами на этом сайте. Я отправил ЛС автору новости, но пока никакого ответа нет. Я боюсь, что это сообщение может просто остаться незамеченным до конца отборочного тура, а тогда уже будет слишком поздно. .-.
на главном сайте есть регистрация(справа)
Есть кто-нибудь без сокомандника? Не хочется в одиночку писать.
Шляпа какая-то. Ни одного гроба, который бы разделил слабых и сильных. Решаешь все задачи, проигрываешь по штрафу, а сделать ничего не можешь, задачи кончились. И так второй год подряд...
Сложно без штрафов решать? 24 часа есть, чтобы подумать перед тем, как отправлять. Можно даже стресс-тестить каждое решение, написать кучу тестов к каждой задаче за это время.
Я просто считаю пункт 1. поста http://codeforces.net/blog/entry/18026 droptable неоспоримой истиной, которую мы увидели тут во всей своей красе.
Есть же еще вторая квалификация, в которой пройти значительно проще по опыту прошлых лет. И согласен, что задачу можно протестить от и до
4 задачи с почти любыми штрафами, наверняка, будет <= 500 место. Много решений упадет на системных тестах.
Ну не знаю, немного идей приходит, на которых бы могло упасть на систестах.
B — когда сумма массива меньше, чем n - 1
C — когда k%2=1
D — когда не подсчитаны xor-ы больше 10к, или лонг-лонг в ответе, но судя по претестах, лонг-лонг в ответе есть.
На переполнение не было претестов
xor-ы больше 10к на претестах падает. :) Из-за этого у меня 2 отправки
Теперь даже решившие АБС с штрафом 1 проходят.
Systesting?
D можно решать и в бОльших ограничениях, если воспользоваться преобразование Фурье над двоичным кубиком: аналогичная задача, описание похожего подхода (отличие: считаем (A + B)(C + D) и (A - B)(C - D), и выражаем AC + BD и AD + BC как полусумму и полуразность).
Когда закончится системное тестирование?
Пока что всех интересует когда оно хотя бы начнётся.
Хорошо, когда оно начнется?
Только что закончилось.
Вопрос в другом, когда оно начнется???
Странно. Моё решение 25213245 по задаче D использует достаточно много памяти, однако тем не менее O(1).
И вердикт оно получило ML38.
решение еще закрытое — нельзя посмотреть((
Не похоже на О(1)
Спасибо, я неправ.
Ну так-то это и правда O(1), т.к. все циклы до констант. Правда не знаю тогда, что удивляет автора)))))
Да, тем не менее это именно тот ответ, который мне был нужен, потому что он объясняет ML.
С чем связан TL в 15 секунд в задаче C? Есть идеи, какое решение предполагалось [с таким большим временем исполнения] ?
идём минимально-лексекографически, если мы успеем после этого вернуться. ну и чётность
Возможно, чтоб решения на python'e и других медленных ЯП заходили
D за квадрат все решали?
O(MAX(a_i) * C(14, k))
за квадрат от чего? от кол-ва чисел или от макс числа?
от макс числа, ясно что за квадрат от количества не зайдет))
Расскажите контример к такому решению C:
Лексикографически минимальный путь:
LLLDDRDRDRDRLRLRLRLRLRLRUUUUULСпасибо!
Чёрт. Я придумал полное решение учитывающее такие случаи, но потом успешно убедил себя в том, что их не бывает и отправил более простой вариант.
Вот пример поменьше:
Ваш алгоритм выдаст: LDDRDULUUR
А правильно: LDDRDRUUUL
Все-таки, как нормально решать C?
Я делал так: нахожу лексикографически минимальный путь длины k, после чего иду от последней клетки в пути, проверяя, можно ли из нее успеть дойти до стартовой, если изменить суффикс пути. Как только можно, заменяем конечную часть пути от данной вершины.
А я сначала обходом в ширину строил матрицу расстояний w, чтобы для каждой клетки знать значение wij — за какое минимальное количество шагов я могу вернуться из неё в начало. Потом строю лексикографически минимальную строку, на каждом ходу проверяя для данной клетки (i, j), не равно ли количество оставшихся шагов значению wij. Если в какой-то момент это равенство выполняется — восстанавливаю путь назад по матрице расстояний w.
Сложность получается O(n·m + k), где n·m даёт первый обход, а k — построение пути.
Почему в VK можно посылать сообщения самому себе, а в задаче B VK Cup-a — нельзя? :(
В задаче же ЕстьКонтакт, а не VK
Можно узнать 49 тест для задачи С?
Он как раз на то, что не всегда выгодно зеркалить первую половину пути. Вот этот тест из коммента повыше вполне ломает такое скорее всего.
Я не могу понять в чём ошибка?
можешь
Будет ли разбор, и если уже есть, то скиньте пожалуйста ссылку.