Yes, B, because I like dirty string problems xD . Moreover you should have not read the whole dirty sample, only edges of text chunks!

Guys, how to solve task H and J? It's interesting tasks, but very hard for me. I think, J is very strange

So which other tasks did you find tedious?

Here's our approach to B: for each length-10 substring of text, we remember the list of lines where it appears, but only until we find 10 appearances — if we find more, we discard that string. Now we find all length-10 substrings of pages, and find which offset has the most matches. Only a few lines of code.

First observation: if you can turn on x[n-1], then the answer is: 3*(x[n-1] — x[0]). If you believe so, then the solution is very easy. First check, if you can go from x[0] to x[n-1], just turning on light. Second check, suppose all the lights are on, now, you are at x[0], can you turn it off and still go to x[1]? Likewise, for i = 0 to n — 2, can you turn off x[i] and still go to x[i+1]? If so, it is solvable. You can use map/set to check whether you can turn of x[i] and still go to x[i+1].

The main idea is to generate grey table with white rectangle [i, n] × [1, i]. Given table satisfies this condition for i = 1. Then you can increase i by one in the following way. Using black pair you can generate tables which look like follows

...B
WWW.
WWW.
WWW.

Then using column swapper you can get

.B..
W.WW
W.WW.
W.WW

Add initial rectangle

WWW.
WWW.
WWW.
WWW.

to all these shifts and you got

....
WWWW
WWWW
WWWW

Eventually you will get 1 × (n) white rectangle and applying this approach to it you will obtain grey table.

The following picture represents our algorithm:

Numbers under tables aren't actual numbers which were used to produce output since somewhere we added a table which is got from the 0th table by swapping rows and columns and contains two black squares sharing a vertical side, hence creating such tables changed the numeration. These numbers under tables are only for better explanation of some additions.

UPD: here is the link to the picture if someone needs a better quality.

Посчитаем cnt[i] — количество i-ых единичных битов в числаx Ai.
Посчитаем sb[i] — i бит в S.

Сумма всех чисел это сумма по cnt[i]*(1<<i).

Заметим что мы можем заменить в сумме cnt[i]*(1<<i) на (n-cnt[i])*(1<<i) поставив в ответе на i позицию 1.

Пусть dp[i][j][q] — миним. бит в ответе на i-2 позиции что на i-1 позиции стоит q и сколько перенеслось из меньших разрядов единичек(остаток)

перехода всего 2:
1. Ставим0наiпозицию.Если (j+cnt[i])%2=bs[i] то перейдём в dp[i+1][(j+cnt[i])/2][0]
2. Ставим1наiпозицию.Если (j+(n-cnt[i]))%2=bs[i] то перейдём в dp[i+1][(j+n-cnt[i])/2][0]

размеры дп: первый параметр это максимум 60. второй параметр может максимум быть n+n/2+n/4+n/8... < n+n

не очень красивый и не оптимальный по памяти код

I think ours was O(2^m * n).

Mine 2^m n * const got TL at onsite competition. I needed to precalc everything. :(

I don't know what's wrong with your solution, so I'll just describe our approach here.

There're two major cases:

1. There are at least two points on one of the four lines. In this case, we can fix these two points and binary search over the answer. For a fixed width, we can ignore all points that are inside the strip formed by the fixed line and the line parallel to it. We need to check that all other points are in some orthogonal strip. It's the case iff the difference between the smallest and the largest projection is no more than the width of the strip.

2. Otherwise there should be at least one point on each line. Let's iterate over all ordered tuples of 4 different points and build a cross going through them (the cross is uniquely defined by these 4 points: we can write down a linear equation in the sine of the angle between one line of the cross and the x-axis. It's not the case if there're collinear or form a square, but these cases can be ignored).

There are no other cases as we can rotate/squeeze any configuration without increasing the width of the strips until it becomes one of the two described above.

This solution is O(n^5), which might seem a little bit too much, but it gets accepted with a couple of hacks.

I think your solution is identical to ours but we had EPS issues, with 10^- 7 we got WA but with 10^- 8 we got AC.

Just to confirm that your solution is identical to ours — we binary search on the size of the cross (call this s). We iterate over every pair of points. We find the two pairs of lines that have distance s from each other going through these lines (otherwise we just use the lines perpendicular to the segment), then we project all points onto these line and check if we could form a cross of size s.

Our solution is therefore O(N³).

Задача сводится к нахождению такого множества стражей, что для любого j из этого множества выполняется a_j + b_j ≤ sum(a_i) for all i.

Если переписать это как max(a_j + b_j) for j ≤ sum(a_i) for i, то можно воспользоваться следующей жадной идеей: отсортировать по возрастанию суммы, а затем перебирать максимальную сумму пары для ответа)

Если зафиксировать пару с индексом j как максимум для множества, то на префиксе [0..j - 1] необходимо набрать сумму a_k, превышающую b_j. (т.к sum(a_k) + a_j ≥ a_j + b_j, при этом a_j + b_j ≥ a_k + b_k для всех k на [0..j - 1]). Для минимизации ответа логично выбирать максимальные a на префиксе. А чтобы получить количество, можно применить декартово дерево :)

Код: https://pastebin.com/KjYU5jms