Если кто-то не может прийти к 12, то ничего страшного - приходите позже, вплоть до 15:30, для тех, кто придет к 12 я после контеста проведу обычный разбор, для тех, кто позднее письменный.

http://opentrain.snarknews.info/~ejudge/team.cgi?contest_id=006565

Для тех, кто дорешивает или хочет оценить в правильном ли порядке они решали задачи буду указывать примерную сложность задач:
1 - очевидная задача, в которой ничего не надо придумывать, не сложно писать, надо только правильно прочитать условие. Такие задачи на контесте надо решать обязательно, причем желательно в первый час.
2 - задача, которую легко придумать и не очень сложно писать. Если вы хотите пройти на полуфинал, то такие задачи надо решать
3 - задача, которую легко придумать и не очень сложно писать, но надо знать и уметь реализовывать классические алгоритмы. Если вы хотите пройти на полуфинал, то такие задачи надо решать.
4 - относительно непростая по меркам четвертьфинала задача (но )
A(1). Это простая задача, в которой нужно написать то, что просят. Самый простой способ - идти по командам начиная с победителей, пока не наберется 10 команд. В мапе по институтам храним сколько мы уже взяли из этого института, пропускаем команду, если в этом институте уже взяли достаточное количество команд.
B(1). Количество дней равно количеству различных идентификаторов D среди n*m чисел таблицы. Достаточно пройти по таблице и положить в мапу по идентификаторам сколько раз встречался каждый из них. После этого нужно рекуррентно вычислить значения маркет индекса в первые D дней, и сопоставить большие значения индекса комапаниям, которые встречались в таблице большее число раз. Для этого достаточно посортировать оба массива (значений индекса и количеств компаний в таблице) и перемножить их скалярно (меньшие с меньшими, большие с большими).
C(2). В этой задаче намного проще придумать решение и написать его, чем доказать его корректность. На московском чф такие задачи иногда дают, надо быть готовым. Чтобы решить такую задачу нужно перебрать сколько-то жадных идей, которые приходят в голову, когда видишь такую задачу - рано или поздно правильная идея придет в голову. Еще можно написать перебор для небольших тестов, это может помочь догадаться до верного решения.
Вначале опишем оптимальную конструкцию на паре примеров:
985 | 9853
674 | 6742
123 |
Начиная с больших высот к меньшим пристраиваем здания друг к другу "уголками", пока не заполним комплекс в ширину или в глубину, а потом начинаем заполнять "прямыми линиями". Иными словами мы стараемся сделать так, чтобы в процессе заполнения комплекса уже заполненный кусок был вначале как можно больше похож на квадрат, а потом на прямоугольник. После того, как заполнили все таким образом можно честно посчитать площадь внешних стен.
Также можно заметить (и это помогает доказательству), что внешняя площадь такой конструкции можно посчитать по фурмуле 4*b[0] + \sum_{i=1}^{n-1}(2*b[i*i]+2*b[i*i+i]) + \sum_{i=n}^{m-1}(2*b[i*n]), где b[] - массив высот упорядоченных по убыванию, n - меньшая сторона, m - большая сторона комплекса (чтобы это доказать, достаточно заметить, что все перечисленные номера - это номера зданий, которые самые высокие либо в своей строке, либо в своем столбце). В каждой линии (строке или столбце) есть наибольшая высота. Заметим, что сумма внешних стен в этой линии всегда будет равна этой наибольшей высоте помноженной на 2. После этого остается только доказать, что в нашей конструкции сумма таких высот минимальна.
D(3). По сути задача заключается в том, чтобы добавлять и удалять значения по ключу и уметь отвечать на запрос о k-й порядковой статистике. Это задача на структуры данных, которую можно было решать очень большим количеством способов. Самый известный - это декартово дерево. Тут: http://e-maxx.ru/algo/treap можно найти хорошее описание этой структуры данных, в том числе и той ее версии, которая решает данную задачу за .
В качестве альтернативы расскажу, идею того, как это решается с помощью sqrt-декомпозиции. Пусть m = sqrt(100000). Будем хранить всё в массивах длины m, в каждом массиве элементы расположены по циклу(начало может быть и не в нулевом индексе), причем упорядочены по возрастанию reliability. Пример: a[5]={4,5,1,2,3} - начало в индексе 2. Для каждого массива храним, какой индекс является его началом. Сами вектора между собой так же упорядочены по возрастанию reliability (в каждом следующем массиве любое reliability не меньше, чем любое reliability в данном массиве). Все массивы, кроме двух крайних должны быть полностью заполнены в любой момент времени. По сути нам нужно только уметь удалять и добавлять в такую структуру по одному элементу. Обе операции очень похожи, нужно за O(m) перекопировать элементы в том массиве, в котором происходит изменение, а потом перекидывать между соседними массивами по одному элементу. Чтобы не двигать весь массив будет достаточно двигать в нем только указатель на начало. Поэтому каждый запрос будет выпоняться за O(m), тк векторов будет не более m. Помимо этого нужно все время хранить по ключу в каком массиве и в каком месте хранится данный элемент.
E(3). Это почти классическая задача на рюкзак. Решается динамическим программированием, как это делается в самой простой формулировке можно прочитать здесь: http://neerc.ifmo.ru/wiki/index.php?title=Задача_о_рюкзаке
Данная задача отличается от классической тем, что помимо главной целевой функции \sum P_i, которую надо максимизировать, есть еще второстепенная целевая функция T1P1+(T1+T2)P2+..., которую надо минимизировать при равенстве главной целевой функции. Чтобы догадаться до правильного решения подумаем, как надо упорядочивать любые две задачи между собой: P1T1+(T1+T2)P2 < P2T2+(T1+T2)P1 T1/P1 < T2/P2. Несложно проверить (переставляя пару последовательных задач Pi и P(i+1)), что когда мы берем какой-то набор задач, то эти задачи должны идти по убыванию Ti/Pi. Теперь остается только посортировать все исходные задачи в этом порядке, а потом запустить на этом множестве классический алгоритм максимизации сумм Pi.
F(3). В этой задаче нужно было знать формулы перевода сферических координат в декартовы (можно посмотреть в википедии), уметь находить пересечение луча и сферы (решать квадратное уравнение), и определять находится ли данная точка X внутри сферического треугольника ABC (способ1: спроектировать все точки из центра на плоскость нормальную к сфере в точке X и потом работать с обычным треугольником, способ2: площать сферического треугольника легко вычисляется - это сумма сферических углов этого треугольника, поэтому достаточно проверить равенство SABC = SABX+SBCX+SACX)
G(2). Если бактерий 2 или 3, то ответ 0. Если их хотя бы 4, то ответ либо 2, либо 1, тк за две операции точно образуется как минимум одно совпадение, тк ((a+b)/2+(c+d)/2)/2=((a+c)/2+(b+d)/2)/2, где a,b,c,d - вектора координат исходных 4 точек. Остается выделить случаи, когда ответ равен 1, для этого достаточно промоделировать первый ход и проверить, есть ли одинаковые на первом же ходу.
H(3). Если в графе 3 или более компоненты связности, то ответ -1.
В самом начале с помощью Флойда-Уоршела найдем все попарные расстояния в графе.
a) Если компонент связности две (A, B), то надо соединить какие-то два города из разных компонент. Таких пар городов не более V^2/4. Для каждой пары x\in A, y\in B диаметр полученного графа равен max(d(A), d(B), d(x,A)+d(y,B)), где диаметры d(A),d(B) - вычисляются из Флойда заранее, а d(x,A) - это максимум по всем вершинам A расстояния до x, вычиляется за O(V). Сложность в итоге равна O(V^3)
b) Если есть всего одна компонента связности, то перебираем пару x,y вершин, между которыми проложим ребро веса ноль. Для каждой такой пары ищем диаметр полученного графа за O(V^2) -- перебираем любую пару вершин a,b, расстояние между ними равно min(d(a,b), d(a,x)+d(b,y), d(b,x)+d(a,y)), где d - расстояние в исходном графе, которое мы посчитали флойдом. Итоговая асимптотика O(V^4)
Остается только заметить, что компоненты тут нужны только для наглядности рассуждений, искать их не надо, достаточно просто запустить вначале Флойда, а потом действовать как в пункте b)
I(2). Нужно взять минимум из решений для вертикальной и горизонтальной дороги. Такая задача решается с помощью bfs или dfs, для примера рассмотрим горизонтальную дорогу. Если уже купленные дома пересекаются по проекции на дорогу, то решения нет. Делаем x-координаты всех домов вершинами графа. Те дома, которые пересекаются по проекции с уже купленными надо выкинуть. Все оставшиеся здания превращаем в ребра, соединяющие левую и правую координату здания. Остается только проверить есть ли в этом графе путь между левой и правой границей квартала.
J(4). В этой задаче нужно написать перебор, который просят.
K(3). Будем решать кубичекой динамикой с N^2 состояниями d[a][i][j] (a=0,1; i,j = [0,...,N-1]) - минимальное количество перекрашиваний, которое необходимо, чтобы перекрасить весь отрезок от i до j в цвет левого или правого края отрезка (здесь неявно используется тот факт, что если мы хотим покрасить этот отрезок в один цвет, то быстрее всего его красить в один из цветов краев, это легко доказать по индукции). Подсчет состояния динамики происходит за O(N) - отбрасываем с краев последовательные куски того цвета в который перекрашиваем, остается отрезок [i1, j1]. Его либо можно покрасить в один цвет целиком (и потом перекрасить в нужный цвет), либо он разбивается на два отрезка, каждый из которых надо покрасить в один цвет(и потом перекрасить в нужный цвет по необходимости).
L(2). Легко видеть, что максимальная последовательность чисел, в которой первые N цифр не совпадают с последними N это (x)(x+1),...,(x+1)(x). Ее длина равна 10^N, и понятно, что максимальная последовательность с неравными суммами не длиннее. Заметим, что если взять x=10^N-2, то эта верхняя оценка достигается.