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

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

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

P.S. Регионы прошлых годов: http://informatics.mccme.ru/moodle/course/view.php?id=46

P.P.S. Ответ "_посмотри, что было раньше, у тебя же архив_" не очень мне интересен, хотелось бы получить цельную информацию, чего можно ожидать. Тем более, что думаю этот вопрос интересует не только меня.

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

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

Можно ожидать 2 дня по 4 задачи.

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

    Так толсто, что даже тонко.

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

      Не, ну серьезно, а чего ты ожидал? Что кто-то из авторов задач, расскажет какие алгоритмы тебе пригодятся?

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

      PS: Прокачивай опыт решения задач, мат. чутье и здравый смысл лучше всего, гораздо полезнее на начальном уровне, чем пачка алгоритмов.

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

Можно ожидать то, что было в последние несколько лет (примерно). Итак, план на оба дня:

  1. Простая задача, либо очень простая задача. Какие-нибудь if'ы, циклы, нужно просто уметь программировать.
  2. Задача на какую-нибудь несложную идею. Обычно, тоже простая.
  3. Задача на какую-нибудь технику (достаточно сложную). Иногда нужно немного знаний.
  4. Сложная задача на какую-нибудь сложную идею.
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

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

      Какой смысл тогда участвовать победителям и призёрам? Получается, что своим участием они лишают кого-то шанса пройти на финал.

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

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

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

          Получается,на каждый регион определены квоты? Где их можно узнать(+ регламент проведения)?

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

            Надо быть призером в своем регионе. Дополниельных квот нет. Призеры — 45% участников если я правильно помню. Распределение по классам на усмотрение регионального жюри. В числе 45 не уверен, смотрите положение (где-то там же еще было число 30).

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

              Стоит отметить, что особо экономящие регионы еще и сокращают процент:(

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

              Квота в 45% — это для заключительного этапа.

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

              И п.45 дословно: "45. Квота победителей и призеров регионального этапа Олимпиады по каждому общеобразовательному предмету определяется организатором регионального этапа Олимпиады по согласованию с оргкомитетом регионального этапа Олимпиады и составляет не более 25 процентов от общего числа участников регионального этапа Олимпиады по соответствующему предмету."

              Как уже было выше, для заключительного этапа ситуация иная, описана в п.59: "59. Квота победителей и призеров заключительного этапа Олимпиады по каждому общеобразовательному предмету определяется Центральным оргкомитетом Олимпиады и составляет не более 45 процентов от общего числа участников заключительного этапа Олимпиады, при этом число победителей заключительного этапа Олимпиады не должно превышать 8 процентов от общего числа участников заключительного этапа Олимпиады."

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

                Мне казалось, что с прошлого года процент победителей и призёров сократили до 35%, разве нет?

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

                  Что знаю совершенно точно — что была редакция этого приказа от 7 февраля 2011 года (ссылка), но она носила чисто технический характер, а проценты остались прежними.

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

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

                  Если я не ошибаюсь, то все олимпиады 2011/2012 учебного года имели ограничение на призёров — 35%. Это уже был приказ, вышедший после 1 сентября 2011.

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

                  А можно ссылку на этот приказ с ограничением? Или хотя бы его номер / какие-то иные данные?

                  Теоретически 35% — это "не более 45%", как того и требует "Положение...", но если существует официальный документ, в котором указано именно 35%, конечно, хотелось бы его увидеть.

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

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

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

    Результаты проверки только после тура.

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

      Я так нигде и не нашёл официальный регламент на 2012/2013г. На муниципальном этапе у нас вообще например решения проверялись на вручную вбитых тестах (и было обидно когда у кого-то проходило решение за n^4). Как вообще будут тестироваться задачи? Обязаны ли проводить пробный тур? Какие среды должны поддерживать? Обязаны ли проводить разбор? Что делать если что-то нарушается?

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

        Регламент поищите на rosolymp.ru

        Только этого скорее всего там нет. Есть методические материалы, но их явно нет в открытом виде, так как они содержат информацию про задачи. В частности там прописано, как должны оцениваться решения. Наборы тестов также рассылаются по регионам. Соответственно тестирование на чем-то отличном от этого набора тестов является нарушением. Материалы вроде батников "запустить все, проверить ответы чекером и.т.д" тоже вроде есть.

        Пробный тур должны проводить если есть какая-то система тестирования. Если нет — не обязательно.

        Должны быть установленные компиляторы для C,C++,Pascal,VB. Какие именно там прописано, точно не помню. И еще на усмотрение организаторов могут быть добавлены C#,Java,Python и что-то еще, без гарантий, что задачи сдаются на этих языках на 100 баллов.

        С нарушениями сложнее. По большому счету все решает региональное жюри, и фиг и в чем переубедишь. На жалобу, скорее всего настучат по голове и скажут так не делать в следующий раз. А может и того не будет.

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

    Предусматривается возможность проверять, но не сообщать участникам.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

По-моему не в пятницу, а в субботу

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

Может кто-нибудь всё же озвучит, скажем так ТОП20 наиболее вероятных алгоритмов?

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

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

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

    Почему минусуют gofkane?

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

    Математика.

    1. Бинарное возведение в степень.
    2. Алгоритм Евклида.
    3. Обратный элемент в кольце по модулю.
    4. Решето Эратосфена.
    5. Вычисление биномиальных коэффициентов C(n,k).

    Графы.

    1. Поиск в ширину.
    2. Поиск в глубину и его применения (топологическая сортировка, компоненты связности).
    3. Алгоритм Дейкстры (кратчайшие пути от одной вершины).
    4. Алгоритм Флойда (кратчайшие пути между всеми парами вершин).
    5. Алгоритмы Прима и Краскала (минимальный остов).
    6. Алгоритм Куна (максимальное паросочетание).

    Геометрия.

    1. Точка пересечения двух отрезков.
    2. Уравнение прямой по двум точкам.
    3. Площадь выпуклого многоугольника.
    4. Алгоритмы Грэхема и Джарвиса (выпуклая оболочка).

    Строки.

    1. Хэши и их применение (самое простое — алгоритм Рабина-Карпа для поиска подстроки в строке).
    2. z- и префикс-функция. Хотя при знании бинпоиска и хэшей можно обойтись без них.

    Структуры данных.

    1. Дерево Фенвика (проще структуру данных трудно придумать).
    2. Дерево отрезков.

    Базовые идеи.

    1. Жадность (например, задача: минимальное количество монет, чтобы дать сдачу, если все номиналы делятся на меньшие).
    2. Динамическое программирование (например, предыдущая задача, если номиналы не делятся; задача о рюкзаке; наибольшая возрастающая подпоследовательность; наибольшая общая подстрока).
    3. Бинарный поиск (с помощью него + хэшей можно решить почти все задачи на строки ну и сам по себе он часто нужен — если функция ответа монотонная, то решение можно искать бинарным поиском).
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В этом году будут группы тестов?

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

    на регионалке — нет

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

    Что подразумевается под группами тестов?

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

      "Подзадачи" с РОИ.

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

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

        Нет, такого нет. Это было бы интересно, но слишком "сложно" для многих регионов. Все также, как и раньше...

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

Кто-нибудь выложит условия?

»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Комментарий удален администрацией по причине несоблюдения правил сайта.