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

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

Всем привет!

В эту субботу (21 ноября) на сайте интернет-олимпиад в 12:00 пройдет четвертая командная интернет-олимпиада для школьников.

Главными героями задач на этот раз будут персонажи известной антиутопии Сьюзен Коллинз, экранизированной Гэри Россом <<Голодные игры>>.

Продолжительность этой олимпиады будет составлять 5 часов в усложненной номинации и 3 часа в базовой. Подробнее о номинациях и правилах можно прочитать здесь.

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

Условия появятся на сайте в момент начала олимпиады. Сдавать задачи можно в PCMS2 Web Client (русская версия).

Задачи для вас придумали и подготовили Илья Збань (izban), Николай Будин (budalnik), Дмитрий Филиппов (DimaPhil), Илья Пересадин (pva701), Евгений Замятин (Odeen), Захар Войт (zakharvoit) и Григорий Шовкопляс (GShark)

По всем возникающим вопросам можно писать жюри интернет-олимпиад.

Удачи!

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

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

Из правил:

Если команда участвует в олимпиаде в базовой номинации и решает столько же задач, сколько команда-победитель, либо строго больше задач, чем команда, занявшая медианное место среди команд, решивших хотя бы одну задачу (место с номером k/2, где k — число команд, участвовавших в базовой номинации, решивших хотя бы одну задачу, округление производится вниз), то она переходит в усложненную номинацию.

А это нормально, что два контеста подряд (1 2, оба раза явно больше, чем k/2-я команда) мы решаем достаточно задач, чтобы нас перекинуло в усложненку, но этого не происходит?

Написал в ЛС на Codeforces DimaPhil — получил ответ: "Спасибо за репорт, изучим." Однако за эти 12 дней нас не перенесли. Написал на [email protected] — ответа нет вообще, как впрочем и изменений в списке команд.

У кого-нибудь еще была такая проблема?

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

    Перераспределение команд по номинациям происходит непосредственно перед самой интернет-олимпиадой. Отвечать на письма жюри также начинает ближе к следующей олимпиаде.

    Спасибо за напоминание о вашей проблеме, все исправим до начала олимпиады. По всем возникающим вопросам пишите на почту жюри интернкт-олимпиад.

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

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

    Надеюсь, в следующем сезоне с перераспределением команд по номинациям все будет в порядке :)

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

У всех заходит в систему? (Усложненный уровень)

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

Подскажите, пожалуйста, когда будут доступны материалы олимпиады? (Условия, тесты и пр.)

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

Ощущение было такое, что организаторы не успели придумать все задачи до начала контеста, поэтому и перенесли начало на час вперёд.

Задачи были интересные. Но очепятки, неточности в сэмплах... В общем, не надо так больше :)

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

    Рады, что задачи пришлись вам по вкусу. Спасибо за отзыв:)

    Больше не будем так)

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

Как решать C из усложненной?

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

    Дп по маскам. Для начала для каждой маски людей проверим следующий факт: если они и только они будут в одном дистрикте, не будет ли это противоречить какой-либо тройке чисел? Это можно сделать пометив все тройки чисел в булевом массиве, а затем для каждой маски перебрать все тройки единичек в этой маске и проверить, что каждая тройка непомечена.

    Теперь нужно разбить маску из всех участников на наименьшее количество непересекающихся непротиворечащих ничему масок. Это стандартное дп: перебираем маски в порядке возрастания, для каждой маски ms перебираем ее подмаску sub, проверяем, что sub ничему не противоречит никакой тройке (эту информацию мы посчитали ранее и сохранили в булевом массиве), и релаксируем dp[ms] = min(dp[ms], dp[ms ^ sub] + 1);

    Про перебор всех подмасок фиксированной маски можно подробнее прочитать тут

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

Вопрос по задаче А из базовой. Почему во втором примере кол-во неудобных стрел равно 1? Если отсортировать стрелы по не возрастанию длин, то получим 2 1 1 1, тогда не получится ли, что неудобно взять две стрелы длиной 1?

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

    итак у нас есть стрелы = 1 2 1 1

    1. Берём 2 стрелу ( удобно ) = 1 0 1 1
    2. Берём 1 стрелу ( удобно ) = 0 0 1 1
    3. Берём 3 или 4 ( не удобно ) = 0 0 1 0 или 0 0 0 1
    4. Берём последнюю ( удобно ) = 0 0 0 0

    Ответ 1

    З.ы. на месте взятых стрел как будто стрела длины 0 ( условие )

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

Задачи интересные, но условия очень плохие, пекло у нас неслабо. Особенно впечатилило описание интерактивки, где автор перестал различать "солдат Капитолия" и "солдат Китнисс" и решил назвать всех просто "солдатами".

До сих пор не пойму 2 момента в задаче B:

1) В каком случае возвращется 1? Поставленный assert показывает, что q(a, b) * -1 = q(b, a) — неверно. Что тогда означает единица вообще не понятно.

2) Мы таки ее сдали подсмотрев решение через тренерку, но в обоих сданных решениях зачем то перепосылается каждый запрос. Наше решение с контеста, получавшее WA12, прошло после того, как мы добавили ложный вызов. Пожалуйста, объясните зачем это нужно.

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

    Что-то не так с этой задачей на CF. Очевидное решение получившее Accepted на самом соревнований не заходит тут.

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

Тесты слабые по D, переполнение вообще не отлавливают. Например тест:

500 499 498 493
499 498 497 492

Ответ: 30627871499

Не знаю, как на онсайте, но в тренировке заходили даже решения "в лоб". Например 14421253