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

Всем привет!

Мы рады представить окончательную версию правил Russian Code Cup 2016! Важнейшее нововведение этого года — чемпионат становится международным, теперь задачи предлагаются на русском и английском языках. Все могут принять участие, для этого необходимо зарегистрироваться на сайте http://russiancodecup.ru, участникам прошлых чемпионатов необходимо подтвердить участие в этом году в личном кабинете.

В этом году участники вновь сразятся за звание лучшего программиста и призовой фонд в размере 750 000 рублей. Мы изменили структуру призового фонда, чтобы дать еще больше денежных призов, теперь участники, занявшие места с 11 по 25 также получат призы. Победитель чемпионата получит 150 тыс. рублей, обладатели второго и третьего места — 100 тыс. и 65 тыс. рублей, соответственно. Программистам, занявшим с четвертого по десятое места, достанется по 30 тыс. рублей, с 11 по 25 место – 15 тыс. рублей. 200 лучших участников отборочного раунда получат футболки с символикой чемпионата.

Основная программа чемпионата состоит из трех этапов: квалификационных раундов (8 мая, 29 мая и 5 июня), отборочного тура (19 июня) и финала (18 сентября). На каждом этапе участники олимпиады должны решить от четырех до восьми разноплановых задач. Программисты, которым не повезло в первом квалификационном туре, могут попытать удачу в следующих. В отборочный тур пройдут по 200 лучших участников из каждого квалификационного раунда, а в финале будут сражаться 50 лучших программистов.

Приглашаем всех на первый квалификационный раунд в воскресенье 8 мая, в 19-00 по московскому времени и желаем удачи всем участникам!

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

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится -25 Проголосовать: не нравится

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

В качестве примера можно вспомнить турнир от Wunder Fund зимой. Ребята придумали интересную идею — давать футболки случайно с 50 по 500 место, многие впервые получили какие то призы (пусть, символические) на Codeforces, а шанс имели как минимум все синие. Соревнование за призы компании получилось для нескольких тысяч человек. Очень позитивный пример.

Просьба не воспринимать сообщение как совет компаниям, как надо делать и как не надо делать :) Просто способ, как сделать ваше соревнование чуть менее справедливым, но чуть более массовым.

Всем удачи на предстоящем контесте!

»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

What if I have no middle name?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can fill in your handle.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The question is rather: do you have to fill in your handle? And the answer to it is: no, any visible string, even an almost invisible one like ".", is enough.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +147 Проголосовать: не нравится

    Fill in the name of your father with suffix "ovich".

    Example: John Smith, the son of Adam Smith -> John Adamovich Smith.

»
9 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

mail.ru еще даже не прислали мне футболку с прошлого контеста (Russian AI Cup).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    буквально вчера получил ее, до Бреста уже успела дойти

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

До сих пор не получил футболку RCC с прошлого года.

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Это вы конечно правильно сделали, что не стали напоминать о том, что через час будет первый раунд.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Рассылка за полтора часа была отправлена.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      В которой вы рассказали о начале 1-ого раунда разогревочного раунда

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Да, вот только что сообщение пришло. Но было бы лучше анонс на главной CF. Не знаю как другие, но я почту редко проверяю.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      У меня на один e-mail пришло за 65 минут, на другой за 55. Думаю, у кого-то и после старта может прийти.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

На какой платформе будет контест?

»
9 лет назад, # |
  Проголосовать: нравится +124 Проголосовать: не нравится

Wow that thing is SLOW...

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D?

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    Precompute the ans for each value of k<=5*10^5 in O(maxn*log(maxn)), where maxn = 500000.

    For query of type 1: find all factors of t[v] and add 1 to those.Update value of t[v].

    For query of type 2: find all factors of t[v]-1 sub 1 from those.Update value of t[v].

    For query of type 3: Output the answer in O(1).

    Overall complexity. O(m*(sqrt(max(t[i]))).I had to use fast I/O and other optimizations to get this AC.

»
9 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

Ужааасно дооооолгое тестирование

»
9 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

What's the intended complexity in D? If it's O((N + Q) * sqrt(max_number)) the constraints look way too high.

»
9 лет назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

Ждать по 10 минут вердикта очень печально. Хотелось бы какую-то более быструю проверку.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится

    Ага, я ждал 10 минут А и получил compilation error =\

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    Я под конец послал 5 решений по D с разными константами.

    До сих пор не могу увидеть результата.

»
9 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Весь контест не мог пробить C и D на джаве по времени. Это какой-то адец. И 502 в конце раунда это просто замечательно

»
9 лет назад, # |
  Проголосовать: нравится +76 Проголосовать: не нравится

Choose your favourite C++ compiler:
- slow
- very slow
- as slow as RCC testing system

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    Compiler is ok, except stdio. I saw such trouble on ROI and NEERC, and it's common trouble for all new enough mingw builds.

    Fix is one of following:
    1. use -D__MINGW_USE_ANSI_STDIO=0 in command line (i'm not sure if it's enough in code)
    2. use -std=gnu++11, instead of -std=c++11.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

как решать C быстрее, чем за ?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    можно предрасчитать gcd-шки среди тех элементов a[i] у которых GCD(a[i], a[0])=K (один из делителей) и потом будет numdivisors^2 с константной gcd-шной. Но даже это на джаве не зашло.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      я в итоге оставил различные числа, делил все на общий gcd и брал a[rand]

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я сделал бин поиск по делителям, но че-т не заходит, хотя я все еще жду вердикты на свои посылки.

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

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

      Это неверно:

      1

      3

      6 7 9

      Для делителя 2 получаем gcd(7,9) = 1 Для делителя 3 получаем gcd(7) = 7

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Я от нечего делать написал рандом:

    Рандомно выбираем число. Находим для него число, НОД с которым минимален. Предполагаем, что эти два числа будут в разных множествах. Жадно раскладываем остальные числа между множествами. Повторяем несколько раз (мне хватило 20).

    20 * O( n log( max A ) ).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      там же тестов 1000, 10^7.5 это же вообще мало

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Хм. Я думал что 10000. Во всяком случае, ускорение нахождения всех делителей позволило мне получить AC после TL, без каких-либо других отсечений и оптимизаций.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    У меня зашло после замены a_0 на min(a) (и добавления отсечения по ответу)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как решалась С? У меня решение O(n * f(ai)) не проходило по ТЛ, где f(n) — количество делителей числа n.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Если добавить перебор делителей с самого большого, отсечение если мы уже не улучшим ответ и случайный выбор начального числа — проходит

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А какой компилятор был выбран? Просто или у них компы медленные, или дело в компиляторе. Я вот отправил на VS 2013 и получил TL на 6 тесте, хотя у меня на компе в VS 2010 он работает 0.9 с.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      под gcc я тоже получал TL6 (локально под слангом, что мое, что авторское работают 0.7)

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

The website is unresponsive. Luckily after the contest!

»
9 лет назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится

Несколько замечаний после раунда:

  1. Поиск — он ужасен. Он учитывает регистр, он требует полного слова с учётом регистра всех букв, иначе не находит. Я почему-то там Sergej. Я себя там с трудом нашел, когда хотел узнать на каком я месте, потому что нигде это не написано (или я не нашел?). Друзей даже искать не стал, звёзды явно были не в фазе Юпитера

  2. Жууууутко доооолго тестируеееееет. 3 посылки ждал 7-8 минут, каждую.

  3. Английский перевод так себе, задачу с поездом я понял только переключившись на русский интерфейс. И то, переключения не нашел, слава Богу замена языка в ссылке сработала

  4. Система так и не научилась запоминать мой компилятор

  5. Переодически появляется ошибка “Неверно заполнена форма” — почему, я так и не понял. Обновил страницу, указал тоже самое — приняли

Вы правда 6-ой год уже проводите это соревнование? Такой вопрос — почему на своей платформе, а не на Codeforces? Здесь проблем 1-5 уже решены

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -28 Проголосовать: не нравится

    В замечания еще можно кинуть качество задач. Первые две задачи — простые, на реализацию, с разбором частных случаев. А учитывая то, как проходило тестирование, такие задачи вообще давать нельзя.

    Ну и конечно же стоит упомянуть про несколько тестов в одном тесте. Вам лень сделать несколько файлов? Или хотя бы проверить размер ввода (у меня B упала из-за TL).

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      А теперь представим сколько бы работало тестирование, если бы мультитесты были в отдельных файлах

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

      FYI: нынче никто не делает мультитест "от лени". Обычно его делают, чтобы протестировать решение не на ~100 тестах, что за разумное время позволяют тестирующие системы, а на стольки, сколько душа пожелает.

      И да, это полезное умение — чистить глобальные массивы.

»
9 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Magical solution for C. Divide all numbers by their common GCD. Now it's easy to see that the answer is no less than 1 and we should check if it's at least 2, and if yes, find it. Let's calculate the following "DP": iterate over numbers, when passing the i-th number keep set of pairs (a, b) where a and b is the pair of gcd values we can achieve by splitting first i numbers into two sets. When passing the number x, we take each pair (a, b) and form two new pairs (gcd(a, x), b) and (a, gcd(b, x)).

It is now working in , but we make a super-observation that we are not interested in pairs where one of the numbers is equal to 1 since we already know that the answer is not less than 1, they provide no information for us. Do not add such pairs and it gets AC. I have no single idea WTH it works. Maybe because I sorted all numbers in increasing order and uniqued them?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Why does it work for in O(n*n*logn)? It looks like there are O(n*logn) pairs (a,b) in the set. How did you estimate this?

»
9 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

Why are there less than 50 participants on some of the standings pages? 50 on page 1, 49 on page 2, 50 on page 3, 48 on page 4, etc.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

Две просьбы-предложения организаторам:

1) Сделать задачи в блоке "Your results" кликабельными.

2) Запретить посылать одинаковый код дважды. (Сайт тупил, несколько раз нажал на кнопку "отправить" -> получил лишний штраф).

»
9 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

До сих пор стоит баг, который сбивал меня с толку весь контест (на самом деле у меня АС по обеим задачам).

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

What is the correct date and time of the Final Round?

It's written "September 18" here and "September 11" on the website.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    The date on the site is corrected. The final round will take place on September 18.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

      Will there be an onsite round in Moscow for those who wish to come?

      EDIT. Let me phrase the question differently: could you organize an onsite in Moscow like last year? I've already came to Moscow for this :)