dp[type][n][k1][k2] — type is either 0 (segment hasn't started), 1 (segment is open now) or 2 (segment has already closed). k1 — number of elements that we swapped in the segment, k2 — number of elements that we swapped out of the segment.

answer is in dp[1][n][i][i] or dp[2][n][i][i]

The same complexity we have accepted in upsolving. We got TL31 when doing k⁴ instead of k³.

Our solution on 1:

Let us have an arbitrary segment [l, r] and two sets (multisets, but then we add to every number an index of it in order to recover necessary swaps for answer) of numbers on [l, r] segment: one set is for numbers inside the segment, one is for the outside numbers. Then we can easily get a sum with swaps on [l, r]: using prefix-sums (or whatever to get an actual sum) on a [l, r], then simultaneously iterate over k biggest numbers (from biggest to lowest) in outside and smallest in inside (from smallest to biggest) sets, and change our computed sum according to these values (will the sum get bigger, if we swap those values?).

The solution is just to move two pointers over an array, while sustaining two sets accordingly and update answer if necessary.

Does anyone know what is wrong with this approach? We've got WA8 or something with that.

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

Работает такое решение: сортируем по X, вычитаем из каждого X его индекс в отсортированной последовательности и находим медианы по X и Y. (И аналогично поменяв местами координаты)

Смотря как выравниваешь. Рассмотрим стартовую точку на линии, пусть это будет L. Тогда все кубики будут располагаться от L до L + n — 1. Будем жадно двигать, то есть, самый первый кубик в L, второй в L + 1, i-тый в (L + i — 1). Несложно заметить, что при таком поставлении, L будет равна медиане среди a[i] — i + 1.

It's not true, that angle speed is equal all time. You losses part of speed v to go along line.

Can you please explain a little bit more?

5) Сгруппируем строки из словаря по равенству без учета регистра. Для каждой строки из ввода заведём битовый массив: 1 -- верхний регистр, 0 -- нижний. Количество различных бит можно посчитать с помощью ксора и __builtin_popcount. Получается O(n·q·L / 64). Работает полсекунды.

6) Посчитаем количество чисел во вводе с каждым остатком от деления на семь. Дальше переберем число a_i, которое будет представлять младшие разряды и все остатки. Прибавим к ответу количество чисел a_j для которых справедливо . Не забудем что нельзя выбирать пару из одного и того же числа.

10) Let's try to make a horizontal line (vertical one can be done similarly). Suppose, we will make a line at y = Y. Then we know the total amount of movements to bring all the points to y = Y (which is sum of |Y — yi|). Movement of x is independent of y movement. So we can minimize x/y independently. To minimize sum of |Y — yi| we should choose median(yi).

Now, let's calculate movement of x. Sort all x. It is okay to say that, x0 will be leftmost, then x1, then x2 ... Say xi moves to x = i. Then signed movement is: set(xi — i). Let, xm = median(set(xi — i)). Then, you have to move: xi to i — xm. Why? Can be proved, can't find are simpler argument now.

5) I got tle by suffix array. Later got ac using hashing+bitset. For each word, I converted the word to lower case and computed hash value (some simple polynomial hash). Also I kept a bitset consisting of 0 for lower case, 1 for upper case (AbaC = 1001) Then for each (word, query) I checked if they satisfy all the conditions (length equal, hash same, count of ON bits in xor of bitset <= K).

When I had WA2 these tests were useful:

2
0 0
0 0 2 0
1 1 3 1
answer
1 1
2 1 0 1 1

and 

5
0 0
0 0 0 1
0 1 0 2
0 2 2 2
0 1 10 1
5 3 5 5

answer
1 2
2 5 1 5 3

This input should help you:

16
3 2
3 1 3 -1
3 -1 5 -1
5 -1 5 1
5 1 8 1
8 1 8 4
8 4 7 4
7 4 7 3
7 3 6 3
6 3 6 7
6 7 3 7
3 7 3 5
3 5 5 5
5 5 5 6
5 6 4 6
1 -1 -1 -1
-1 -1 -1 3

First, print 0 200 times. Then denote the sum of last n - 1 elements (denote them by a₁, a₂, ..., a_n - 1) by S. We print 0 and get . Then we print a₁ + a₂ and get . Then we print a₃ + a₄ and get . When the new answer t_k + 1 is less than the previous one t_k we know that M = 2t_k - t_k + 1.

The only problem is when . In this case we print a₁ + a₂ ± 1 (plus or minus depends on if a₁ + a₂ equals 1e9 or doesn't) and continue in the same manner.

First 200 zeroes are needed in order to have a_2k - 1 + a_2k no more than 1e9.

Sorry, this was wrong.

Random solution is better =) Print 10 random numbers, then answer will be GCD({realSum_i - response_i})

First print 10^9. We will get r. (SumOfLast(n) - r) % m == 0, (SumOfLast(n) - r) > 0.

Assume that we know that m1: m1 % m == 0, m1 > 0.

Let's x = min(m1 - 1 - SumOfLast(n - 1) % m1, 10^9); r1 = SumOfLast(n - 1) % m1 + x.

Let's print x and get answer r. If r == r1, then m == m1.

Else if m1New = gcd(m1, r1 - r), then m1New % m == 0, m1New <= m1 / 2 and m1New > 0.

Let's m1 = m1New. Continue this, while m1 is decreasing.

At most 40 questions (first m1 < 10^11).

The round-trip doesn't have to pass through all the cities so it suffices just to find one cycle in a graph. This can be done by doing a DFS and keeping track of the current stack of vertexes.

If you cannot find a cycle then you can add a single edge to road with 2 vertexes. The possible answers can be -1, 0, 1, 2.