Если я правильно помню, регистрация на тренировку (имеющую фиксированное время начала) автоматически открывается за 6 часов до старта; регистрироваться и участвовать можно до окончания тренировки.

It's a gym contest.

Ну может хотя бы со стремянками?

Contest will be available in Gym.

dp[i][j] — можно ли через i ходов иметь число j. Дальше ищем достижимое состояние с максимальным i

у меня была динамика. DP[i][j]= 0 или 1 , в зависимости от того можно ли за первые I чисел получить сумму J.

I — переберем умение, которое будет минимальным, дальше по каждому ищем минимальное значение, большее данного. Быстро делаем так: отсортируем возможные умения одного типа и будем поддерживать для других указатель на минимальное значение, большее данного.При переходе двигаем как в 2 указателях

I. Перебираем минимальное число которое мы возьмем, и для каждого массива будем брать наименьшее число, которое больше либо равна нашего минимума. Это можно сделать с помощью сета.

К — динамика dp[i][j]: за сколько ходов мы можем поставить на первые i + j мест i букв A и j букв N. С учетом того, что относительный порядок этих букв в оптимальном решении не меняется, можно узнать, какую именно из букв A или N требуется поставить на позицию i + j и посчитать, сколько ходов понадобится на то, чтобы поставить эту букву на место. С учетом dp[i - 1][j] или dp[i][j - 1] в зависимости от взятой буквы считаем dp[i][j].

I — Отсортируем все вместе умения вместе, для каждого вместе с ним храним сферу деятельности. Теперь для каждого i нужно посчитать минимальное j, так что между i и j есть все сферы деятельности. Сортировка за O(nmlog(nm)), остальное за O(nm)

В задаче K можно было перебрать позицию до которой не будет буквы F, и после которой не будет буквы A.

В нашей команде задачу K решил kaliostro за линию: пройдемся двумя указателями — с начала строки для F и с конца строки для A. Для каждой встреченной пары i < j: s[i] == F, s[j] == A — прибавляем к ответу разницу в их индексах (именно столько действий потребуется для обмена этой пары букв) и переходим к следующим позициям.

Вот код решения:

int answer = 0;
for (int i = 0, j = n - 1; i < j; ++i, --j) {
 while (i < n && s[i] != 'F') ++i;
 while (j >= 0 && s[j] != 'A') --j;

 if (i < j) answer += (j - i);
}

Minimum spanning tree, answer is maximum edge weight

Let's build graph, where string are verticles abd between each pair of verticles there is an edge of weight equal to difference between strings. Now question is: what is the smallest K such a graph with edges with weights <=K is connected. It can be done using binary search. If we fix K we just do dfs which is going by edges <= K and check if graph is connected

my solution : build graph with recipes. g[i][j] is equal to distance between recipe i and recipe j. then use binsearh for answer: for the fixed answer there shuold be a path with all recipes and without edges with weight greater then anwer

ans = 0
while (true) {
  posA = (position of the rightmost not processed 'A')
  posF = (position of the leftmost not processed 'F')
  if (posA < posF) break
  ans += posA - posF
}

Here's my idea: all we want to do is all As should come before F. Now considering A and F are some values such that A<F now we want to calculate no of inversions ( problem becomes similar to sorting an array with only operation of swapping two adjacent elements. I dont know proof but its equal to no of inversions in the array). Now main problem is every N can be taken as A or F. Which we can solve using a recursive function with two arguments 1.position we are referring to 2.no of Ns considered as F before this position. For every F just count no of As after that position. For every A dont do anything. Now for every N if we consider it as F do same thing as normal F and if its A then add to the answer total no of Fs before this position (original no of F + considered ones). I hope this helps.

consider dp[i][j][k] which means how many swaps do we need to move all A's in first k positions of substring(i,j) and moves F's out of first positions.
then you can update dp so easily.

Вот мой код для задачи E: http://pastebin.com/48L57tZs

Запускаем dfs от первой вершины.

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

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

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

Пусть мы просматриваем непосредственного потомка U вершины V. Если от U можно добраться до более раннего предка не через V, то при удалении V U будет принадлежать компоненте c предками. Иначе при удалении V образуется компонента, состоящая из вершины U и всех ее потомков.

Итак, для каждой вершины V будут известны размеры компонент, образующихся при удалении V, размер компоненты с предками равен n — 1 — сумма_размеров_остальных_компонент. Ответом является вершина, для которой максимальный из размеров образующихся компонент минимален.

P.S. Кажется, я изобретал велосипед. Если от U нельзя добраться до V или более раннего предка, не используя ребро, соединяющее V и U, то это ребро является мостом.

P.P.S. Код чуть попроще.

Something similar to:
7 5
1 1 1 1 1 5 1
Correct answer is
7
+++++-+
but your answer is 5.
Correct approach is dynamic programming dp[i][j] — are we able to get number j after i moves.

Try this:

4 100
50 10 10 60

Build pairs of  < skill, field >  for each course, sort all of them in increasing order by skill and find an interval [i, j] of courses which has the following properties:

1. There exist at least one course for each field in that interval
2. Skill[j] - Skill[i] is minimum

Мое решение было не "основным", но, как мне кажется, достаточно понятным

Сразу (при чтении) будем формировать отрезки времени, в которые этот коридор свободен — т.е. каждый коридор у нас будет описываться набором свободных отрезков [b_j..e_j]. Вообще свободный отрезок — важная для нас структура, поэтому, кроме границ отрезка мы будем также хранить в нем самый ранний момент времени, в который мы можем переместиться в коридор ниже. Понятно, что исходно этот момент для всех отрезков будет равен (b_j + 1) (на самом деле в структуре в моем решении хранились все моменты перехода, но это уже технические подробности). Для краткости далее я буду говорить о "точках перехода". Достаточно неформально можно понять, что чем левее на отрезке точка перехода, тем он "лучше" — больше возможностей уйти вниз.

Воздушных коридоров (эшелонов, но решили уж избегать этого слова) у нас не очень много — не более 100. Попробуем зафиксировать какой-то коридор в качестве стартового и выясним, в какое самое раннее время мы можем долететь.

Пусть мы зафиксировали коридор #k. Теперь будем двигаться по его свободным отрезкам и — параллельно — по коридору #(k + 1), при необходимости "подклеивая" отрезки коридора #(k + 1) к отрезкам коридора #k (полагаем, что коридор #(k + 1) у нас есть; более того, есть и коридоры еще ниже). Эти "склеенные" отрезки мы будем помещать в новую очередь (список), после чего используем их при рассмотрении коридора #(k + 2).

Когда такая необходимость возникает?

Если рассматриваемый отрезок коридора #k имеет границы b_j и e_j, точка перехода у него c_j (на первом шаге c_j = b_j + 1, в дальнейшем это может быть не так); рассматриваемый отрезок коридора #(k + 1) имеет границы x_i и y_i, возможны следующие варианты (рассматривать их нужно последовательно):

А. x_i < b_j — такой отрезок из коридора #(k + 1) на этом этапе рассматривать не нужно: если даже мы можем перейти из отрезка коридора #k в этот отрезок и впоследствии достичь конечного пункта, при рассмотрении коридора #(k + 1) в качестве стартового этот результат будет неизбежно улучшен.

B. y_i ≤ c_j — такой отрезок рассматривать нельзя: мы просто не сможем попасть в него из коридора #k (а даже если попадем, то не сможем находиться в коридоре #(k + 1) требуемую единицу времени).

C. b_j < x_i < c_j — в этом случае мы можем спуститься в коридор #(k + 1) в момент c_j, так что мы можем сформировать новый отрезок с границами b_j и y_i и точкой перехода c_j + 1. Этот новый отрезок мы поместим в очередь, о которой говорилось выше.

D. c_j ≤ x_i ≤ e_j — в этом случае мы также можем спуститься коридором ниже и сформировать отрезок с границами b_j и y_i и точкой перехода x_i + 1. Этот отрезок мы тоже поместим в очередь.

E. e_j < x_i — перейти в коридор #(k + 1) нельзя, нужно рассматривать следующий отрезок в коридоре #k.

Таким образом, при проходе по коридорам #k и #(k + 1) мы сформируем новую очередь отрезков, которые упорядочены по левым концам, а при равенстве левых концов — по точкам перехода. Теперь точно так же возьмем за основу полученный набор отрезков и будем двигаться по нему и отрезкам коридора #(k + 2).

Мы будем действовать жадным образом: если есть возможность присоединить какой-то отрезок из #(k + 2) к отрезку из очереди — мы будем это делать (можно показать, что это никогда не ухудшит ответ).

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

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

UPD Асимптотика:
Для каждого коридора (коих n) мы пройдем по всем нижележащим. В силу "жадности" при формировании очереди в ней всегда будет отрезков не более, чем в том коридоре, отрезки которого "подклеиваются", а переберем мы в худшем случае все отрезки всех коридоров по одному разу. Таким образом, оценка — .

Ну и собственно код: pastebin

Вначале по поводу WA 17:

При сжатии координат необходимо учитывать не только время открытия/закрытия, но и моменты времени на 100 вперёд. Таким образом, получается порядка 10^8 операций, можно попробовать попихать на плюсах.

Теперь моё решение, которое является основным решением жюри:

Будем идти по коридорам сверху вниз. Для каждого коридора поддерживаем множество непересекающихся отрезков (intervals_i), у каждого отрезка есть следующие свойства: открытие (from) и закрытие (to) отрезка в этом коридоре и минимальное время начала полёта (start), такое, что мы можем попасть на отрезок к моменту его открытия. Также для восстановления ответа можно хранить предка (prev): из какого отрезка мы пришли в данный, либо null если мы начали путешествие из текущего отрезка.

Для первого коридора эти отрезки соответствуют интервалам времени, когда первый коридор открыт. Естественно мы учитываем, что выгодно всегда начинать полёт с какого-либо момента открытия коридора. Также заметим, что полученные отрезки у нас отсортированы по времени их открытия.

Рассмотрим теперь i-й (i > 1) коридор. Мы можем либо начать полёт с этого коридора (опять же, как и в случае с первым коридором, нам выгодно начинать с момента, когда этот коридор открывается), либо перейти в этот коридор с коридора с номером i - 1. Найдём curStarts   —  все моменты времени, когда мы можем оказаться в данном коридоре (то есть начать полёт с него либо перейти в него). Для того чтобы найти все времена перехода, посмотрим на все возможные пары {отрезок для коридора i - 1, открытый промежуток времени для коридора i} и выберем для каждой пары такой минимальный момент времени (его может и не быть), что мы можем перейти с i - 1-о коридора в i-й (опять же, выбирать минимальный момент времени всегда выгодно). Теперь можно построить на основе curStarts отрезки для i-о коридора, а затем жадно смерджить их следующим образом: если a и b соприкасаются, a.from < b.from и a.start < b.start, то присоединим отрезок b к a   —  a.to = b.to. Затем, если в каком-то из отрезков мы можем закончить полёт (interval.to - interval.start >  = t), то пытаемся обновить результат значением start данного отрезка.

Время работы. На каждом коридоре у нас может добавиться максимум c_i отрезков, соответственно максимальное количество отрезков на коридоре равно . Также переход от одного коридора к другому можно делать с помощью двух указателей, поддерживая отсортированность отрезков по времени открытия from. Итого получаем асимптотику .

Код: pastebin.

Что подразумевается под онлайн турниром? Онсайт был четвертого апреля и только с русскими условиями.

dp[i][a][b] — the best result for i processed indices, a of them are chosen for the first player, b of them — for the second player.

There is also a flow solution but DP is much easier.

Sorry for my bad English.

C) Main idea: go from up halls to downs and for each hall keep set of disjoint intervals. Interval is a structure with following parameters:

• hall — hall number
• from — first moment such that we can come in interval
• to — last moment such that we can leave interval
• start — start of the flight such that we can come in interval in moment from
• prev — prev interval on hall with number hall - 1 or null if we start from hall with number hall

For each hall we can construct its intervals using intevals of previous hall (it is case when we come from up hall) and open segments of current hall (case when we start from that hall). After building intervals for current hall we have to merge them greedily. All that can be done in O(numberOfIntervals) operations if we keep intervals sorted by from and use two pointers. Maximum available value of numberOfIntervals is less or equal than , so we can process all halls with total asymptotic . Further we can find best interval. It is interval with minimal start such that to - start ≥ t. After we just need to restore the answer.

Source: pastebin.

D) I’ll just leave this here: part 5 in article.

E) Just find cutpoints and biconnected components and construct tree of biconnected components. After that we can use dfs on that tree to calculate for each cutpoint sizes of children components and size of parents components. English, Russian. It can be done in O(m) operations.

Source: pastebin.

H) It will be written later by me or elena.

J) In first calculate maxGame  –  prefix maximum of queries(lengths of games) and sort gamers by t. After that come from the last game to the first and for game number i will be add gamers with t ≥ maxGame[i] in DSU. Answer for game number i: g[i] * size(0), where size(0) — size of set, which contains knight. It also can be solved by BFS and TreeSet. Asymptotic: O(m·α(n)).

Source: DSU, BFS.

some write ups in rev 1.

Your submission is not available for all.

And why will we use straightforward approach small amount of times?