Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

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

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

Вроде первый тур регионального этапа ВсОШ по информатике закончился везде где только можно, поэтому предлагаю здесь обсуждать региональный этап ВсОШ 2021. (Если у вас есть другая информация по времени окончания первого тура где либо — напишите пожалуйста)

UPD:

Комментарий с полезной инициативой от purplesyringa с опросом о баллах

Совмещенная таблица

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

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

A -- задача на формулу. B -- формула либо бинпоиск, для особо упор(от)ных -- тернарник. Пока все хорошо. Зато C -- задача на реализацию с разбором случаев и очевидной оптимизацией, на 250 строк. D -- нормальная классическая Dшка. Вот только из-за контраста B-C (по силе рук) и C-D (по сложности) у большинства участников результат будет около 300-316 баллов. В целом, было и лучше, и хуже, условия не слили -- уже хорошо. Ждем второй день.

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

    Вот только из-за контраста B-C (по силе рук) и C-D (по сложности) у большинства участников результат будет около 300-316 баллов.

    Непонятно оцениваете. У большинства не более 100 (максимум 150) баллов же, не?

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

      Окей, криво выразился. У большинства олимпиадников, которые стабильно проходят на регион. Здесь контраст в этой группе меньше, чем в прошлые года, не в последнюю очередь потому, что написать D на балл больше 16 -- это почти что решить на 100.

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

        Но в этом году тебя не интересуют многие топы при угадывании проходного

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

    Мне кажется 200-225

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

    Ну легко делается на 70 строк, из которых 20 — просто структура, и на самом деле случаев ~5

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

      (Хотя не отменяет тот факт, что задача мягко говоря не очень)

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

Опрос по баллам, в основном для Москвы: https://forms.gle/rhKf2DRkWUaxNtVM7

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

Все результаты вместе: https://reg.prog.cf

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

Когда добавят 1 тур в тренировки?

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

Извиняюсь, не заметил выше про ЯК

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

Задачи хлам, это касается переборных С и В

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

    В некоторых регионах ещё идет тур, воздержитесь от комментариев по задачам.

    UPD: Теперь можно )

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

Самый ужасный регион(как и по задачам, так и по балансу)

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

Православненький тур получился...

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

Результаты СПБ (без сириуса, оба дня) https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-spb-2021-standings.html

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

Имхо, 3 задача 2 дня отвратительна. Очень сильный контраст ощущается между 2 и 3 задачей, вторая решается быстро, третья просто МОШ за 10-11 какой-то. Ужасно, что решили ввести в регион такой тип задач. "Фармилка баллов", как по мне, можешь заслать какую-то фигню,а она пройдет. Я думаю, что это был самый неприятный регион среди всех как по балансу, задачам, так и по интересу

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

    Меня больше всего выбесило то, что много людей просто по приколу нашли тест на 95 ручками и все, в итоге это свелось просто к рисованию ручками

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

      Ну на 90 сдается что-то вида: набираем префикс, для текущей позиции берем рандомное значение, если оно допустимо(провереям что нет прямоугольников тз уже построенных). Так что ручками на 95, имхо, сложнее

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

        Ну у меня +- такое только на 75 :/ А на 85 только при помощи еще идейных оптимайзов, так что не соглашусь, да и ты опытный информатик, а 95 получают те, кто просто по приколу пошли на регион, увидели задачу, порисовали ручками примеры, и слали на 95, ничего не сделав, что супер-пупер-дупер плохо, как C региона.

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

          Ну такая С на регионе, конечно отвратительно, но зато теперь нет кучи людей с 316)

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

Красноярск has entered the chat

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

Второй день как-то не очень получился. Кажется, за недавнее время это первый регион, в котором C сильно сложнее D.

По порядку: A, B -- всякая математика, ничего интересного, решается за 10 минут. C -- задача, которая выглядит как обычный конструктив. И вы час сидите над C и пытаетесь понять, почему же конструктив не придумывается. Пропускаем C, решаем D -- почти халява. Немного тривиальных преобразований, и задача сводится к количеству эйлеровых путей на графе из двух вершин, там достаточно простая формула. За O(n^2) пишется просто, за O(n) надо чуть-чуть посидеть и пооптимизировать, но тоже пишется. Оставшиеся 3 часа убиваются на C с переменным успехом. Простейший рекурсивный перебор набирает ~80. Потом вы понимаете, что нужен прекальк, и в зависимости от удачи либо получаете 85 баллов, запрекалькав 9x9, либо 90, запрекалькав 10x8, либо 95, запрекалькав еще и 10x9.

Решение на 100 баллов, кстати, вот:

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

    Ну во-первых D — не очень приятно, нужно увидеть перегородки, а не полететь писать дпшку... случаи с нулями вообще мерзость... В с за 1:40 суммарно набралось 90 БЕЗ прекалька(хотя я пытался:) )

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

      'Количество разбений числа N на K слагаемых' -- достаточно классическая комбинаторная задача, я ее в первый раз увидел на курсах математики, а потом она где-то еще и в информатике всплыла. Я лично не считаю, что перегородки -- что-то жутко сложное, я в первый раз это минут за 10 придумал.

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

      всм. в д нули же вообще никак не мешали. ты просто перебираешь первое ребро(это +10 строк)

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

      Случай с нулями, кстати, я не очень понял. У меня решение практически нигде не опирается на нули, там разница в одном if'е.

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

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

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

      При случае с нулями и стартовым числом s ответ просто будет cnt[s]! — z[s] * (cnt[s]-1)!, где z[s] кол-во нулей в числах типа s, cnt — колво чисел типа s, непонятно че тут мерзкого

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

Результаты второго дня на Яндекс.Контесте: https://contest.yandex.ru/roiarchive/results/?postId=1018

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

Раз уж все начали писать про помойность задач, тоже хочу выразить свое недовольство помойными задачами на формулы, переборы, рисование и расписывание руками. Лично мне непонятно как можно давать А на формулу с решением в условии, Б на перебор "куда и что вставить" с учетом того что вчера была ровно такая же С. Замечательнейшая задача С которая решалась или локальным перебором, или локальным перебором руками)) (на 95 баллов. задача. с региона. по информатике. руками на листочке.). Ну и конечно моя любимая олимпиадная тема, то, что называют ad-hoc или "идейно" — Шары И Перегородки в задаче Д

Чувствуется вкус олимпиады по математике, отвратительно

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

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

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

      она простая на плюсах, а на медленном питоне я не смог оптимизировать блок с к=1 и пройти последнюю группу из-за лимита времени(

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

        Ну решение всего за 18*18*10*10, что мало и на чем угодно заходит, так что ваша фраза наглая ложь и провокация

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

        Б на 100 на питоне зашла за 190мс, нормально я считаю, даже с запасом

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

          как при k = 1 расписать это как адекватный человек без всякой сложной лабуды? При k=0 совсем очевидно, смотришь первую цифру и пара циклов фор, а вот для k = 1, не смог сделать быструю программу, когда x>10^12

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

            Честно, я сам не знаю, я делал перебор всех возможных вариантов (их около 100 вышло на число), что-то из серии возьмем первое, а остальное сделаем 0, 1, 2... Далее перебрал ещё разные варианты... А потом просто смотрю из всех таких возможных выбираю более подходящее, решение +- за длину числа * 10 было. Стресс-тесты очень сильно помогли, без них бы не смог сделать скорее всего

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

              уууу, не, мне такое делать лень было. Я брал переменную б и добавлял к ней 1, если она встречается в списке больше или равно, чем длина числа, которое рассматриваем. Потом рассматривал случаи, но так как перебор был таков: for i in range(x, x+10**17+1): аргумент то он был очень долгим, поэтому потерянные 44 балла

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

                Ну да, это и есть решение на честные 56 баллов ¯_(ツ)_/¯

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

      Было бы весело, если бы ее дали на длинку...

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

    Проблема C, на самом деле, не в том, что это прекальк, а в том, что она решается на высокий балл руками. Это автоматически переносит ее из разряда задач на информатику в задачу по математике (с ограничениями чуть пониже ее вполне можно дать на регион по математике, я думаю).

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

    Что тебе не понравилось в D? Ты говоришь так, будто там в условии написано "Шары и перегородки". Имхо ход мысли от исходной задаче к задаче, которая решается формулой неочевидный и довольно красивый. Если поставить ее на место C региона, то у меня вообще претензий к ней не будет.

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

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

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

        А что с ней не так для задачи на регион по инфе?

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

          Она на математику O_o В плане переход к такому графу очевиден, но потом просто нужно подогнать формулу, что мерзко, противно, и явно не соответствует задачам на регионе

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

            Кажется для того, чтобы считать задачу за задачу по математике нужно немного больше, чем "заметим, что мы ходим туда-обратно между двумя вершинами, теперь у нас есть несколько мест, куда мы можем вставить разряды типов 00 и 11, это можно решать шарами и перегородками". Это классическая комба, и ничего сложного в ней имхо нет.

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

      Какой ход мыслей, какие красиво, че?

      Задача решается так

      1) Нужно посчитать количество способов что то переставить

      2) Все столбики разбиваются на 4 типа

      3) Все в итоге состоит из отрезков вида ...axxxb...

      4) Ты знаешь количество всех штук, дальше — шары и перегородки.

      0 переходов. 0 идей. 0 "красивых" переходов.

      И не надо говорить что если ты сделал длинную "петлю" на пути к решению — то задача красивая. Если ты будешь решать задачу "найти сумму 2 чисел" нетривиальным сведением к NP-полной задаче, которой найдешь красивое полиномиальное решение — это не сделает задачу "сложить два числа" красивой.

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

        Ну меня, честно говоря, поразило именно то, что тип столбика не зависит от порядка столбиков, хотя сложение с переносом. Но, действительно, как-то на Dшку не тянет.

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

          Тебя удивило, что для столбиков важны только переносы? Если реально то ну ок. Но просто придумывать тут какие-то графы и пути это оверкилл и говорить что если ты просто начал усложнять себе жизнь и потом из этой тресины выбираться — это интересно, то я не согласен.

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

            Нет, это-то ясно. Просто обычно в задачах с суммой какое-нибудь дп по цифрам dp[i][carry], а тут оказывается, что дополнительно хранить carry не нужно. Это не то чтобы идейная задача, но мне понравился этот факт. На счет графов скажу так: в официальном решении 4 состояния, между которыми по определенному правилу может быть переход. Я же заменил вершины (need_carry, make_carry) на ребра need_carry->make_carry и получил граф из двух вершин. Идейно то же самое, но сложность уменьшилась.

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

              Так ведь по сути состояние need_carry жэто и есть carry :/

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

        Это очень субъективно. Я подобных переходов не видел и мне зашло, если для тебя это было очев — окей, тебе же лучше?

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

        Регион и не должен быть интересным для сильных участников.

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

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

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

Два года без дп :(

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

    В прошлом году была четвертая задача во втором дне на дп в ДО.

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

Если вдруг кто-то не видел, на https://reg.prog.cf появились результаты второго дня.

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

Как думаете какой проходной будет при таких странных задачах?

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

Юху, походу оба Некрасова Александра Павловича пройдут на РОИ2021, и мне интересно, не будут ли их в этом случае путать, да и как вообще различать будут?

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

Сходила я на этот ваш регион. Получилось прикольно, только не поняла, куда 10 часов делись.

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

Картинка: Pics-Art-01-18-04-07-27

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

cs.umd.edu//papers/gridpaper.pdf Фанатам цшки рекомендуется к прочтению

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

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

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

Интересно. Олимпиада появилась в разделе "Тренировки", побыла там немного и пропала

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

Подскажите, пожалуйста, через какое время в среднем появляются проходные баллы? Например, в прошлом году?

И ещё вопрос : каждый регион сам выбирает кто там будет по региону призер/победитель (самому-то не важно, но родители интересуются)? Или составляется общий по регионам список и берется процент оттуда?

Заранее благодарю.

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

    Проходные баллы, а также баллы призёра и победителя устанавливаются на всю страну. Обычно они появляются примерно через месяц после региона, например в 2020 появились около 14 февраля.

    UPD: как подметили ниже баллы призёра и победителя устанавливаются регионом. Просмиите за дезинформацию!

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

Задачи регионального этапа можно сдавать на Яндекс.Контесте:

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

Проходные баллы на заключительный этап 9 класс — 532 10 класс — 588 11 класс — 612

https://vos.olimpiada.ru/files/m_files/169/letter-minpros-03-236-ot-04-03-2021.pdf