Probably the easiest way to solve the problem is greedy. Sort people from the first line by increasing of their stamina. Give them tickets in this order, each time using the place which is furthest away from the other line. After that try to assign people from the second line to the remaining seats by sorting people by stamina and seats by the distance.

The time complexity of your solution must not exceed O((nm)²), however using std::set one can get a solution with complexity of O(nm log(nm)).

Let us divide the graph to biconnected blocks. Each block is either a bridge, or a cycle. Our goal is to remove one edge from each cycle, so that the number of remaining colors were maximum possible.

Let us build a bipartite graph, one part would be blocks, another one would be colors. For each block put an edge of capacity 1 for each color of an edge in this block (make multiple edges, or bigger capacity if there are several edges of some color). Add two vertices: source and sink, add edges from source to blocks, if the block is a cycle of length l, set its capacity to l - 1, if it is a bridge, set its capacity to 1. Add edges from color vertices to the sink of capacity 1.

It is quite clear that size of the maximum flow in this graph is indeed the answer to the problem.

As a final note, the judges know the solution that runs in O(n) and requires no maximum flow algorithms, challenge yourself to come up with it!

The solution is constructive.

• First let us use backtracking to find solutions for all n, m < 5, it is also better to precalculate all answers, in order not to mess with non-asymptotic optimizations.
• Now m ≥ 5.
• Let us put asterisks from left to right, one row after another. When adding the new asterisk, we add 4 new L-trominoes, except the first asterisk in a row that adds 1 new L-tromino, and the last asterisk in a row adds 3 new L-trominoes. Let us stop when the number of remaining L-trominoes k is less than 4, or there are less than 5 free squares in the table.
• Now there are two cases
  • there is a free row
  • thee is no free row
• If there is a free row, we stopped because k is now less then 4. So:
  • k = 0: the solution is found
  • k = 1: if there are already at least 2 asterisks in the current row, put the asterisk in the beginning of the next row, if there is only 1, put it in the end of the current row
  • k = 2, k = 3 — similar, left as an exercise.
• If there are now free rows left, one can see that you can only add k from the set {0, 1, 2, 3, 4, 5, 6, 8, 9, 12, 15} L-trominoes.
• And finally there is also the special case where the size of the board is 3 × m, m ≥ 5 and k = 2 * (m - 1) - 8 — in this case the first column should be left empty, and the rest of the board must be completely filled with asterisks.

First let us consider all paths from the starting square to the finish one. Let us say that two paths are equivalent, if each obstacle is at the same side for both paths. For each class of equivalence let us choose the representative path — the one that tries to go as low as possible, lexicographically minimum.

Let us use dynamic programming. For each square let us count the number of representative paths that go from the starting square to this one. When the obstacle starts, some paths can now separate. The new representatives will pass this obstacle from above (it will be to the right of them). So we add the sum of values for squares below it, but above any other lower obstacle, to the value for the square right above the obstacle.

To overcome the time and memory limits that the naive solution with O(nm) memory and O(nm²) time complexity, we use segment tree for range sum queries with mass update, running scanline and events "start of an obstacle", "end of an obstacle". This leads to the solution with O(m) memory and O(n log m) time complexity.

First let us consider a slow solution. Let us find a condition for each number k after what number of seconds Borya can distinguish it from the given number. Let us look at their initial encoding. Increase both numbers by 1 until the encodings are different (or one of the numbers needs more than n digits to represent in which case the beep allows Borya to distinguish the numbers as well).

Now there are two main ideas that allow us to get a better solution. First, we don't have to check all numbers. We only need to check numbers that differ from the given number in exactly one digit.

Second: to get the time when the numbers can be distinguished we don't need to iterate over all possible values. We just need to try all digit positions and all values for that position, and check only moments when the digit at the position will first have this value in one of the numbers.

So the complexity is now polynomial in n and since n ≤ 18, it easily fits into the time limit.

We give the outline of the solution, leaving technical details as an excercise.

First note that the answer will always use min(k - n, 0) subarrays with maximal sums. Sof let us find the sum of min(k - n, 0) maximal subarrays, elements that are used in them, and the following min(k, n) subarrays. We can do it using binary search for the border sum, and a data structure similar to Fenwick tree. For the given value of the sum this tree must provide the number of subarrays with greater or equal sum, sum of their sums, and the set of the elements of these subarrays. It should also allow to list all these subarrays in linear time complexity. This part has time complexity O(n log² n).

Let us now describe how to solve the problem in O(n² log n). Let us try all values of x — the number of subarrays with maximum sums that we will use in our solution (there are O(n) variants, because top min(k - n, 0) subarrays will definitely be used). Let elements with indices i₁, ..., i_m be the ones that are not used in these subarrays. Now we must add k - x segments that would contain all of these elements. Note that each of these k - x segments must contain at least one of these elements, and no two segments can have a common element among them (in the other case the solution is not optimal). These observations let us greedily choose these k - x segments in O(n log n) and the final solution complexity is O(n² log n)

To optimize this solution, we keep segments [i_j + 1; i_j + 1 - 1] in the ordered set. When we iterate over x and increase its value, we remove some of the i_j-s, and recalculate the required values for the affected segments. After that we must take k - x maximal values from the set, so since there are O(n) changes in total, this part now works in O(n log n).

To solve this problem, notice that the sides of the Elijah's rectangle don't matter, only the area is considered. So he can use any number of squares to create a rectangle of size C × nC for any positive integer n.

The optimal n is the result of the division AB / C² rounded either up or down. So we just check two variants and choose the better one. Additionally, it is important to remember that n > 0, so sometimes it is impossible to round down.

First notice, that we can make inversions only in one string. Also notice that the order of inversions doesn't matter.

So the solution is greedy: consider characters of the first string from left to right. If the corresponding character s₁[i] ≠ s₂[i], we inverse characters i, i + 1 of the first string. In the end check that s₁[n] = s₂[n], if it's not, there is no solution, in the other case we have found the only, and therefore optimal, solution.

The solution is using special construction.

First, let us show how to create the track with maximal possible k. Starting with the horizontal segment, each vertical segment would cross all previous horizontal segments except the adjacent one. The example with 14 segments is shown in the picture.

To get exactly k segments first draw 2l segments such that l(l - 1) / 2 ≥ k > (l - 1)(l - 2) / 2, make a small track with k intersections. To do so, start creating the maximal example, but terminate the last segment after required number of intersections. The remaining n - 2l segments can be added in the beginning of the track to form the spiral around the smaller track. See picture below for example, where n = 17 and k = 9.

The constraint on k is really the maximal bound on the number of intersections of n segments. We omit the proof, but the hint is: look at the number of intersections of the pair of segments n and n - 1 with pairs n - 3 and n - 4, n - 5 and n - 6, ..., 2 and 1 (or only the segment 1, if n is even).

Let us add weights to tree edges, and set edge weight equal to 1 initially for all edges. Now instead of removing the vertex we would change the weight of the edge from it to its parent to 0. The distance between any pair of vertices would be equal to the distance that would be should we had actually removed the vertex.

We can solve the new problem as follows. For each vertex in the initial vertex find the distance from the root to the vertex, and put the distances to the array in DFS order. After changing some edge weight, we must change the distances in the continuous segment of the array. This can be implemented using, for example, range tree.

Now the distance between vertices can be found, using : d_ab = d_a + d_b - 2·d_lca, where lca — is the least common ancestor of a and b, d_v — is the distance from the root to v.

Notice that the angriness of all people in one connected component is equal to their initial angriness multiplied by some value, the same for all islands in this component.

Let us process edge removal in time proportional to the size of the smaller components that appears after its removal. In this case the time complexity of the algorithm would be . To prove the complexity notice that for each vertex when it is in the smaller component, the size of the component at least halves. So it can only happen times.

If removing the edge we could know which component is smaller, we could traverse it and move its vertices to a new component, leaving the vertices from the larger one in the old one. But we don't know which component is smaller. So let us run two BFS-s simultaneously in both components, and when one of them terminates, terminate the other one as well. This way the time for such BFS would be proportional to the size of the smaller component.