Clearly this contests was too hard and I am sorry about that. Nevertheless, I will show you in this editorial that actually these problems are not so very hard and are closely related to some problems already here.

Problem A: Ad-hoc, Lists

This problem clearly is a list problem similar to Broken Editor and Broken Keyboard

The reverse operation cannot be implemented by literally reversing the list as this costs \(O(n)\) per rotate operation thus leading to a \(O(n^2)\) algorithm.

Instead just keep the list elements in an array with. We keep a pointer for the leftmost element and another for the rightmost one. Also, keep a boolean flag saying whether the list is rotated. Whenever we delete an element if the list it not rotated we increase the leftmost pointer. Otherwise we decrease the rightmost one.

The rotation operation simply consists in flipping the flag in \(O(1)\).

Make sure to test your code in corner cases like an empty input list and a list with a single element. Also, make sure to print it in the right order in the end depending on the flag.

You need to be careful with the output. It is quite large avoid:

1. Building it as a string with +
2. Making a lot of System.out.print calls

Instead use a StringBuilder to build it and a single call to System.out.println

Problem B: Classic DP

This is a classic dynamic programming problem. Just sort the people by increasing income and compute the longest decreasing subsequence with respect to the happiness. Don't forget to ensure that when you compute your sequence you only consider elements with strictly lower income and strictly higher happiness.

After sorting the DP recurrence is the following:

Problem C: Brute-force on solution structure + BFS

This is not a flow problem as some people might think. It is a brute force on solution structure similar to Pickup and Delivery and Iron and Coal

If you think about the solution, it will be a path from the outside to some node \(v\) (which can be either a cell of the outside node) and then one path from each prisoner to \(v\). For a given \(v\) is it easy to compute the cost of that solution. It is simply

Thus we can just perform a BFS from P1, P2 and outside and compute the best \(v\).

Problem D: Geometry

With this type of problem it is always easier to normalize the input. We can do that in the same way you solved (or should have solved) Align Polygon.

In this case we normalize so that the first edge is the segment between \((0, 0)\) and \((x, 0)\) for some \(x\) and the camera is at \(C = (x / 2, 0)\).

Then we simply compute the lines \(l_1 = line(C, C + (1, 1))\) and \(l_2 = line(C, C + (-1, 1))\). We intersect these lines with the edges of the polygon and compute the area of the polygon with vertices

where \(v_1, \ldots, v_k\) are the vertices of the original polygon between \(inter_1\) and \(inter_2\).

Problem E: Binary search on the answer

This is a simple binary search on the answer problem. Similar to Plane purchase problem and Glyph Recognition

So imagine that the problem is instead: given a time \(t\), can they move apart in time t? If you think about it you will see that it is easy to solve when \(t\) is given.

Hint: The leftmost food truck will walk left \(t\) units in the optimal solution.

Questions?

Use the slack !