This is unofficial editoral without proofs, sorry for grammar mistakes.
The Battle of Giants
If $$$a$$$ $$$mod$$$ $$$3 \neq b$$$ $$$mod$$$ $$$3$$$ answer is -1. Otherwise answer is $$$a/3$$$,$$$a$$$ $$$mod$$$ $$$3$$$, $$$b/3$$$.
Tetris Remastered
Lets find maximum element in the array, and change every element to its difference with maxmum. Now greedy approach works. We should go through array from left to right and keep integer $$$u$$$ — height of current fill If ($$$a_i > u$$$), we increase $$$u$$$, answer with $$$a_i-u$$$, otherwise, decrease $$$u$$$ to make $$$u = a_i$$$, and dont add anything to asnwer.
Optimal Truck
Important fact in the begining. If we can achieve nedded benefit using $$$x$$$, we can do so using $$$x+1$$$.
We can sort all contracts with condition $$$w_i < w_{i+1}$$$ and $$$c_i < c_{i+1}$$$(we can delete contracts wich are less expensive and more demanding then other).
Now we can binary search the answer. First, lets learn how to do it in $$$O(n \log n)$$$. To do so, we check every customer`s sorted list, and take the most expensive contract we can afford with current capacity.
To get full score, I created list of additional benefit we get after taking next contact (more demanding one). When we create such lists for every customer, we can merge them in one!. Now we need only one binary search and complexity is $$$O(q \log^2 n)$$$. It`s useful to use prefix sums for realisation.
Bookshelf Sorting
Lets solve task for fixed permutation. We should find longest subsequence of form $$$l, l+1, l+2, ... r - 1, r$$$. I claim, that answer is $$$n - (r-l+1)$$$. Prove sufficiencyis easy — we just take other elements to the beggining, or to the end. However, I dont remember necessity prove, but it sounds obvious.
How to find this subsequence? We can build inverse permurtation and find longest increasing subarray there. It`s easy to see, this subarray is our subsequence. To get 75 points we can search this array naive way. Full score is a bit harder.
Let`s build segment tree, in every vertex we store answer(length of biggest increasing subarray), length of biggest increasing prefix and same value for suffix. And some more useful thigs(leftest element, etc). Merging two nodes is easy. Answer can be in the left child, right child, or, if possible, we merge suffix of left child and prefix of right one.
Now every swap is two change operations on this segment tree, and answer is stored in it`s root.
Nice Shape
Its ovious, that answer wont exceed 4.
If answer is less then 4, we can leave 2 rook untouched.
Let`s check, how much moves do we need to create a rectangle from each pair of rooks. We can determine rectangle by two coners. . We need to move two rooks to the positions of the other two vertices.If there is a rook that is already in place, then there is no point in moving it. If there is a rook in the same row or column with the desired position, then one move is enough for us.
This soulution can get up to 60 points. ($$$O(n^2)$$$).
To get more, we need to check if there is a rectangle formed by points(answer is 0 in that case). I have used quite hard $$$O(n \sqrt n)$$$ algo. Wepartition all points in groups with same x-coord. froups with size less than $$$\sqrt n$$$ we call small, other — large. To check if answer is present only in small ggroups, we leave only points from small groups, and repartition them by y-coord. Now we create array $$$a$$$, filled by zeros. Each entry in this array corresponds to one x coord. Lets check, does there exist a rectangle with border $$$y_c$$$. We traverse through all points with such y-coord. Assume we are checking point $$$(x_c, y_c)$$$. For all points $$$(x_c, v), v > y_c$$$ we add $$$a_v=a_v+1$$$. If $$$a_v=2$$$, we have found rectangle, bounded by sides $$$v$$$ and $$$y_c$$$. There are no more then n points in union of all small sets, each time we increment no more then $$$\sqrt n$$$ array entries (by defenition of amll sets). $$$O(n \sqrt n)$$$.
To check, weather answer is in large and small froup we do the following. Lets consider each small group S. We create counters for each large group, initialy zero. for each point $$$(p, q)$$$ in $$$S$$$, we check all large groups, that contain point with second coord $$$q$$$ and add 1 to their counters. If we get 2 on any counter, we get an anwer. Each time we change no more then $$$ \sqrt n$$$ large groups. $$$O( n \sqrt n)$$$.
What should we do with large groups? I claim, if we swap coordinates, repeat process described above, we will found answer, if it was among big groups. Big groups made by x -partition will be small by y partition.
Other cases are much easier. If answer is 1, we need look for a "corner" and a point on the same line with its place (two parallel lines on which there is at least one common y coordinate).
Answer is 2 only if we have two gorizontal ot vertical lines with at least two rooks on them.
Answer is 3 only if all points are NOT on the same line, and there exist a vertical or horizontal line with at least two rooks on it.
Otherwise, answer is 4.
