Many contestants started with this problem but didn't succeed because it is not that simple as it looks at first glance. It's actually the 9th problem in the contest if we sort them by difficulty.

I'll call the total balance the sum of 1 for every opening bracket and -1 for every closing bracket, and the minimum balance — the minimum of total balances of every prefix (minimal balance cannot be positive).

Naive sorting by total balance or minimum balance doesn't work here, and I leave it to you to construct cases where it's wrong. It was quite interesting to come up with such cases.

Divide the bracket sequences by two groups — with the positive total balance and with the negative total balance (the sequences with the zero total balance may be attached to any of these two). These two groups are symmetric, so consider only one of them — to deal with the other one you may just reverse the sequences and apply the same thoughts. So, we have a group of bracket sequences, all of which have non-negative total balance. How to order them properly? It is now obvious that they should be sorted by minimum balance, started from the minimum balance 0, so that the first sequences don't ruin everything.

Find the occurences of "happiness". If there is only one occurence, swap two letters in this occurence, e.g. 'h' and 'a'. If there are two, swap 'h' from the first occurence and 'a' from the second occurence. If there are more than two, it's clearly impossible.

The most funny things happen when there are no occurences. You still have to swap two characters and you may accidently get "happiness" after your swap and get WA 29 / WA 64 / WA something else. The most simple way is to swap random characters and then check if everything is fine, until the answer is found.

This is not my problem and it can be solved by several "if"-s, but for me this approach was hard to understand, so I solved it by binary search. If you solve it with "if"-s, beware of integer overflow.

Say, we are taking m balls from the urn. What now? The maximal number of balls of red balls we could have taken is min(m, a + c), and the maximal number of greed balls is min(m, b + c). If the first of these numbers doesn't exceed n, and the second doesn't exceed m, it's ok and we can consider greater values of m in the binary search.

The minimal distance of jump is gcd(a[0], ..., a[n-1]). Why is that? Let's see what happens if we have only two numbers. Then, to jump to some distance z, you should perform x jumps to a[0] and y jumps to a[1]. The equation x * a[0] + y * a[1] == z has integer solutions (x, y) when z is divisible by gcd(a[0], a[1]). Apply the same logic further, we get gcd(a[0], ..., a[n-1]) as the minimal possible length of jump. Check if the desired distance is divisible by this gcd.

How to collect all bonuses between two teleports? There are several ways:

1. to go through the whole segment between these teleports
2. to start from the left teleport, go right, collect all bonuses and return to the left teleport
3. to start from the right teleport, go left, collect all bonuses and return to the right teleport
4. combined (2) and (3), iterate over bonuses, fix the last bonus to collect from the left teleport (the next one will be collected from the right teleport)

Be careful with the bonuses to the left of the leftmost teleport and to the right of the rightmost teleport.

It is a problem from Cormen's book — don't ignore it, read it and try to solve the tasks :)

We should find an operative circuit somehow, and then test it together with all other circuits.

Let's check circuit 0 vs circuit 1, 2 vs 3, and so on. Looking at the result, we will take at most one circuit to process further, such that the invariant "the number of operational circuits is more than the half of the total curcuits count" still will be true.

What the results of checks can be?

• "- -" — throw them away. Either both of them are defective, and nothing bad happens if we exclude both, or one of the is operational and the other one is defective, but if we exclude both, the invariant will still take place.
• "+ +" — both of them are operational or both of them are defective. Again, take exactly one of them, and the invariant still holds.
• "+ -" — either both of them are defective or the one which said "-" is operational. We will take the one who said "-". As the invariant is true now, the number of operational circuits which said "-" in "+ -" is greater than the number of defective circuits which said "-" in "+ -".

If the number of curcuits is odd, check the remaining one with all others. If more than half of the others said the last is defective, it is defective, otherwise it is operatonal.

Continue this algorithm until only one circuit remains.

Simply iterate from the end. At each step you have the current index of a person, if necessary (a[i] == current index), replace this index with the new index (b[i]) and increase the count of "I_love_" by 1. Don't store the full names — you will get ML. Just a single integer — the number of "I_love_" prefixes.

Find the maximum element in the matrix. There are two ways to ban it — to ban a row or a column. Try both and choose the best way. If you ban a row first, find the maximal element in the remaining matrix and ban the column of this maximal element. If you ban a column first — ban the row of the maximal element in the remaining matrix.

A very simple solution which is very hard to come up with if you don't understand how linear algebra works.

Choose a random vector x and check if A*B*x == C*x. You should now perform 3 matrix x vector multiplications that will fit in time limit.

Let's call a "sun with long rays" the graph with the following structure:

• 1-2-3-...-k
• 1-(k+1)-(k+2)-...-(k+l)
• 1-(k+l+1)-(k+l+2)-...-(k+l+m)
• ...

That is, there is a vertex 1 which is a center of a sun and rays 1-2-3-...-k, 1-(k+1)-(k+2)-...-(k+l), 1-(k+l+1)-(k+l+2)-...-(k+l+m) and so on.

If the graph has this structure, how to catch the monster? The first person should stay at the center, and the other person should check the rays one by one.

The answer to the problem is "YES" if and only if the graph is a line tree, where some vertices, possibly, are replaced by suns with long rays. Two people check suns one by one using the algorithm described above. Checking it is not hard comparing to get it, so I'll skip it.

Compress coordinates, then iterate through moments of time and do simple forward DP, updating the best possible usefulness and time. From some moment of time you may go to the next moment, doing nothing. Additionally, if there is a contest at the current moment of time, you may go to the end of this contest, gaining usefulness and spending time. There are only n transitions corresponding to contests and n transitions corresponding to doing nothing.

If there are two spells such that L1 <= R1 <= L2 <= R2, the second one is always better, and the first can be easily thrown away.

So, the only useful spells have L1 < L2 < ... Lk <= Rk < ... < R2 < R1, and they form something similar to convex hull. While processing the convex hull algorithm, you have the spell at the back of stack [backL, backR] and the current spell [curL, curR]. To find if the back spell should be popped from the stack, find the point X where the spell [curL, curR] has the same probability as the spell [backL, backR]. If X < backR, starting from X == backR, the spell [curL, curR] becomes better, and it should be added to the stack.

Trying to solve this problem in doubles can cause WAs. Integer solution exists, and you should always write integer solutions in this kind of problems.

If the sum of numbers doesn't equal to n-1, answer is NO. Don't try to calculate this sum in int type as you will get overflow and WA.

Then perform simple emulation: starting with the person with the lowest positive number of frags, write its frag on any person without frags, and decrease the number of frags of the killer by 1.