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

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

Добрый день.

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

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

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

Участники, болеем за вас!

UPD 1: Спасибо, The.Fusy. Опубликована суммарная таблица результатов по многим регионам. Пока в ней только первый тур, но скоро появится и второй.

UPD 2: Второй тур завершен. Теперь можно отдыхать и немного переживать за квоты на заключительный этап.

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

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

»
4 года назад, # |
  Проголосовать: нравится -56 Проголосовать: не нравится
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    1. построить бор из цифр, каждый переход пометить кол-вом "проходящих" через него чисел
    2. жадный алгоритм
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

    Отсортируем строки по такому компаратору: если S + T > T + S, то строка S должна идти в отсортированом массиве раньше чем строка T. Ответом будет конкатенация отсортированого массива строк.

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

      как?

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

      можешь отправить код

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Код под спойлером
»
4 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

А можно ссылку на задания?

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

Только два вопроса. 1. Как эффективно выделить все циклы в графе? 2. Как решить 4? :)

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

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

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

      А как находить двусвязные компоненты? В Интернете не могу найти такой алгоритм.

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

        Мосты делят граф на компоненты

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

          Спасибо, надо было гуглить "Поиск мостов в графе". А выделением циклов никак нельзя уложиться во время?

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

            Тебе надо находить наибольшие из возможных циклов == двусвязная компонента

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

              Я dfs'ом находил хоть какие-то циклы, а потом с помощью системы непересекающихся множеств объединял. Про двусвязные компоненты до олимпиады вообще не знал. :) Спасибо. А по 4 есть идеи?

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

                1,5 группы бинпоиск по ответу, первые несколько — потоки, все — по особому применить формулу включения и исключения

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

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

                  Нужно что-нибудь, быстро считающее такое расстояние для каждой мобильности роботов. Можно написать дерево отрезков, или создать и поддерживать set расстояний с хотя бы одним свободным местом.

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

                  Бинпоиск работает для любых ограничений, если баз не больше 2, т.е. 1,2,5 подгруппы

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

                  Если база одна, то за линию проверяем для всех I, что все роботы с мобильностью <=I влезают в прямоугольник, раздувшийся на все стороны на I из точки базы, можно их не ставить явно. Итого max(W,H)*(log(K)+log(Z))

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

Где же, где же результаты?)

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

    Результаты некоторых регионов

    https://contest.yandex.ru/?postId=527

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

      так, 101 бал в третьей задаче — это официально???

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

        В листочке с заданиями сумма баллов по всем подзадачам 101.

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

          я знаю. вопрос в том, оффициально ли это. мы это багом условия посчитали. в совокупности с багованым описанием семпла во второй, посчитали, что у нас просто кривые условия. регион проводился на своей системе.

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

            Спрашивал в интерфейсе системы на олимпиаде. Сказали, что 101. Как говорится, не баг, а фича. Значит будет или суммарный 801, или во втором туре задача на 99.

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

            Как минимум была рассылка для председателей жюри — письмо Центральной предметно-методической комиссии по информатике, в том числе было про то, что в 3 задаче установлен максимальный балл 101. Исправленный пример во второй задаче тоже был в рассылке.

            Рассылка шла по линии АПК и ППРО, мне из нашего (Самарского) минобрнауки прислали.

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

              спасибо за разъяснение

              до Красноярска видать письмо не дошло :)

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

    Ни одного 400-балльника в Питере? Нифига себе олимпиада.

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

      Зато в Татарстане есть))

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

      В Красноярске есть 400 баллов

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

        А где пруфы?

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

          смотря что вы считаете пруфом :) я как организатор, могу подтвердить

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

            Ну, таблица по Красноярску была бы, конечно, предпочтительнее. Но я верю и на честное слово. Не будет же фиолетовый врать...

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

              есть такая таблица (Но из-за 101-го балла, она не совсем официальная)

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

                "Региональный этап ВсОШ по информатике 2017. Второй тур" Я что-то не понимаю или тут что-то не так?

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

    А есть результаты второго дня республики Татарстан?

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

Можете дать условия задач?

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

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

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

Будет ли зеркало?

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

    contest.samara.ru в помощь. Могу скинуть фото условия, если надо

    UPD: не доступна регистрация

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

Будут ли оглашены результаты первого тура в Саратове? Или они уже где-то есть?

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

Москва и МО? Екатеринбург? Челябинск?

  • Хотелось бы видеть эти регионы и в целом картина первого дня будет ясна
»
4 года назад, # |
Rev. 2   Проголосовать: нравится +80 Проголосовать: не нравится

Регион — это когда тебе обещают C++11, а по итогу он оказывается доступным только на компах — тестируется под Visual Studio 2005, а посреди контеста у тебя умирает codeblocks; это когда ты не можешь сдать задачу на пробном туре, потому что жюри забыло добавить тесты; это когда ждешь заданий основного тура до 10:50 вместо 10:00; когда не можешь сдавать в первые 15 минут, потому что жюри не может включить сервер; когда никто не может сказать тебе, какого размера стек, а у тебя из-за этого рекурсия падает ...

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

    Как то очень жизненно, если учесть, что мы из одного региона.

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

    Единственная из значимых неучтенных в таблице областей это Нижегородская. Так какие у вас результаты. Поделитесь хотя бы верхней пятеркой, желательно по 10 кл. Или дайте ссылку на результаты. Сочувствуем по поводу организации олимпиады. Было ли перетестирование

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

      Да, перетестирование было, один человек получил 101 за 3, у остальных без изменений

      По 10

      1) 678

      2) 574

      3) около 500

      4) 460

      Дальше у всех меньше 400 походу

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

У всех регионов, кто писал на Яндексе была очередь по 10-50 и больше минут?

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

    Следил за очередью на Ивановском регионе — к двум часам ожидание уже превышало 10 минут, а к концу олимпиады достигло пятидесяти. При том, что посылок у нас висело около двадцати единовременно.

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

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

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

      Ну, кстати, хорошо починили, на второй день тестилось все моментально!

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

      Подскажите пожалуйста, второй день с контестов на Яндексе будет дополнен по тем регионам, у которых пока только 1-й день указан?

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

Мб кому надо — сводный монитор Яндекс + Спб + Татарстан https://yadi.sk/i/w-nqjKXz3Cr6Rn

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

Красивое полное решение D (на туре не сдал, мне рассказали):

Сделаем бинпоиск по ответу (числу роботов) и будем проверять, существует ли паросочетание (пусть в левой доле роботы, в правой свободные места). Вместо того, чтобы явно строить его, воспользуемся теоремой Холла: если для любого k любые k элементов левой доли связаны по крайней мере с k элементами правой, то паросочетание полное (и наоборот).

Перебирать все 2t множеств и для каждого проверять долго. Перебирать не всё, а только крайние случаи, помогает следующая жадность: если мы включили в множество группу роботов с мобильностью m, то неравенство (число вершин в левой доле  ≤  числа вершин в правой доле) точно станет хуже, если мы выберем и все группы у этой же базы, у которых мобильность  ≤ m (потому что число вершин в левой доле увеличилось, а в правой не изменилось).

Отсортируем у каждой базы группы роботов по их мобильности и переберем максимальную мобильность у каждой базы (мы включаем в множество некий префикс всех групп). Число вершин (роботов) в левой доле — сумма на s префиксах. Число вершин (свободных мест) в правой доле — площадь объединения s квадратов, помноженная на q.

Асимптотика . Худший случай — когда у каждой базы по 25 групп роботов.

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

    Нам после тура рассказали именно это решение в разборе. Возможно, это авторское решение

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

    Да, это авторское решение. Правда, в асимптотике у вас 2s на объединение квадратов куда-то пропало.

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

Есть какие-нибудь данные (хотя бы опросные) по регионам, которых нет в таблице Яндекс.Контеста, но из которых обычно проходят люди? Всякие Москва, Челябинск, Екатеринбург, Саратов, Самара, Удмуртия и т.д.?

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

Раз уж архив уже опубликован, то вот готовая тренировка здесь: 2016-2017 Всероссийская олимпиада школьников по информатике, региональный этап, 1 тур.

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

Сделал таблицу общих результатов, если не заходит смотрите тут..

UPD1 Добавил Саратов (thx MikeMirzayanov)
UPD2 Добавил участников со всех страниц Яндекс.Контеста (thx geranazavr555)
UPD3 Добавил Иркутскую область (thx nevgen)
UPD4 Добавил Ленинградскую область (thx smirnov.i)
UPD5 Добавил Крым (thx ruperson)
UPD6 Добавил Вологодскую область (thx igand)
UPD7 Сделал табличку чуть красивее, добавил фильтр по классам/регионам (thx The.Fusy)
UPD8 Добавил Москву (thx nevgen)
UPD9 Добавлены результаты второго тура (весь Яндекс.Контест, Татарстан, СПБ, Ленинградская область, Крым, Вологодская область, Оренбургская область, Челябинская область, Саратовская область, Омская область)
UPD10 Добавил второй тур Москвы
UPD11 Начал добавлять оставшиеся регионы (Московская область, Самарская область, Иркутская область, Республика Адыгея)
UPD12 Обновил таблицу, выделил всех тех, кто прошел на финал

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

Есть ли результаты Москвы?

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

    Что-то стесняется Москва выкладывать свои результаты.)

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

    Появились. Я чуть выше скинул

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

Может, кто-нибудь разбор запилит по всем задачам? А то я, например, первые две не на полный балл решил

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

    В первой задачи надо сначала посчитать количество квартир в одном доме. Пусть n-число этажей, k-на каком этаже x квартир, y-сколько на остальных. Тогда формула будет m = (n/k) * x + (n — n/k) * y. Пусть теперь надо найти, на каком этаже квартира a. Сначала сделаем a = a % m, если a==0, то присваиваем a=m. Ну а дальше можно либо математикой, либо сделать двоичный поиск по этажу и считать кол-во квартир вплоть до этого этажа по формуле выше.

    Во второй надо заметить, что при увеличении N и постоянных a,b,c ответ может только увеличиться или остаться прежним, то есть функция неубывающая. Опять же можно сделать двоичный поиск по минимальному ответу. Мне было удобно решать с конца и смотреть, в какое максимальное число можно превратить текущее проверяемое значение. Если это максимальное число больше или равно N, то сдвигаем правую границу, иначе же левую.

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

      Вторая решается также трехмерной динамикой за 60^3.

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

        Думал о динамике, но не смог ее придумать и тупо написал двоичный поиск. :)

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

    Третья задача: найдем все мосты в графе (за квадрат 80 баллов, за линию 100 баллов), уберем их, в найденном графе каждую компоненту связанности представим как одну вершину и проведем между ними ребра (мосты, которые мы убрали шагом ранее). Мы получили дерево (если бы там были циклы, то мы бы сжали их в 1 вершину). Минимальное количество вершин в ответе = количество вершин в полученном дереве, степень которых равна единице. Количество способов выбрать эти вершины — произведение размеров компонент, которые мы сжали в эти вершины (степень равна единице).

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

    На самом деле, вторая задача решается без бинпоиска/динамики: 1) Пусть из числа N после нажатия определенной последовательности кнопок получили число X. Тогда из любого числа N1 <= N получим при той же последовательности X1 <= X, поскольку функция, заданная последовательностью кнопок, неубывающая. 2) Определим для каждой кнопки K "обратную" операцию K', которая определяет наибольшее возможное исходное число. Тогда:

    • A'(x) = 2 * x + 1
    • B'(x) = 2 * x
    • C'(x) = 2 * x + 2

    3) Из п. 1 следует, что ответ — наименьшее число такое, что при применении некоторой последовательности обратных операций получим число не менее N. Очевидно, для получения наибольшего числа выгодно применять обратные операции в порядке C' -> A' -> B' (поскольку +2 и +1 далее также умножаются на 2). 4) Таким образом, оптимальный порядок обратных операций: C' -> A' -> B', а значит, оптимальный порядок кнопок: B -> A -> C. Это и есть алгоритм: b раз нажать на B, затем a раз нажать на A, наконец, c раз — на С. Сложность: O(a+b+c).

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

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

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

        Возможно, это потому, что в случае a, b, c > 60 ответ всегда равен нулю, а значит, пройдет тот же бинпоиск и даже динамика за куб, только с одним лишним if-ом.

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

Если это реальное решение, то как это вообще возможно решить на олимпиаде? (А не дома за пять часов)

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

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

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

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

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

Простите, что врываюсь Мне тут один знакомый рассказал, что во второй задаче у него зашло на 100 решение, которое вытекало из использования сначала операции B, потом операции A, а потом С. Может быть с несколькими дополнительными if-ами... Это как-то не очень честно по отношению к тем, кто писал динамику (пусть и несложную).

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

http://codeforces.com/contest/673/problem/C как в задаче могли до сих пор не исправить семпл

Примечание В первом примере цвет 2 является доминирующим на трёх отрезках:

Отрезок [2, 2] содержит один шар. Этот шар имеет цвет 2, так что, конечно, 2 является доминирующим цветом для этого отрезка. Отрезок [4, 4] также содержит один шар, и цвет этого шара — 2. Отрезок [2, 4] содержит два шара цвета 2 и один шар цвета 1. На остальных 7 отрезках доминирующим является цвет 1.

там вот такое пишет а про отрезок [2, 3] они забили я не понимаю как никто етого не увидел во время контестаи какой у них тогда чекер?

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

    В случае, если таких цветов несколько, доминирующим называется тот из них, номер (индекс) которого минимален.

    с помощью примера вы должны понимать, что они имеют в виду значение, а не индекс

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

Если кому нужно, у нас можно виртуально дорешивать с оценкой по группам тестов: https://imcs.dvfu.ru/cats/main.pl?f=problems;cid=1124800

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

Теперь можно отдыхать

А как же суммарная таблица по двум турам =(

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

R.I.P. мой проход на всерос

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

Сколько людей с класса примерно пройдут на всерос?

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

    Могу предположить, что примерно столько же, сколько и в прошлом. В заключительном этапе в прошлом году участвовало:

    11 класс : 110

    10 класс : 75

    <=9 класс : 57

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

кто-нибудь решал 8ую за ?

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

    А это как?

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

      Давайте обойдём дерево в глубину и при заходе каждую вершину положим её в вектор на своей высоте.

      Давайте потом преобразуем запросы (v, k) в (a, b) — отрезок вершин на нужной высоте.

      Давайте оставим только различные пары (a, b). Утверждается, что их суммарная длина не более (константу не помню).

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

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

    Берем ограничения, в которые не вложены другие ограничения (для этого можно использовать dfs). Очевидно, что они не пересекаются. Далее делаем 2 указателя и смотрим кол-во выполняемых ограничений из взятых нами (1 вершина принадлежит максимум одному ограничению),

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

      Я в курсе про это решение (и про то, что оно круче)

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

Есть где-нибудь подробный разбор задач?

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

https://contest.yandex.ru Вторые дни регионов, писавших на яндексе выложили

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

какой прходной бал на всерос?Интересно знать свой уровень, заранее спасибо.

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

    Не известно еще, где-то к марту будем знать. Около 600, предположительно

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

      Не думаю. Из Санкт-Петербурга тогда всего 27 человек пройдет. Я думаю пройдет примерно столько же, сколько и в прошлом году, — баллов 520 можно ожидать.

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

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

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

    Для разных классов — разные баллы. Имхо, примерно, для 11-х — 615, 10-х — 560, 9 и младше — 520

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

Просто интересно: в чём был смысл 101 балла по 3-й задаче? В таблицах я нашел только один случай, где, если этот 1 балл отнять, места двух участников изменятся (что никак не влияет на проход и степень диплома).

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

    Ну если ты решишь задач ровно на 400 баллов (например, 4 задачи на 100), то ты — не призер региона, поскольку набрал меньше 50% от всех баллов

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

      Я думаю речь даже не о призер-непризер, а о том, что получив 400 баллов, нельзя будет пройти по квоте. В итоге квотников будет меньше.

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

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

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

    Одна из простейших версий)

    https://vk.com/wall27697_16493?reply=16495

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

    Ни в чем. Просто организаторы обсчитались и поздно заметили. Либо обсчитались и решили не исправлять ради прикола)

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

    апапапап

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

    Чтобы можно было набрать 666

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

Неизвестно, а когда Московская область будет? А то уже чего только не выложили, а её нет.

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

Суммарные результаты Саратовской области клик

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

А видеоразбор будет в этом году?

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

Гуру,навскидку — 699 баллов за два этапа могут обеспечить участие в заключительном этапе? Или все-таки проходной балл может быть выше?

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

    100% проходной. Для 11-х классов не больше 620 будет проходной, имхо

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

      Забыл уточнить. 699 за 10-й класс.

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

        У 10-го вообще думаю не больше 570

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

          Эти бы слова да главе комиссии в уши. В прошлом году многие призеры по Московской области не прошли

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

            по баллам конечно странно без Москвы делать прикидки, но 699 точно проход)

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

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

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

            Схема стандартная, последние годы неизменная. Призерство — вещь относительная, а баллы — абсолютная, значение имеют только они. Призеры с низкими баллами постоянно на заключительный не проходят. Более того — например, в этом году в Иркутске есть 11-классники — победители с 511 баллов. Но в Казань они точно не попадут

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

            Идите выпендриваться в свой регион со своими 699)

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

olymp.isu.ru — Иркутская область, два тура.

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

Результаты Москвы, скоро обновлю общую таблицу

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

Будет ли тренировка по 2 туру регионального этапа на Codeforces?

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

Интересно, почему Свердловская область два дня шифруется? Да и Самара тоже (рукописный скрин не считается) ))

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

    Самара будет шифроваться до десятого числа, а то и дольше. СИПКРО — очень медлительная организация (результатов математики самарцы ждали больше недели), а право выложить официальные результаты имеет только она, причем не факт, что это произойдет ровно в указанный на сайте день, может и намного позже.

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

      Сейчас никто не может выложить официальные результаты регионов ВОШ из предметов второй группы (к которой относится информатика). А вот по предварительным результатам никаких запретов нет, вроде.

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

        Ну под официальными результатами я имел как раз в виду официальные предварительные, а не "рукописный скрин", как вы сказали выше. Региональный этап в Самаре контролирует СИПКРО, а он почему-то решил, что будет выкладывать результаты (предварительные и окончательные) ровно в те даты, которые он назначает сам, по логике, понятной только ему, и ни днем раньше.

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

    В Свердловской области регион проводит Дворец молодежи, а они всегда сильно тормозят, они еще химию не выложили. По идее где-то на тимусе должны быть рез-ты, попробую узнать

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

    Точно знаю что по Свердловской области 1) 746 2) 699

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

      По Свердловской области результаты есть в виде фоточек (9 класс, 10 класс, 11 класс), но в итоговую табличку не вставить такие, до тимуса не могу достучаться

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

Когда второй день в тренировках появится?

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

Михаил , просьба добавить в топик основные ссылки

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

Пока многоуважаемый The.Fusy не обновил сайт — временная табличка, с добавлением Свердловской, Московской, Новосибирской, Самарской областей, Камчатского края, Республики Адыгея

UPD. Добавлен второй тур по Иркутской области и участники Нижегородской области от 400 баллов

UPD2. Добавлена вся Нижегородская область

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

    Учитывая, что здесь уже практически все регионы, по крайней мере значимые точно все, повангую проходные баллы на всерос — 590/540/480

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

если разбор пробного тура?

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

Самара полные результаты с разбаловкой по задачам: http://contest.uni-smr.ac.ru/ru/monitorvseros/519/521/

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

Иркутская учтен только первый тур на fusy. И по 10 кл можно добавить Николенко Московская обл, и Грибов Москва как призеры всероса за прошлый год

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

Татарстан пропал из fusy

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

Я правильно понимаю, что сложность для Задача 4.Полезные ископаемые O((lg(t)+lg(MaxN)) * (2t/s)^s) ? Т.е. lg(10^12)*50^4 = 2.5*10^8. В 1 сек точно влазит?

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

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

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

Уважаемые, может есть у кого в заначке ссылка на сводную таблицу баллов по регионам за 2015 и 2016 года ВсоШ (или файл). Что-то вроде той, что сделал The.Fusy?

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

Моя версия таблицы. — файл в экселе для скачивания.

Нюансы:

    • указал только потенциальных финалистов из примерного расчета в 260 человек + запас: все 11-кл с баллами выше 570, все 10-кл с баллами выше 520, все 9,8,7 кл с баллами выше 470 (+ частично ниже по всем классам);
    • второй день только общая сумма;
    • включена Якутия и еще несколько регионов, которые в других таблицах только с первым днем;
    • пока отсутствуют данные по регионам: Хабаровский край, Оренбургская и Брянская область;
    • справочно указаны двое призеров финала 2016, не участвовавшие в регионе 2017;
    • кое где проставлены по регионам баллы прошлого года для сравнения с текущим (без привязки к ФИО);
    • регионы с низкими баллами, явно не попадающие в финал, указаны справочно в списке в самом низу таблицы:
    • в книге отдельными листами добавлены года регионов 2016 и 2015 от NIC11, чтобы в будущем году не искать с указанием проходных баллов и количеством приглашенных участников по классам.

Всем, кто будет участвовать в финале — доброй охоты! ))

P.S. Если кто найдет ошибки, прошу сообщать в ветке, поправлю.

Update:

  • Добавлена цветовая дифференциация штанов призеров и победителей финала 2016 среди участников региона 2017;

  • появились данные Хабаровского края (в списке таблиц регионов-непопадаловцев).

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

Прогноз проходных баллов на всерос по второй группе предметов от портала olimpiada.ru http://info.olimpiada.ru/article/629

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

    Да, уже удивились люди в их группе ВК над прогнозом по проходным баллам информатике

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

      Согласен, по 11-м классам сильно завышено. И людей из 11х больше, и такое ощущение что они еще вычли количество прошлогодних победителей и призеров, а в ведь все кроме двоих в регионе участвовали

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

Проходные на всерос, официально <=9 класс — 473 10 класс — 550 11 класс — 621 http://info.olimpiada.ru/upload/files/VOSH2017/Kolichestvo_ballov.pdf

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

    Итого, по моим данным, далее проходят

    • из 11 классов проходит 94 человека по баллам + 3 по прошлогодним заслугам;

    • из 10-х классов — 82 по баллам + 2 за прошлогодние заслуги;

    • из =<9 классов — 56 человек.

    Всего — 237 человек. Может еще 1-2 добавятся.

    P.S. Прошлогодние проходные баллы (2016) — 9 кл. — 511 б., 10 кл. — 548 б., 11 кл. — 601 б.

    Похоже 11-е классы в этом году обидели

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

      А кто эти пятеро? Я только Николенко и Грибова знаю

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

        Бажанов (Питер) — 453 балла набрал в этом году Иванов (Питер) — 614 баллов в этом году Селиванов (Питер) — не учавстовал

        Вроде так, если я ничего не напутал

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

Искал информацию по поводу возможности участия в региональном этапе школьников младше 9-ого класса и не нашел однозначно ответов на свои вопросы.

Раньше для участия требовалось сдавать информатику экстерном до 9-ого класса. Сейчас это требование сохраняется или достаточно начиная со школьного этапа заявиться на участие среди 9-ых классов?
Если требуется сдавать экстерном, то поделитесь опытом, что для этого требуется сделать учащемуся?