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:
- Building it as a string with
+
- 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 !