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

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

В Алматы завершается IX Международная Жаутыковская олимпиада (МЖО) по математике, физике и информатике – совместный проект Республиканского научно-практического центра «Дарын» и Республиканской специализированной физико-математической средней школы-интерната имени

О.Жаутыкова для одаренных детей, осуществляемый под эгидой МОН РК, при поддержке акимата города Алматы. Особенность олимпиады заключается в проведении олимпиады по трем предметам ежегодно на базе одной школы (РСФМСШИ) с выведением рейтинга сильнейших команд специализированных школ.

В олимпиаде приняли участие 53 команды (348 участников) специализированных школ из 13 стран – России, Украины, Азербайджана, Грузии, Армении, Казахстана, Кыргызстана, Таджикистана, Туркменистана, Румынии, Болгарии, Индонезии и Монголии. Компетентное жюри представлено специалистами 7 стран: Казахстана, России, Болгарии, Белорусии, Армении, Грузии и Узбекистана. Председатель жюри – ректор КазНУ имени аль-Фараби Мутанов Галымкаир Мутанович, сопредседатель – академик НАН РК Джумадильдаев Аскар Серкулович.

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

По итогам олимпиады определятся 7 команд лучших специализированных школ – победителей олимпиады (в их числе обладатель Гран-при). Их ждут ценные призы от спонсоров олимпиады.

Спонсорами IX МЖО являются генеральный партнер олимпиады Общественный фонд «Фонд выпускников РСФМШИ» и генеральный спонсор компания «ЭксонМобил Казахстан», в течение восьми лет поддерживающие организацию и проведение олимпиады на высоком уровне.

Если можете дайте ссылку на архивы МЖО?

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

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

...

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

    На фото — команда РСФМСШИ имени Жаутыкова. Они заняли третье общекомандное место

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

    Какой-то неполный пакет, в нем нет ни исходников чекеров, ни авторских решений. Если первое еще не страшно — в каждой задаче единственно возможный ответ, то без эталонных решений заливать куда-либо задачи не очень удобно, даже если есть ответы на тесты.

    Заодно хочу спросить, как решать задачи С и G, если кто-нибудь знает. Сам могу рассказать любую из остальных.

    Тем, кто не хочет качать толстый пакет в 60 мб, вот условия — русская, английская версии.

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

      Пожалуйста напишите разбор.

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

      Задача С:

      Отсортируем все пары чисел по невозрастанию A[i]. Будем перебирать первые K пар в этом списке (K от M до M+S) и скажем, что все эти первые K пар будут взяты в сумму (либо по A, либо по B) и более того, ровно M из них будут взяты по A. Теперь несложно видеть, что ответ достигается при одном из этих K.

      Как понять какие M пар внутри первых K брать по A? Нужно отсортировать список по разнице A[i]-B[i] и взять M пар с наибольшей разностью.

      Осталось только понять как обновлять ответ при увеличении K на единицу. Наибольшие M по разности пары можно поддерживать в очереди с приоритетом. Наибольшую сумму по B в оставшемся куске (кроме первых K) можно поддерживать с помощью множества.

      Вот, например, мое решение.

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

      Как решать Д-шку на 100 ?

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

        Задача D:

        Заметим, что граф имеет вид нескольких циклов, за вершины которых прицеплены деревья.
        Найдем все циклы в графе, построим на каждом цикле дерево отрезков, в вершину дерева отрезков положим время, когда исчезает ребро из данной вершины.
        Пустим DFSы из всех вершин циклов по обратным ребрам в эти деревья. Теперь, придя в какую-либо вершину, будем оффлайн отвечать на запросы.
        Несложно показать, что из любой вершины мы можем попасть либо в вершину цикла, на котором висит рассматриваемое дерево, либо в одну из вершин, которые находятся в стеке вершин, посещенных текущим DFSом (т.е. все предки этой вершины в дереве).
        Построим по стеку этих вершин (по предкам) еще одно дерево отрезков.
        Когда рассматриваем запрос, есть три варианта:
        Вершина, в которую нужно прийти, лежит на стеке DFSа. Запросом к дереву отрезков находим ребро, которое будет удалено на этом пути раньше всего и сравниваем время его удаления с временем запроса. Если ребро будет удалено позже, чем сделан запрос, то по высотам восстанавливаем длину пути.
        Вершина, в которую нужно прийти, лежит на текущем цикле. Находим ребро двумя запросами к дереву отрезков — один запрос по всему стеку, другой — аккуратно по циклу.
        Любой другой случай — вершина точно не будет посещена.
        Каждый запрос обрабатывается за логарифм. Итого — O(M log N).
        Единственная задача, по которой не было фидбека и которую нельзя было не тестировать.

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

      Напиши как решить F?

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

        Сделаем бинарный поиск по величине самой дешевой клетки(понятно что такая функция монотонна). Пусть мы рассматриваем некоторую цену p. Заменим каждое значение таблицы на 0(если значение в этой клетке меньше чем p) или на 1(если больше или равно p). Теперь понятно что нужно найти наибольшую единичную подматрицу. Суммарная ассимптотика такого решения будет O(NMlog(maxK)).

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

          Спасибо большое! Можешь написать как решит H на сто если знаешь?

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

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

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

              Спасибо! А можно легче решить если цена каждый день не будет увеличиватся???

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

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

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

English version: "Diploma of the 1st Degree is delivered to The Republican Specialized Physics-Mathematics Secondary Boarding School named after O.Zhautykov for gifted students (Almaty, Kazakhstan)."

I think diploma of the 1st Degree went to The Public School #199 "Komarovi" (Tbilisi,Georgia). Team Rating Link :)

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

    In the english version of the article is a huge mistake. There's information about IZhO VIII, not IX.

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

Could someone explain the solution of problem A? Thanks in advance. https://docs.google.com/file/d/0B_BCx3O6Gp4WUE1CUzJ6RUpkNXc/edit?pli=1

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

    i thought it was just problem for implementation, because haven't seen that T = S^K:) Do anybody have any ideas about this problem ?