В Алматы завершается IX Международная Жаутыковская олимпиада (МЖО) по математике, физике и информатике – совместный проект Республиканского научно-практического центра «Дарын» и Республиканской специализированной физико-математической средней школы-интерната имени
О.Жаутыкова для одаренных детей, осуществляемый под эгидой МОН РК, при поддержке акимата города Алматы. Особенность олимпиады заключается в проведении олимпиады по трем предметам ежегодно на базе одной школы (РСФМСШИ) с выведением рейтинга сильнейших команд специализированных школ.
В олимпиаде приняли участие 53 команды (348 участников) специализированных школ из 13 стран – России, Украины, Азербайджана, Грузии, Армении, Казахстана, Кыргызстана, Таджикистана, Туркменистана, Румынии, Болгарии, Индонезии и Монголии. Компетентное жюри представлено специалистами 7 стран: Казахстана, России, Болгарии, Белорусии, Армении, Грузии и Узбекистана. Председатель жюри – ректор КазНУ имени аль-Фараби Мутанов Галымкаир Мутанович, сопредседатель – академик НАН РК Джумадильдаев Аскар Серкулович.
В индивидуальном первенстве ожидается награждение 30 золотыми, 60 серебряными и 85 бронзовыми медалями.
По итогам олимпиады определятся 7 команд лучших специализированных школ – победителей олимпиады (в их числе обладатель Гран-при). Их ждут ценные призы от спонсоров олимпиады.
Спонсорами IX МЖО являются генеральный партнер олимпиады Общественный фонд «Фонд выпускников РСФМШИ» и генеральный спонсор компания «ЭксонМобил Казахстан», в течение восьми лет поддерживающие организацию и проведение олимпиады на высоком уровне.
Если можете дайте ссылку на архивы МЖО?
...
На фото — команда РСФМСШИ имени Жаутыкова. Они заняли третье общекомандное место
Какой-то неполный пакет, в нем нет ни исходников чекеров, ни авторских решений. Если первое еще не страшно — в каждой задаче единственно возможный ответ, то без эталонных решений заливать куда-либо задачи не очень удобно, даже если есть ответы на тесты.
Заодно хочу спросить, как решать задачи С и G, если кто-нибудь знает. Сам могу рассказать любую из остальных.
Тем, кто не хочет качать толстый пакет в 60 мб, вот условия — русская, английская версии.
Пожалуйста напишите разбор.
Задача С:
Отсортируем все пары чисел по невозрастанию 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) можно поддерживать с помощью множества.
Вот, например, мое решение.
Как решать Д-шку на 100 ?
Задача D:
Заметим, что граф имеет вид нескольких циклов, за вершины которых прицеплены деревья.
Найдем все циклы в графе, построим на каждом цикле дерево отрезков, в вершину дерева отрезков положим время, когда исчезает ребро из данной вершины.
Пустим DFSы из всех вершин циклов по обратным ребрам в эти деревья. Теперь, придя в какую-либо вершину, будем оффлайн отвечать на запросы.
Несложно показать, что из любой вершины мы можем попасть либо в вершину цикла, на котором висит рассматриваемое дерево, либо в одну из вершин, которые находятся в стеке вершин, посещенных текущим DFSом (т.е. все предки этой вершины в дереве).
Построим по стеку этих вершин (по предкам) еще одно дерево отрезков.
Когда рассматриваем запрос, есть три варианта:
Вершина, в которую нужно прийти, лежит на стеке DFSа. Запросом к дереву отрезков находим ребро, которое будет удалено на этом пути раньше всего и сравниваем время его удаления с временем запроса. Если ребро будет удалено позже, чем сделан запрос, то по высотам восстанавливаем длину пути.
Вершина, в которую нужно прийти, лежит на текущем цикле. Находим ребро двумя запросами к дереву отрезков — один запрос по всему стеку, другой — аккуратно по циклу.
Любой другой случай — вершина точно не будет посещена.
Каждый запрос обрабатывается за логарифм. Итого — O(M log N).
Единственная задача, по которой не было фидбека и которую нельзя было не тестировать.
Напиши как решить F?
Сделаем бинарный поиск по величине самой дешевой клетки(понятно что такая функция монотонна). Пусть мы рассматриваем некоторую цену p. Заменим каждое значение таблицы на 0(если значение в этой клетке меньше чем p) или на 1(если больше или равно p). Теперь понятно что нужно найти наибольшую единичную подматрицу. Суммарная ассимптотика такого решения будет O(NMlog(maxK)).
Спасибо большое! Можешь написать как решит H на сто если знаешь?
Модификация дерева отрезков с интервальными операциями. Построим над городами дерево отрезков. Теперь будем по очереди обрабатывать всех торговцев и обновлять ответ на отрезке. Аналогично присвоению на отрезке только здесь пропихивание отложенного обновления из вершины в сыновей будет происходить таким образом: в вершине хранится число х — цена продаж в первом городе отрезка данной вершины дерева, тогда в левого сына записываем х, а в правого
х + mid-l+1(где mid,l — середина и левая граница отрезка соответственно).После обработки всех торговцев пропихнем оставшуюся информацию в листья и это и будет ответом. C++ КодСпасибо! А можно легче решить если цена каждый день не будет увеличиватся???
Я лично сомневаюсь что можно как-то проще решить(без структур данных). Я бы писал дерево отрезков будь такая задача, оно впрочем не сложно пишется ведь.
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 :)
In the english version of the article is a huge mistake. There's information about IZhO VIII, not IX.
Could someone explain the solution of problem A? Thanks in advance. https://docs.google.com/file/d/0B_BCx3O6Gp4WUE1CUzJ6RUpkNXc/edit?pli=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 ?