Блог пользователя Aksenov239

Автор Aksenov239, история, 10 месяцев назад, По-английски

Hello everyone!

The official contest is for UK and Ireland residents only. For other we will consider to provide the mirror.

We would like to announce “UKIEPC 2024: Spring Practice” programming contest which will be held online at 12:00-14:30 pm, 23 March. Our main goal is to promote programming for everyone in the UK and Ireland. This contest is targeted at novices and amateurs — we expect the problems to be of Div. 3 — Div.2 level in the terms of the site codeforces.com. Programmers with a rating higher than 1900 are encouraged to join our team of problem setters (look at the bottom).

Contest.

The date is 23rd of March. The start time is 12:00. The duration is 2:30.

The contest is in teams of two people and each team can use two computers.

The link to our group is: https://ukiepc.contest.codeforces.com/.

Organization.

Officially, everything is online. Please, fill the following form. Some universities can provide a local hub — but we leave the organization of such hubs to the hosts (however, we will help as much as we can). To become a host, please, fill the form.

Please note that this time anyone from the UK and Ireland can participate, not just university students!

Introduction.

We will make several events to introduce you to programming problems. Stay tuned.

For additional information, please, visit our website: http://ukiepc.info/practice/.

If you have further questions, please, contact [email protected].

P.S.: You have an opportunity to propose, prepare, and test problems under the guidance of ICPC World Champions and Medalists! So, if you are interested, please, fill the form. We expect that the preparation of a problem would be a smooth experience that will take some reasonable amount of time. Note that anyone can suggest the problem, but they will not be able to participate in the contest. We need lots of simple problems.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

Автор Aksenov239, история, 3 года назад, По-русски

Добрый день, уважаемые абитуриенты.

Приглашаю поступить к нам на КТ в ИТМО. Я буду краток.

Для тех, то рассматривает возможность поступать на ПМИ в ИТМО, у нас есть тёплый и ламповый чат: https://t.me/abit_ct. Там Вы можете пообсуждать направление с реальными студентами и преподавателями.

Больше информации про направление можно получить на страничке в ВК http://vk.com/ct_itmo.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится

Автор Aksenov239, история, 3 года назад, По-английски

Hello, everybody!

We would like to invite you to participate in the Mirror of The ICPC World Finals Moscow Invitational Contest. The original contest was made for the teams who cannot come to The World Finals in Moscow. They were competing for the medals and glory. The Invitational contest has already passed and the results will be revealed on October 5th.

The mirror contest will be held by almost standard ICPC rules with 10 to 14 problems. The difference from the traditional ICPC format is that your team can use three computers instead of one. The problems are expected to be of The World Finals difficulty. Also, the round will be unrated!

The problemset was prepared by NERC Jury Team with the help of many other people. The chief judge is Roman elizarov Elizarov. The jury members are Pavel PavelKunyavskiy Kunyavskiy, Georgy kgeorgiy Korneev, Evgeny eatmore Kapun, Ilya izban Zban, Niyaz niyaznigmatul Nigmatullin, Vasiliy SirShokoladina Mokin, Daniil danilka.pro Sagunov, Gennady tourist Korotkevich, Oleg snarknews Hristenko, Egor Egor Kulikov, Borys qwerty787788 Minaev, Pavel pashka Mavrin, Mike MikeMirzayanov Mirzayanov, Anton Paramonov, Bruce bmerry Merry, Zachary Friggstad Friggstad, Jakub Wojtaszczyk, David Van Brackle, and myself. (I hope I haven't missed somebody. :P)

I hope you will like the contest! Good luck and have fun!

UPD: The editorial is available here.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +300
  • Проголосовать: не нравится

Автор Aksenov239, история, 4 года назад, По-английски

Hello everybody!

After a long break I would like to announce the fourth Bioinformatics contest organized by ITMO University, Bioinformatics Institute, Rosalind and Stepik. The contest is sponsored by JetBrains, Yandex, Serokell, and Genotek.

The contest is hosted on Stepik platform. To participate you have to sign the rules.

The contest consists of two rounds:

The contest is prepared by the following team: Alexey Sergushichev, Nikita Alexeev, budalnik, demon1999, tourist, cdkrot, GShark, doreshnikov (all ITMO University), German Demidov (Center for Genomic Regulation), Andrey Prjibelski (CAB SPbU).

Are there any prizes?

  • 1st place – Whole Genome Sequencing
  • 2nd and 3rd – Whole Exome Sequencing
  • 4th and 5th – 23andMe or Genotek DNA Service
  • 1st–30th – Honorable Bioinformatics T-Shirt

Do I need to know biology?

The knowledge of biology is not necessary to solve the problems!

We wish that you will like the problems!

Good luck!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +254
  • Проголосовать: не нравится

Автор Aksenov239, 4 года назад, По-русски

Hello Codeforces!

My name is Vitaly Aksenov and I present you the new lesson in English EDU section. I will talk about Disjoint Sets Union (DSU).

A little bit about myself, I cannot brag about being red (International Grandmaster), however, I was twice and each time afterwards there was a revolution of colours on Codeforces. :-) Right now I am the Researcher in ITMO University in parallel and distributed computing (link). Also, I am in Jury Committee of several olympiads such as NERC, Bioinformatics Contest, Russian Code Cup and etc.

This is my first time to write a lecture so do not judge harshly. I hope you will like it!

I want to thank pashka for video editing, and thanks to pashka, MikeMirzayanov and niyaznigmatul for sharing the problems.

Go to EDU →

More about EDU section you can read in this post.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +751
  • Проголосовать: не нравится

Автор Aksenov239, история, 4 года назад, По-русски

Всем привет!

Я тут немного поднапрягся и записал занятие про систему непересекающихся множеств. Пока только на русском языке.

Итого, в нашем курсе уже шесть занятий:

Подробнее об учебном подразделе на Codeforces (и его β-тестировании) можно прочитать по ссылке.

Спасибо большое pashka за монтаж видео, а также спасибо pashka, MikeMirzayanov и niyaznigmatul за предоставленные задачи.

Перейти в раздел EDU →

Я знаю, что я не pashka, но я старался сделать так, чтобы это было не очень плохо. Надеюсь, что у меня это получилось, и кому-то это даже понравится и поможет получше разобраться в теме.

Буду очень рад конструктивным комментариям, чтобы я постарался сделать что-то лучше. Ваш фидбек очень важен для нас.

Всем спасибо и удачи на контестах!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +190
  • Проголосовать: не нравится

Автор Aksenov239, история, 6 лет назад, По-английски

Hello everybody!

I would like to announce the third Bioinformatics contest organized by ITMO University, Bioinformatics Institute, Rosalind and Stepik. The contest is sponsored by JetBrains, Yandex and Serokell.

The contest is hosted on Stepik platform. To participate you have to sign the rules.

The contest consists of two rounds:

The contest is prepared by the team from ITMO University: Alexey Sergushichev, Nikita Alexeev, Sergey Aganezov, GShark, YakutovDmitriy, Maria Atamanova, izban, VArtem, chavit and me.

Are there any prizes?

Please, visit the site.

Do I need to know biology?

The knowledge of biology is not necessary to solve the problems!

We wish that you will like the problems!

Good luck!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +35
  • Проголосовать: не нравится

Автор Aksenov239, 7 лет назад, По-английски

Hello everybody!

I would like to announce the second BioInformatics Contest organized by Bioinformatics Institute, Rosalind and Stepik.

The contest is hosted on Stepik platform. You can already register and become familiar with the rules and the testing system. Note, that you have to sign the rules, otherwise, you will not be able to participate.

The contest consists of two rounds:

The contest is prepared by the team from ITMO University: Alexey Sergushichev, Nikita Alexeev, Alexander Tkachenko, chavit, izban, GShark, VArtem and me.

For now, you could train on the problems of the previous year.

Are there any prizes?

Yes, there will be. As in the previous year we will announce them later.

Do I need to know biology?

This year we will try to make problems more real-life, so some knowledge of biology is necessary. But do not worry this amount of knowledge is not deep and could be learned during the contest.

What kind of problems to expect?

There will be two kind of problems: exact (ACM) and approximate. We encourage you to take a glance on the problems of the previous year.

Good luck!

UPD1: The Qualification Round has started!

UPD2: We added the description of prizes!

UPD3: Approximately, one day left for Qualification Round.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +71
  • Проголосовать: не нравится

Автор Aksenov239, 7 лет назад, По-английски

Better late than never.

World Champions Programming School (wcps.ifmo.ru) announces the third training camp in France on ACM ICPC. It will be held in Universite Toulouse III Paul Sabatier from October 30 to November 3. The school page is https://www.irit.fr/olymp_prog2017/. The coaches for this session are Vladimir Smykalov (enot110, ICPC World Champion 2017) and Grigorii Shovkoplyas (GShark).

Note, that there are no registration fees, but the registration is obligatory.

Hope to see you there!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +47
  • Проголосовать: не нравится

Автор Aksenov239, 8 лет назад, По-русски

Hello, everybody.

Probably, you know that we will have a broadcast of the ACM ICPC World Finals this year. (As in previous years. :-)) We want to make some flash interviews with participants and other people related to the contest. BUT, we are quite bored with the standard interviews and the standard questions that are asked. We will give some boring examples: What is the first step to become a successful competitor? When did you start to code? How much do you practice? How your team is training? I understand that for someone they are still interesting questions, but on the other hand, they are very impersonal.

We would like YOU to HELP us create funny or interesting questions! (You could still pose the standard question and, probably, we will use it. But it is better to think out of the box)

Here are several examples:

  • AMD or Intel?
  • What music do you prefer?
  • How much the Chinese football team should pay you per year, so you would agree to play with them?
  • Your first/most memorable trophy/achievement in life?
  • If you have to teach programming to a (non-programming) celebrity, who would it be? And why?

Here comes the form: https://docs.google.com/forms/d/16I_fH2j8ljAoH9WFFMKoUNABTbDk29vd1FsbdSJnGhI/edit#responses.

Note: it is better not to post the questions inside the comments, so the inteviewees could not prepare. :-)

Thanks!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +51
  • Проголосовать: не нравится

Автор Aksenov239, история, 8 лет назад, перевод, По-русски

Hello everybody!

I would like to announce the first BioInformatics Contest organized by Bioinformatics Institute.

The contest is hosted on Stepik platform. You can already register and become familiar with the rules and the testing system. Note, that you have to sign the rules, otherwise, you will not be able to participate.

The contest consists of two rounds:

There will be prizes for Top 10-20, but they are currently kept in secret. (Note, there will be no money prizes. :-))

All other information related to rounds is located at FAQ.

Why bioinformatics?

We think, that this is one of the most important fields of modern applied Computer Science and we would like to introduce this field to everybody who is interested in something new aside from Olympiad Programming and Software Engineering :-). Probably, somebody will find it interesting and will want to choose this path in his career.

If there will be such a person in Saint Petersburg, Russia, you could apply for a one year course at Bioinformatics Institute.

What type of problems will be there?

We have ACM-style (exact) and Challenge24-style (approximate) problems. This is our first try to do contest with approximate problems, so we could not be sure that everything will go smoothly but we hope so. At least, we tried to prepare interesting problems. Do not worry, most of the problems should be solvable without a knowledge of biology.

Who prepares the contest?

The contest is prepared by the team from ITMO University: Alexey Sergushichev, chavit, Anna Malova, izban, GShark, VArtem and me.

Good luck!

UPD: The Qualification Round has started!

UPD2: Less than two days left till the end of the Qualification Round!

UPD3: Final round will start in 15 minutes!

UPD4: The standings could be found here.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +90
  • Проголосовать: не нравится

Автор Aksenov239, история, 9 лет назад, По-английски

Hi, everybody.

We would like you to join Live broadcast from ACM ICPC World Finals 2016. The broadcast will start at 8-00 ICT 19 May 2016, while the contest will start at 9-30 ICT. get more statistics afterwards.

The broadcast consists of two parts:

  • Main broadcast with comments from our analytic Egor. There will be presented all information about the contest, interviews and other interesting videos! Broadcast will be available in youtube and twitch.

  • Additional broadcast with videos from teams screens and web-cameras. This year you can influence what teams will be shown. For that, you should send the tweet in twitter, which contains #ICPC2016 and hashtag of the team. (The hashtags could be found in the page of each team under link social from MyICPC) If you prefer webcam to the screen, you could specify it with #camera. Examples of tweets: #ICPC2016 #ITMO, #ICPC2016 #ITMO #camera. We will show team if it gets enough votes. (Also, we count only one tweet per user per minute, so there is no need to spam votes) Broadcast will be available in youtube as second screen and twitch.

Also, we want to test our system tomorrow (18 march 2016) at 8-00 ICT. Dress rehearsal contest will start at 9-30 ICT, so all videos from teams and the second screen should be available starting from this time. Could you help us? :-)

At the end I want to mention everybody who is working on this broadcast:

  • Director: elizarov.

  • Script and beverages: lperovskaya.

  • Design of infographics and hardware: pashka.

  • Design of everything else: Mikhail Kutsov.

  • Video preparation: Viktoria Volochay.

  • Analytics and Creeping line manager: niyaznigmatul.

  • Analytics and commentator: Egor.

  • Flash zone interviewer: Charles Nevile.

  • Software developers: pashkal, Anna Malova and me.

Don't forget to subscribe on channels and tell everybody! See you on broadcast!

P.S.: We encourage you to use youtube rather than twitch. (Even if the twitch chat is more comfortable to use. ;-)) This will help us to get more statistics afterwards.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +117
  • Проголосовать: не нравится

Автор Aksenov239, история, 9 лет назад, По-русски

Здравствуйте, Уважаемые Друзья.

Мы решили постараться запустить экспериментальную видео-трансляцию с полуфинала. К сожалению, у нас будет очень мало активности, потому как настроить видео с экранов не успели. Ведущий трансляции: Egor. К нему будут приходить различные гости и помогать ему комментировать происходящее. В процессе трансляции ожидается разбор задач и всяческие комментарии к исходному коду участником.

Трансляция будет на twitch в 10:00 MSK.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +57
  • Проголосовать: не нравится

Автор Aksenov239, 10 лет назад, По-русски

Приветствую всех.

Команда ICPC Live, в составе elizarov, pashka, niyaznigmatul, Egor, lperovskaya и я, передаёт всем привет. И напоминает, что будет онлайн трансляция финала в среду 20 мая в 12 часов по Москве.

Трансляция будет на двух площадках (ютюб и твич). Правильные ссылки будут выложены завтра.

Планируется следующее расписание:

  • 12:00 — начало трансляции
  • 13:00-18:00 — контест
  • 19:00 — начало церемонии закрытия

Не забываем подписываться на каналы на youtube и на твиче: icpclive1 и icpclive2.

А пока прошу отметить, что во вторник 19 мая проходит Dress Rehearsal в 12 часов по Москве. Будет доступно прямое видео на канале youtube ICPC Live и на канале twitch ICPC Live. Цель: проверить, что Вы можете посмотреть, а не бить нас битами в подворотне. Нормальная трансляция с Dress rehearsal не гарантируется.

С уважением, команда ICPC Live

UPD: Читайте онлайн трансляцию. http://icpcnews.tumblr.com/post/119424970944/world-finals-live

UPD2: youtube

UPD3: twitch, main screen, twitch, split screen

UPD4: Спасибо alexyz за интересную ссылку: multitwitch

Полный текст и комментарии »

  • Проголосовать: нравится
  • +211
  • Проголосовать: не нравится

Автор Aksenov239, 10 лет назад, По-русски

UPD:Также специально для финала мы выпустили видео-разбор.

Задача A. Игра

Идея: Анна Малова
Реализация: Анна Малова
Разбор: Анна Малова

Рассмотрим двудольный граф — первая команда, вторая команда. На ребре написано, какими подсказками владеет участник второй команды, которые еще не знает участник первой, то есть разность множеств подсказок участников. Оставим только те ребра, на которых записано одно число. Среди таких ребер оставим только те, на которых записано только одно число.

Используя построенный граф, составим другой двудольный граф: вершинами первой доли являются участники первой команды, вершины второй доли — те подсказки, которые еще неизвестны первой команде. Между двумя вершинами есть ребро, если было ребро в предыдущем двудольном графе, выходящее из той же вершины, на котором была записана эта информация. Если в полученном графе найдётся максимальное паросочетание, значит, первая команда может выиграть. Иначе, первая команда выиграть не может.

Чтобы уложиться в заданные ограничения по времени, для нахождения разности множеств, нужно использовать битсет. Кроме этого, перед запуском алгоритма Куна для поиска максимального паросочетания, нужно сравнить размеры долей, если размер доли с подсказками превышает размер доли участников, то сразу выдается ответ 2. Без этой проверки, решение не укладывается в ограничения по времени.

Задача B. Покраска здания.

Идея: Виталий Аксёнов.
Реализация: Николай Ведерников.
Разбор: Николай Ведерников.

В задаче требовалось покрасить полоску в два цвета. Мы умеем красить любой подотрезок в какой-то цвет. Требовалось посчитать количество способов раскрасить полоску за минимальное число покрасок.

В данной задаче есть два случая: концы полоски покрашены в один цвет или в разные. Рассмотрим первый случай.

Концы покрашены в один цвет, значит, всего отрезков 2k + 1. Покажем сколько минимум покрасок надо. Рассмотрим конечную раскраску полоски, если последним отрезком мы покрасили отрезок в середине, то общее количество отрезков увеличилось на два (мы разбили какой-то отрезок на два и добавили новый). Таким способом мы можем извлечь k отрезков и в конце останется 1. Итого мы потратили k + 1 ходов. Если в какой-то момент мы взяли отрезок не из середины, а с края, мы потратим больше ходов, чем надо.

Теперь посчитаем количество способов. Рассмотрим конечную раскраску и последним ходом мы красили отрезок в середине, тогда количество способов выбрать этот отрезок равно общему число отрезков минус крайние, итого 2k — 1. Тем самым мы свели задачу к задаче меньшего размером. Продолжая таким способом, мы получим итоговый ответ (2k — 1) · (2k — 3) · ... · 3 · 1, что равно (2k — 1)!!.

Рассмотрим случай, в котором концы покрашены в разные цвета, тогда всего отрезков 2k. Рассмотрим конечную раскраску полоски. Пусть в начале мы l раз извлекали отрезки из середины, а потом извлекли отрезок с краю. Тогда мы потратили l + 1 и у нас осталось 2k-2l-1 отрезоков, причём концы оказались одинакового цвета. По предыдущим рассуждениям мы не сможем раскрасить это быстрее, чем за k-l. Итого: k+1 ходов* Кроме того, отсюда следуют факт, что мы первым ходом красим, отрезок с одного из концов.

Теперь посчитаем количество способов. Назовём первый отрезок черным. Пусть первым ходом мы покрасили отрезок с левого края. Переберем докуда он покрасит, а всё что справа от него надо будет покрасить в белый, по нашим рассуждениям. Заметим, что теперь у нас получились две предыдущие задачи, у которых концы покрашены в один цвет. Пусть в левом отрезке l черных отрезков, тогда ответ на этом отрезке будет ((2l — 1) — 2)!!, а на правом ((2k — (2l — 1)) — 2 )!!. Кроме того, мы можем можем красить отрезки из левой половины и из правой в любом порядке. То есть произведение отрезков надо ещё умножить на choose (l — 1, k), так как мы уже один отрезок покрасили, значит нам осталось сделать ещё k покрасок, а в левой осталось сделать l — 1 покрасок. Кроме того, первый отрезок мы могли красить и дальше, потому что мы поверх всё равно покрасим правым отрезком. А таких вариантов равно длина правой части. Итого, для фиксированого числа l ответ будет равен ((l — 3)!!) · ((2k — 2l -1)!!) · choose(l — 1, k) · (suff_lenl). Таким образом переберем l и просуммируем. Аналогично посчитаем для другого конца.

Если предподсчитать факториалы и обратные факториалы по модулю, то для одного l мы сможем отвечать за O(1). Итоговое время работы — O(n).

Задача C. Задача о рюкзаке

Идея: Борис Минаев
Реализация: Артем Васильев
Разбор: Артем Васильев

В данной задаче требуется найти такой тест для задачи о рюкзаке, что количество способов набрать вес W делится на число M.

Далее будем считать W равным 500. Основная конструкция авторского решения основывается на генерации такого набора n вещей небольшого веса так, чтобы их сумма была меньше W/2. Подсчитаем для этого набора количество способов набрать подмножество вещей с суммарным весом k для всех k от 0 до W/2 и обозначим это число за ck. Потребуем, чтобы для нашего набора любое число от 1 до 1018 представлялось как сумма не более, чем 200 — n чисел ck.

Предположим, что существует такой набор вещей, чтобы для каждого x было такое k, что ck = 2x, то такое свойство было бы очевидно: для каждого x, если двоичная запись M содержит единицу на позиции x, мы добавим вещь с весом Wx в наш набор. Поскольку сумма вещей, добавленных до этого шага, была меньше W/2, то легко видеть, что количество способов получить вес W равно M. Заметим, что такой процесс можно описать следующим жадным алгоритмом: пока M больше нуля, мы находим максимальное ckM, добавляем вещь с весом Wk и вычитаем из M число ck.

К сожалению, такой набор вещей получить трудно, поэтому необходимо придумать какой-то другой набор вещей, обладающий тем свойством, что вышеописанный жадный алгоритм находит решение для любого M. Для этого возьмем набор вещей со случайным небольшим весом и суммой меньше W/2. Можно проверить и убедиться, что если мы выберем наш набор таким образом и посчитаем для него числа ck, то жадный алгоритм с большой вероятностью вернет корректное разбиение любого числа M на слагаемые ck. Таким образом можно построить набор вещей, удовлетворяющий этому свойству, и с помощью жадного алгоритма добавить вещей таким образом, чтобы количество способов собрать W стало равным 0 по модулю M.

Задача D. Организация сети.

Идея: Борис Минаев
Реализация: Андрей Комаров
Разбор: Андрей Комаров

В задаче было дано дерево и требовалось пометить минимально возможное число вершин так, чтобы вектора расстояний от каждой вершины до выбранных были различны.

Рассмотрим отдельно случай, когда заданное дерево является цепочкой: вершины можно упорядочить так, что первая связана только со второй, последняя только с предпоследней, а остальные только с двумя соседями. Если дерево является цепочкой, то, очевидно, в качестве ответа можно взять один из концов этой цепочки: все вершины будут удалены от него на различные расстояния.

Иначе, в дереве есть вершина степени больше двух. Подвесим дерево за эту вершину. Посчитаем следующую динамику для каждого поддерева: минимальное число меток, которое необходимо поставить в этом поддереве, чтобы вектора расстояний для каждой пары вершин этого поддерева были различны, при условии, что где-то выше корня поддерева есть хотя бы одна помеченная вершина. Назовём значение этой динамики min↑. Заметим, что это не совсем то, что нужно посчитать в задаче, но это совпадёт с задачей, если убрать ограничение на существование выше корня помеченной вершины. Назовём эту динамику min. Заметим, что min↑ ≤ min. Значит, если мы сможем предъявить ответ размера ровно min↑, то это будет ответом на задачу. Решим задачу в два этапа — сначала посчитаем значения min↑, а затем получим ответ такого размера.

Пусть мы хотим посчитать min↑ для какой-то вершины v. Посчитаем эти значения для её поддеревьев. Получили, что в некоторых из них есть хотя бы одна метка, а в остальных меток нет. Пусть количество поддеревьев, в которых меток нет, равно k. Тогда в ответ для v нужно добавить хотя бы k − 1 помеченную вершину (по одной в каждое непомеченное поддерево, кроме одного). Пусть мы добавили меньше. Тогда осталось хотя бы два непомеченных поддерева. Тогда корни этих поддеревьев будут неразличимы: в их поддеревьях помеченных вершин нет, а до всех остальных расстояния одинаковы. Теперь покажем, что этих добавлений хватит. Рассмотрим любые две вершины из разных поддеревьев. Они могут быть либо на одинаковой, либо на разной глубине. Пусть они на разной глубине. Тогда расстояния от них до предполагаемой помеченной вершины над корнем различны (различны длины путей до корня). Пусть они на одинаковой глубине. Тогда, по построению, хотя бы в одном из поддеревьев, в которых эти вершины лежат, есть помеченная вершина. Тогда расстояния до неё от этих двух выбранных вершин будут различны: от той, из чьего поддерева выбранна помеченная вершина, расстояние будет меньше.

Построим теперь ответ размера min↑. У выбранного нами корня хотя бы три ребёнка. Значит, по построению min↑, хотя бы в двух поддеревьях корня есть помеченная вершина. Значит, для каждого поддерева есть помеченная вершина вне этого поддерева. Возьмём её в качестве требуемой min↑ помеченной вершины выше. Тогда ответом будет являться объединение ответов min↑ для всех детей корня.

Все рассмотренные операции можно сделать с помощью одного обхода в глубину. Значит, итоговое время работы — O(n).

Задача E. Булево дерево

Идея: Борис Минаев
Реализация: Демид Кучеренко
Разбор: Виталик Аксёнов

Для начала сведём нашу задачу к задаче об одной переменной. Заведём по дереву на каждую переменную, в которых в изначальном состоянии будут находиться корень изначального дерева и ссылка на него. Ссылка в дереве у нас всегда будет указывать на вершину, в чьём поддереве мы сейчас находимся. Обойдём наше дерево обходом в глубину. Если мы заходим в вершину, в которой выставлена какая-то переменная, то мы создаём у вершины в соответствующем дереве нового ребёнка и переставляем ссылку на него. Если мы выходим из вершины, то мы переставляем ссылку в соответствующем дереве на её предка Мы сжали деревья. Нужно ещё не забыть хранить в каждой вершине количество листьев в её поддереве

Мы теперь будем решать задачу на дереве для одной переменной. Будем обрабатывать все запросы на данную переменную последовательно. Нам нужно уметь делать две вещи:

  • на сколько листьев влияет только эта вершина
  • найти ближайшего предка, в котором выставлено какое-то значение для данной переменной.
Если мы реализуем это, обрабатывать запрос не очень сложно:
  • находим количество листьев, на которые влияет эта вершина — x;
  • находим ближайшего предка, в котором выставлено какое-то значение для данной переменной — p;
  • если в p такое же значение, что и в нашей вершине, то количество не меняется;
  • если в p другое значение, нежели в нашей вершине, то количество меняется на x;
  • если p не существует, то количество меняется на x* то количество “неизвестных” листьев уменьшается на x;
  • в p нужно уменьшить количество влияемых листьев на x

Чтобы реализовать запросы нужно развернуть дерево в дерево отрезков, где можно делать запрос на поддереве. Тогда запросы первого вида очень легко обрабатывать с помощью суммы в поддереве. Для поиска правильного предка сделаем следующее: когда делаем запрос в вершину, мы прибавляем ко всем вершинам в поддереве, кроме неё, единицу, то есть говорим, что они покрыты ещё одной вершиной. Тогда чтобы найти предка, мы будем искать двоичным подъёмом первую позицию, в которой значение отличается на единицу — она и будет искомым предком.

Итоговое время работы: O(mlog2n), где n — размер дерева, m — количество запросов.

Задача F. Робот.

Идея: Борис Минаев
Реализация: Борис Минаев
Разбор: Борис Минаев

В задаче необходимо было посчитать количество клеток, которые достижимы из первой строки поля. Основная сложность заключается в том, что размеры каждой стороны поля могут достигать 109 клеток.

Во-первых, из-за того, что робот совершает ходы по диагонали, удобно отдельно рассматривать клетки разной чётности. Робот может достичь все клетки первой строки поля. Будем увеличивать y и пересчитывать достижимые клетки. Удобнее всего хранить множество достижимых клеток для строки в виде объединения непересекающихся отрезков. Тогда можно легко пересчитывать множество при переходе к следующей строке. А именно, к каждому отрезку добавится по одной клетке с каждой стороны. Некоторые отрезки, возможно, объединятся в один, а некоторые пересекутся с границами поля или преградами.

Научимся эффективно изменять это множество отрезков. Лучше всего хранить его в структуре данных, которая позволяет за O(logn) находить отрезок, который пересекает заданную координату. Дополнительно, у каждого отрезка будем хранить информацию о том, может ли отрезок увеличится влево и вправо. Давайте аккуратно рассмотрим все события, которые могут происходить:

  • Два отрезка объединились. Это самый простой случай. Необходимо просто объединить их в структуре данных.
  • Отрезок расширился до такой степени, что пересекся с краем поля или преградой. Тогда необходимо поставить пометку в описании отрезка, что он не может больше расти в некоторую сторону.
  • Началась преграда. Необходимо рассмотреть все отрезки, которые пересекаются с преградой. Некоторые из них нужно полностью удалить, некоторые обрезать, а некоторые разделить на две части. Также необходимо создать события, которые произойдут, когда соседние отрезки разрастутся настолько, что пересекут текущую преграду.
  • Преграда закончилась. Необходимо найти два соседних отрезка и поставить им пометку о том, что они могут расти в направлении прямоугольника. Также необходимо добавить событие, которое должно произойти между соседями. Например, если два соседа являются отрезками, то они могут в некоторый момент объединиться. Если один из них отрезок, а другой — преграда, то они могут пересечься. В остальных случаях ничего добавлять не надо.

Также заметим, что все отрезки необходимо хранить лениво. То есть изменять их размер, а также пересчитывать общее количество достижимых клеток, необходимо только тогда, когда происходит некоторое событие, которое затрагивает данный отрезок.

Время работы решения — O(n log (n)), где n — общее число преград.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +48
  • Проголосовать: не нравится

Автор Aksenov239, 11 лет назад, По-русски

Задача A. Командная олимпиада.

Идея: Виталий Аксенов.
Реализация: Андрей Комаров.
Разбор: Виталий Аксенов.

Самое логичное в задаче сразу перебрать количество задач первого типа, которые решил Вася. Пусть он решил vn задач первого типа, тогда очевидно, что максимальное количество задач второго типа vm, которое мог решить Вася за олимпиаду, равно (n-vn·p)/q. Итого, у нас осталось n-vn задач первого типа и m — vm задач второго. Нужно не забыть сравнить эти количество с нулём.

Посчитаем, какое максимальное число задач первого типа и второго типа можно решить за олимпиаду. Первого типа получается maxn=t/p, а второго типа — maxm=t/q. Благодаря подсчитанным значениям, несложно уже посчитать ответ: 1 + (n — vn + maxn — 1) / maxn + (m — vm + maxm — 1) / maxm.

Задача B. Три ладьи.

Идея: Георгий Корнеев.
Реализация: Демид Кучеренко.
Разбор: Виталий Аксенов.

Заметим, что расставлять ладьи можно только в квадрате 3 на 3. Любая другая расстановка сводится к этой переносом ладей. Существует два различных решения. Первое из которых просто перебирает все возможные расстановки трёх ладей в квадрате 3 на 3.

Либо можно рассмотреть все различные варианты взаимных расстановок 3 ладей:

  • (1, 1), (2, 2), (3, 3). Бьют 3 · n + 3 · m — 12 клеток.
  • (1, 1), (1, 2), (2, 3). Бьют 2 · m + 3 · n — 9 клеток.
  • (1, 1), (2, 1), (3, 2). Бьют 3 · m + 2 · n — 9 клеток.
  • (1, 1), (1, 2), (2, 1). Бьют 2 · n + 2 · m — 7 клеток.
  • (1, 1), (1, 2), (1, 3). Бьют m + 3 · n — 6 клеток.
  • (1, 1), (2, 1), (3, 1). Бьют n + 3 · m- 6 клеток.
Во всех других случаях нужно выводить «IMPOSSIBLE».

Задача C. Король и королева.

Идея: Виталий Демьянюк.
Реализация: Павел Кротков.
Разбор: Павел Кротков.

Заметим, что максимальное количество регионов на доске равно восьми. Научимся находить размер одного из них, а размеры всех остальных найдем, отразив и повернув доску несколько раз.

Пусть королева стоит в клетке с координатами (x, y), строки и столбцы нумеруются с нуля, и мы хотим научиться находить размер региона, расположенного левее вертикали, на которой расположен ферзь, и выше диагонального луча, выпущенного налево вверх из клетки, в которой стоит королева. Заметим, что в случае, если этот луч упирается в верхний край доски (xy) , то ответом будет являться сумма всех чисел от одного до x — 1. В противном же случае из этой величины необходимо вычесть количество клеток, которые были бы биты королевой, если бы не край доски. Количество таких клеток равно сумме всех чисел от одного до x-y-1.

Задача D. Дерево.

Идея: Анна Малова.
Реализация: Артём Васильев.
Разбор: Виталий Аксёнов.

Дано дерево, которое нужно получить из одной вершины двумя операциями: отрезать ребро и добавить 2 вершины к листу. Чтобы решить данную задачу первым делом проверим, есть ли вершина степени не менее 4. Если она есть, то дерево получить нельзя.

В любом другом случае дерево построить можно. Для этого посчитаем количество вершин v2 степени 2 и v3 степени 3. Если есть вершина степени 2, то при выборе её начальной мы построим дерево за (v2 — 1)·2+(v3 + 1), иначе число действий равно (v2 + 1)·2+v3. Это верно потому что для получения внутренней вершину степени 3, нужно применить одну операцию второго типа, а для получения внутренней вершины степени 2 нужно применить 2 операции.

Задача E. Налог на проезд.

Идея: Борис Минаев.
Реализация: Борис Минаев.
Разбор: Борис Минаев.

Заметим, что полученный от налогов доход всегда четен, так как для любой пары городов существует два жителя, которые собираются проехать по пути, который их соединяет.

Посчитаем для каждой дороги количество путей, которые через нее проходят. Для этого необходимо перемножить количество вершин в двух компонентах, на которые разбивается дерево при удалении ребра. Чтобы посчитать общий доход, необходимо просуммировать по всем дорогам произведение стоимости проезда по этой дороге на величину, которую мы только что посчитали.

Посчитаем доход, который получит президент, если на всех дорогах цены на проезд будут минимально возможными. Вычтем эту сумму из необходимой. Если мы получили отрицательное число, то не существует ни одного удовлетворяющего набора налогов. Заметим, что если мы получили неотрицательное число, то общее количество дорог не превышает 600.

Теперь нам необходимо решить некоторую модификацию задачи о рюкзаке. Она решается методом динамического программирования. Будем рассматривать все дороги по очереди. Также будем поддерживать количество способов собрать некоторую сумму денег, используя только некоторый префикс дорог. Рассмотрим более подробно, как обрабатывать очередную дорогу. Пусть увеличение налога на проезд по этой дороге добавляет c денежных единиц в общую прибыль, а цена за проезд по дороге может находится в пределах от 0 до max. Как узнать, сколько существует способов получить суммарный доход ровно m? На самом деле это количество совпадает с количеством способов получить суммарную прибыль mc за исключением двух слагаемых. Эти слагаемые соответствует тому, что мы можем назначить стоимость проезда равную 0, но не можем max + 1. То есть каждое значение динамического программирования можно посчитать с помощью трех уже посчитанных значений. Таким образом, очередную дорогу можно обработать за O(MAX), где MAX — прибыль, которую хочет получить президент.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

Автор Aksenov239, 11 лет назад, По-русски

Задача А. Игра.

Идея: Андрей Комаров.
Реализация: Малова Анна.
Разбор: Малова Анна.

В данной задаче требовалось проверить, является ли игровое поле хорошим. Хорошим полем называлось поле, в котором есть свободная клетка или две соседние клетки, в которых стоят одинаковые числа.

Решением задачи является проверка всех клеток игрового поля и пар соседних клеток игрового поля, удолетворяют ли они указанным выше условиям. Итоговая сложность: O(n2).

Задача B. Таймер.

Идея: Виталик Аксёнов.
Реализация: Артем Васильев.
Разбор: Артем Васильев.

В задаче нужно найти максимальное возможное число, которое может получиться на таймере после t секунд, если разрешено не более k раз заменить число на таймере на наименьшее число, не меньшее x и делящееся на y.

В заданных ограничениях всегда возможно получить число, которое делится на y. Рассмотрим первый момент, когда такое число появилось на таймере. Можно показать, что это число будет наименьшим среди чисел, не меньших x и делящихся на y. Обозначим его за z.

Существует не более двух различных оптимальных способов получить z на таймере. Первый из способов это использовать уязвимость до первого тика таймера. В таком случае мы тратим одно использование уязвимости и ноль секунд. Второй способ — не тратить использование уязвимости и подождать необходимое количество секунд. Этот способ возможен только тогда, когда z-xt и затрачивает z-x секунд и ноль использований уязвимости. Обозначим время после получения z за to, а оставшееся количество использований за ko.

После того, как на таймере появилось z, действия Пети становятся однозначными. Нам выгодно использовать как можно больше уязвимостей, потому что они прибавляют дополнительно y-1 секунд. Отсюда ответ равен z + min(to, ko) · (y-1) + to.

Осталось проверить оба способа получить число z, вычислить ответ для получившихся to и ko и выбрать максимальный из них. Время работы решения — O(1) на один тестовый пример.

Задача C. Обратная задача о наибольшей возрастающей подпоследовательности.

Идея: Андрей Станкевич, Николай Ведерников.
Реализация: Николай Ведерников.
Разбор: Николай Ведерников.

В задаче требовалось по массиву для решения задачи динамического программирования о наибольшей возрастающей подпоследовательности восстановить исходную последовательность.

Данную задачу можно решить конструктивно. Например так d[i] = a[i] · ni + 1, где n — длина последовательности. Докажем, что это последовательность подходит.

i < j для которых d[i] < d[j] будет выполнено: (d[j] — d[i]) · nn, а (ji) < na[i] < a[j]. Аналогично в другую сторону.

i < j для которых d[i] = d[j] будет выполнено: a[i] > a[j].

Кроме того, существует решение, использующее алгоритм топологической сортировки.

Задача D. Трехцветные шахматы.

Идея: Виталий Демьянюк.
Реализация: Виталий Демьянюк.
Разбор: Виталий Демьянюк.

В задаче требовалось подсчитать количество способов покрасить каждую не покрашеную клетку доски n × m в три цвета так, чтобы никакие две соседние клетки не были покрашены в одинаковый цвет.

Данная задача является задачей динамического программирования по изломанному профилю.

Занумеруем все цвета. Каждому состоянию соответствует четверка чисел (x, y, c, mask), где (x,y) – координаты клетки в которой начинается излом профиля. Рассмотрим все клетки профиля в порядке обхода сверху вниз. Тогда c – цвет первой клетки профиля. Рассмотрим i-тую клетку профиля и множество цветов в которые она не покрашена. Это множество состоит из двух цветов. Тогда i-тый бит mask равен 0, если цвет i+1 клетки профиля равен минимуму этого множества, 1 – если максимуму.

В каждом состоянии будем хранить количество способов покрасить соответствующую часть доски. Пересчет значений такой же как и в любой другой задаче динамического программирования по изломанному профилю. Для получения ответа переберем все c и mask и просуммируем значение в состояниях (n, m, c, mask).

Время работы — O(nm2n).

Задача Е. Как проложить сеть.

Идея: Борис Минаев.
Реализация: Борис Минаев.
Разбор: Борис Минаев.

В задаче требовалось подсоединить все компьютеры к коммутаторам, которые расположены по кругу, затратив при этом наименьшее количество кабеля. Эту задачу можно решать с помощью алгоритма поиска максимального потока минимальной стоимости. Однако мы опишем решение, которое использует метод динамического программирования, а также имеет лучшее время работы.

Для начала рассмотрим более легкую задачу. Пусть компьютеры и коммутаторы расположены на прямой. Назовем балансом разность между количеством компьютеров, которые мы рассмотрели, и количеством подсоединений к коммутаторам, которые использовали. Для каждого баланса от -n до n будем хранить наименьшую стоимость его достижения. Стоимость достижения баланса нужно определить таким образом, чтобы при балансе 0 его стоимость совпадала со стоимостью прокладки всей сети. Например, это можно сделать следующим образом: eсли после добавления очередного устройства модуль баланса увеличился, то из его стоимости вычитается расстояния до устройства, иначе добавляется. Теперь воспользуемся методом динамического программирования. Будем рассматривать устройства слева направо. Если текущее устройство — компьютер, то баланс нужно обязательно увеличить на один и соответствующим образом изменить его стоимость. Если же мы рассмотриваем коммутатор, то необходимо перебрать, сколько компьютеров будет к нему подключено, и аккуратно пересчитать стоимость баланса (возможно, первые несколько подключений будут его увеличивать, а следующие — уменьшать). Такое решение работает за O(n2·(n+m)).

Рассмотрим способ, который позволяет уменьшить время работы алгоритма до O(n·(n+m)). Самое долгоработающее место алгоритма — обновление значений динамического программирования при обработке коммутатора. Будем находить стоимость получения балансов от меньших к большим. При этом будем поддержить очередь, в которой хранятся стоимости получения нужного баланса из различных предыдущих состояний балансов. При переходе к новому значению баланса нужно, возможно, удалить из очереди первый элемент (если к текущемему коммутатору нельзя поключить нужное количество компьютеров), добавить возможность получить текущий баланс не использовав коммутатор совсем, а также изменить все текущие стоимости, которые есть в очереди — для этого нужно прибавить (или отнять) расстояние до коммутатора. В очереди всегда должна хранится возрастающая последовательность стоимостей. Тогда ответ для текущего баланса всегда будет находится на первом месте очереди.

Теперь вернемся к задаче на круге. Разрежем круг и зафиксируем количество проводов, которые проходят через разрез. Можно легко показать, что если существует оптимальный ответ, в котором ровно столько проводов проходят через разрез, то существует оптимальный ответ, в котором эти провода подключены к первым устройствам соответствующего типа. Таким образом мы получили решение на круге за O(n2·(n+m)).

Полный текст и комментарии »

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

Автор Aksenov239, 11 лет назад, По-русски

417A - Отбор. Автор и реализация Aksenov239.

Сначала нужно заметить, что если k больше либо равно, чем n·m, то ответ — 0. Нам осталось набрать n·m - k человек. Есть три способа их набрать:

  • Взять раунды только первого типа: .
  • Взять чуть раундов второго типа до числа, делящегося на n: .
  • Взять только раунды второго типа: d(n·m - k).

Также в данной задаче можно было написать переборное решение — сколько мы берём раундов первого типа, и сколько раундов второго.

Код: 6396283

417B - Сбой. Автор и реализация Aksenov239.

Заведём массив a на 105 элементов, изначально заполненный  - 1, и в ячейке с номером k будем хранить максимальный номер посылки k-го участника, который сейчас есть. Будем обрабатывать посылки последовательно. Пусть обрабатывается посылка x k. Если a[k] < x - 1, то очевидно, что ответ NO, иначе обновляем массив — a[k] = max(a[k], x).

Код: 6396297

418A - Футбол. Автор и реализация Aksenov239.

Представим турнир себе как граф. Из каждой вершины ровно k выходящих рёбер. Тогда всего nk рёбер. В полном графе максимум рёбер, поэтому если n < 2k + 1, тогда ответ  - 1. Иначе, соединим i-ую вершину с i + 1, ..., i + k, зациклим если нужно.

Код: 6396331

418B - Хитрый Гена. Автор и реализация Aksenov239.

Давайте отсортируем друзей по возрастанию требуемого количества мониторов. Будем считать динамику на масках — какое минимальное число денег нужно заплатить, чтобы решить такие-то задачи, если мы взяли первых i друзей. Тогда ответ надо сравнить с ответом для i первых друзей плюс количество мониторов, которое требует i-ый друг. Не трудно заметить, что если брать друзей последовательно, то пересчитывать динамику можно как рюкзак. Время работы данного алгоритма O(nlog(n) + n2m).

Код pashka: 6396347

418C - Квадратная таблица. Автор и реализация Aksenov239.

Давайте для любого n построим массив длины n, что сумма квадратов чисел на нём является квадратом:

  • Если n = 1, то берём [1].
  • Если n = 2, то берём [3, 4].
  • Если n чётно, то берём .
  • Если n нечётно, то берём .

Нам дано 2 числа n и m. Пусть массив a соответствует числу n, а b соответствует числу m.

Тогда итоговый массив c построим следующим способом — cij = ai·bj.

Код: 6396358

418D - Большие проблемы организаторов. Автор chavit, реализация Aksenov239.

В данной задаче есть два решения.

Первое. Подвесим за какую-нибудь вершину. Предподсчитаем для каждой, 3 самые удалённые вершины в её поддереве, а также для каждой вершины её глубину. Также предподсчитаем массивы для двоичного подъёма. Для каждой вершины i и степени двойки 2j предподсчитаем следующие массивы — p[i][j], up[i][j] и down[i][j]. p[i][j] — это предок вершины i на расстоянии 2j. В up[i][j] будет храниться наидлиннейший путь из i, до вершин, которые находятся в поддереве вершин, которые находятся на пути между i и p[i][j]. down[i][j] отличается от up[i][j], что хранит путь из вершины p[i][j].

Теперь осталось дело за малым. Нам приходит запрос u v, мы ищем его наименьшего общего предка — w. Осталось найти вершину hu, которая будет находиться на середине это пути. Обрезать дерево по этой вершине, и посчитать длиннейшее расстояние от вершины u в её дереве и длиннейшее расстояние от вершины v в её дереве. Представляя на дереве это, если мы не будем удалять, то можно воспользовавшись нашими предподсчитанными массивами аккуратно пересчитать значение длиннейшего пути.

Решение за O(nlog(n)).

Код: 6396376

Второе. Вкратце. Найдём диаметр этого дерева. Предподсчитаем там ответ на префиксе для каждой вершины. Тогда при ответе на запрос — мы находим, когда путь вливается диаметр. На это отрезке находим среднюю вершину, а далее отвечаем на запрос на префиксе или суффиксе.

Код cerealguy: 6396390

418E - Хитрый пароль. Авторы enot110, Aksenov239, реализация Aksenov239

Ключевая теоретическая идея данной задачи заключается в том, что 2 строка совпадает с 4, 3 с 5 и т. д. Поэтому нам нужно уметь менять что-то только на первых трёх строках.

Теперь дело остаётся за практической частью. В первую очередь сожмём все значения, чтобы они не превосходили 105. Разобьём массив на отрезки длиной LEN. На каждом отрезке будем считать следующее — для каждого значения будем хранить сколько раз он встречался на префиксе cnt, а так же дерево Фенвика, в котором в ячейке f[k] будет храниться количество чисел на данном префиксе, встречающихся ровно k раз. Несложно заметить, что в первом массиве хранится ответ на запросы ко второй строке, а чтобы получить ответ для третьей строки, нужно посчитать f[cnt[k]... 105]. Понятно так же, как делать пересчёт данной динамики.

Итого, получаем время на запрос за . Если мы возьмём , то время ответа на запрос составит .

Код: 6396412

Полный текст и комментарии »

Разбор задач RCC 2014 Warmup (Div. 2)
Разбор задач RCC 2014 Warmup (Div. 1)
  • Проголосовать: нравится
  • +37
  • Проголосовать: не нравится

Автор Aksenov239, 12 лет назад, По-русски

Здравствуйте, друзья.

В ближайшее воскресенье (16 июня) в 14-00 по Москве состоится отборочный раунд, который позволит 50 людям из 600 пройти на онсайт раунд, который пройдёт в сентябре.

Хочется обратить внимание, этот раунд будет длиться уже на один час больше, то есть ровно 3.

Всем удачи!

До свидания!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +118
  • Проголосовать: не нравится

Автор Aksenov239, 12 лет назад, По-русски

Здравствуйте, друзья.

Приглашаем всех тех, кто не прошёл/забыл/проспал/что-то иное, поучаствовать в третьем и последнем в это году квалификационном раунде за право участвовать в отборочном раунде. Собственно, состоится он в это воскресенье (2 июня) в 14:00 по Москве и будет длиться стандартные 2 часа.

Всем удачи!

Пока!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +73
  • Проголосовать: не нравится

Автор Aksenov239, 12 лет назад, По-русски

Здравствуйте!

Кто ещё не участвовал или не прошёл с QR 1 приглашаются на QR 2, который состоится завтра (11 мая, в 12:00 по Московскому времени). Будет весело. Присоединяйтесь.

Предоставляю ссылку — http://russiancodecup.ru. И будьте точно уверены, что вы зарегистрированы... У Вас есть шанс получить футболочку. Уииииии.

До свидания!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

Автор Aksenov239, 12 лет назад, По-русски

Здравствуйте.

Уже пришло время анонсировать соревнование Russian Code Cup 2013. Собственно, на данный момент уже известно расписание раундов (дублирование с официального сайта):
Первый квалификационный раунд 2 часа 13 апреля, 19:00
Второй квалификационный раунд 2 часа 11 мая, 12:00
Третий квалификационный раунд 2 часа 2 июня, 14:00
Отборочный раунд 3 часа 16 июня, 14:00
Финальный раунд 3 часа 23 сентября, 11:00

Дальнейшая информация будет выложена позднее. Но несмотря на это, жюри уже начало подготовку. :-)!

P.S.: Регистрация уже объявлена открытой.

P.S.S.: По поводу технических проблем с регистрацией обращайтесь к службе-support.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +73
  • Проголосовать: не нравится

Автор Aksenov239, 12 лет назад, По-русски

Начало.

Всё началось с того, что где-то осенью этого года я окончательно забил заниматься олимпиадным программированием, но не закончил придумывать задачи для данных мероприятий. (Краткость, сестра...)

Четвертьфинал.

Первое серьёзное мероприятие, в котором я принял участие с сентября года в роли жюри, был четвертьфинал Северо-Западного региона. Я радостно прибежал на собрание жюри, самое удивительное для меня было, что моё присутствие там почти никто не удивило. Там я предложил несколько неплохих задач, а также ту, которую я придумал на месте, как это ни удивительно — взяли ту, которую я только что придумал.

Собрание жюри полуфинала.

Итак, прошёл четвертьфинал, на котором я налажал с некоторыми тестами (я упустил некоторый случай, а теста у меня против этого не было), за что на меня частично взъелось ИТМО 1. Я их не до конца понимаю — они же выиграли четвертьфинал... Немного обиженный и пристыженный я ждал момента исправиться. И вот он наступил! Мне прислали долгожданное письмо, в котором меня приглашали на встречу жюри полуфинала. Взяв задачи, которые были придуманы ещё к четвертьфиналу, а также придумав ещё одну задачу за день, я пошёл на собрание.

Долго-долго мы тужились, и в конце концов надумали проблемсет. К сожалению, у меня опять не взяли более-менее интересные задачи, пришлось довольствоваться тем, что взяли какую-нибудь задачу. Поэтому эти задачи, видимо, будут предложены на некоторый раунд "codeforces". Она же и была будущей задачей H. Сложнее жюри удавалось придумать названия к задачам, чтобы покрыть буквы латинского алфавита от A до K, к некоторому удовольствию, название моей задачи можно было варьировать, главное, чтобы оно было вида "*drome".

И вот пришёл облом.

Спустя все прошедшие четвертьфиналы, выяснилось, что некоторые задачи уже повторяются — что не есть хорошо. Поэтому собрали срочное заседание жюри, на котором достаточно быстро сообразили ещё задач. Теперь всё оставалось за малым. Надо было подготовить задачу.

ГиперДром.

Задача оказалась не столь простой, сколь я ожидал. Не в плане решения, а в плане подготовки. Я достаточно шустро её подготовил, но потом пошло-поехало. Сначала, мне предложили немного изменить идею задачи. Ну, ничего, подумал я, зато задача стала более естественной. Окей. Научился отличать TreeSet от HashSet. Но не тут-то было...

ГиперДром и бурундук.

Пришёл Burunduk1 и меня расстроил своими быстрыми решениями, что проходил не только map, но и бинарный поиск. (Правда, по понятным причинам.)

Далее на меня снизошло озарение — плохо, если проходит map на C++, так как это асимптотически не является верным, но если map не должен проходить, то и hashmap не должен проходить. Поэтому в срочном порядке придумывалось решение, которое бы работало за приблизительно такую же асимптотику, что и решение с hashmap. С этим всё-таки справились. Далее я долго и упорно подгонял ограничения, чтобы проходило только это решение. Я справился — удалось завалить даже решения Сергея, что не могло не радовать.

Облом-2.

После вот такого долбания с задачей мне сообщили, что это очень хорошо — неасимтотическая оптимизация. Но в таком виде не хотелось давать, так как было неизвестно, какие инвокеры в регионах, а, значит, нельзя быть уверенным, что там процессоры настолько хорошо выполняют последовательные пробеги по массиву. Поэтому пришлось опустить ограничения, чтобы проходило почти всё что угодно. Почти...

Воскресенье. 2.12.2012 г. 10:10-15-10.

Уже очень хотелось спать. Я не так часто встаю так рано. Но, переборов это желание, я подключился к тесной компании, которая находилась в комнате жюри. И сделал не зря — меня почти сразу осчастливили талончиком на питание в столовой. :-)!

Petr писал свой блог. Меня удивлял следующий факт, когда в блоге появлялась информация об ошибке какой-то команды, их accepted не заставлял себя ждать... Также выяснилось, что @niyaznigmatul постит в свой твиттер, некоторые люди возмутились вплоть до того, чтобы дисквалифицировать команду, но как и ожидалось — это было провокация оппозиции.

Пока всё это происходило elizarov писал разбор задач. Я в какой-то момент присоединился... Пытались придумать совсем простое решение к задаче G (Great Deceiver), но справились написать правильное решение только с какого-то раза...

Шоколадка и еда.

elizarov и Petr поспорили друг с другом на две шоколадки — сдаст ли кто-нибудь 11 до заморозки и сдаст ли кто-нибудь всё. Судьба первой шоколадки решилась до обеда. ИТМО 1, можно сказать, развело Романа на шоколадку, притом очень неожиданно — они сдали 11 задачу за 2 минуты до заморозки. После обеда выяснилась судьба второй шоколадки. Счёт: 1-1. Никто не покупал шоколадку.

Закрытие.

И вот настало время закрытия. Мы, жюри, были хранителями тайны. ;-)! Эта фраза, а также ещё множество остальных, у бывалого жюри вызывало истерику — они уже раз в 20-й слышат эти речи.

Я был удивлён, что меня вызвали на сцену. Конечно, было смешно, что я, получается, отдувался за часть жюри, которая находилась не в Питере, так как до следующего присутствующего, произнесли фамилий 5.

Ну, а про песенку-"чо-чо" Вы и сами слышали.

Пьянка после закрытия.

Естественно! Как же могло обойтись без пьянки — ведь команда нашего университета опять выиграла. Вот cerealguy и niyaznigmatul осушили на двоих кубок полный шампанского. После этого залпа, ребят явно повезло...

Пока их везло, я попытался безуспешно поднять Alex_KPR, в то время, как он меня поднял достаточно много раз. А также нашёл у pashka на столе радиоуправляемый "Range Rover" (Радиоуправляемые машинки являлись подарком серьёзному техническому комитету.) и пооббивал ей стенки на нашей кафедре. На удивление — она не развалилась. :-)!

Заключение.

В-общем, на этом для меня закончился NEERC-2012. Мне понравилось. Уж лучше, чем в прошлом году, когда я был волонтёром.

Спасибо всем, кто это дочитал до конца.

Удачи. Возможно, ещё увидимся. Командам желаю удачи на финале.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +90
  • Проголосовать: не нравится

Автор Aksenov239, 12 лет назад, По-русски

Hello!

This Sunday (the 2nd of December) NEERC 2012 will take place at 10am (UTC +4). (It is really north-eastern, we are fully in snow... Official site of the competition.) This competition is selection to the World Finals, that will take place in Russia, Saint-Petersburg, at the beginning of July.

I think this will be very interesting semifinal, as always.

And for the competitors — good luck and have fun!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

Автор Aksenov239, 12 лет назад, По-русски

Здравствуйте!

В это воскресенье (4 ноября) состоится юбилейный командный чемпионат по программированию среди школьников. Он же является и отборочным на ВКОШП. По этим задач также будет проходить онлайн-отбор на ВКОШП и ещё несколько отборов в других регионах.

Контест обещает быть интересным. Вероятно, кто-нибудь после турнира выложит его в Codeforces.Тренировки, чтобы Вы тоже смогли потренироваться на этих задачах.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится