Div II A — Fancy Fence

Problem

The problem is to tell whether there exists a regular polygon with angle equal to a.

Solution

Consider all supplementary angles of the regular n-polygon with angle a, which are equal to . Their sum is equal to , because the polygon is convex. Then the following equality holds: n·(180 - a) = 360, which means that there is an answer if and only if .

Time: O(t).

Memory: O(1).

Implementation: C++, Java

Comments

The problem can be also solved by rotating vector (1, 0) by angle until it returns in this position (but at most 360 times), and checking that only one full turn has been made (implementation example: C++).

It is also a rare problem on Codeforces that contains just 1 sample test, 1 pretest and 1 full test.

Div II B — Multithreading

Problem

In this problem we are asked to find the number of n-permutation elements that definitely have been moved after performing any sequence of move-to-front element operations. Equally, we should find the maximum possible number of elements that could have not been moved.

Solution

If some a_i is greater than a_i + 1, it is clear that a_i definitely contains a new message because the order of these two elements has changed. Let the last such element be a_k. Then all of the elements a_k + 1, a_k + 2, ..., a_n can contain no new messages, since their order has not changed. The answer to the problem is n - k. If there is no such a_k the order hasn’t changed at all and there may be no new messages.

Time: O(n).

Memory: O(n) / O(1).

Implementation: C++, Java

Comments

The problem was born while staring at the Codeforces main page and trying to think up an easy Div II problem. =)

Div II C / Div I A — Magical Boxes

Problem

We are given a_i squares with side length 2^k_i. It is allowed to insert squares only inside larger ones, and no two squares should overlap. We must determine the minimum p so we can place all the given squares inside a square with side length 2^p.

Solution

Suppose we can put all the squares inside a square with side length 2^p. Then we can insert each k_i type squares independently along the grid as shown in the picture. No two squares will overlap, since 2^x divides 2^y, if x < y. That means that we can find the smallest square that can hold all the given squares with side length 2^k_i for each k_i separately. The answer will be the side length of the largest such square.

To be able to put a_i squares with side length 2^k_i inside a square with side length 2^s, the following should hold:

We can then find the minimum s:

In a special case, if we obtain s = k_i, s should be increased by 1.

Time: .

Memory: O(1).

Implementation: C++, Java

Comments

The problem can be also solved using binary search on p. However, we can see that each square with side length 2^k + 15 holds any number of squares with side length less than 2^k, since . So it is enough to find the first square that fits from range 2^{max{k} + 1} to 2^{max{k} + 15}.

Div II D / Div I B — Greenhouse Effect

Problem

There are n points on the line, each of type from 1 to m. We can freely divide the line into m - 1 intervals and replace some points so each point with type i is inside the i-th interval numbered 1 to m from left to right. We must find the minimum number of points to replace.

Solution

First, observe that the coordinates don’t matter: only the order of the points is important. Let there be some number of points we can replace to achieve the good arrangement. Then all the other points remain in their positions, so their values must be in increasing order from left to right. Then we must find the maximum number of points that can remain in their positions, which is the longest non-decreasing subsequence of types in the input. If it is of length l, the answer is n - l.

In this problem it was enough to implement a quadratic solution. We count dp[i][j] — the length of the longest non-decreasing subsequence on prefix [1;i], with element of type j being the last in subsequence. The transition is as follows:

For easy implementation, we can maintain only array dp[j], and skip the second case.

Time: O(n²) / .

Memory: O(n²) / O(n).

Implementation: C++

Comments

We had to solve this problem during the work on our project, the origin lies in arranging some rectangular table borders. Our original project dp implementation actually runs in O(nm).

Div II E / Div I C — Flawed Flow

Problem

In this problem we are given an undirected graph and its flow, and we must reconstruct the edge directions of this flow.

Solution

The key element to solving the task is the following observation: if we know all the incoming edges of a vertex, all the remaining edges must be outgoing. The source has no incoming edges, so we already know that all its edges are outgoing. For all other vertices except the sink the amount of incoming and outcoming flow is the same, and is equal to half of the sum of the flow along its incident edges. The algorithm then is to repeatedly direct all the flow from the vertices for which all the incoming edges are known. This can be done with a single BFS:

for all v from 2 to n-1
    f[v] := sum(flow(v,u))/2;
put source in queue
while queue is not empty
    v := pop(queue)
    for all edges (v, u)
        if (v, u) is not directed yet
            direct v -> u
            f[u] = f[u] - flow(v,u)
            if u not sink and f[u] = 0
                push(queue, u)

As the flow contains no cycles, we can sort the vertices topologically. Then we can be sure that, until all edge directions are known, we can put at least the first vertex with unknown edges in the queue, as all of its incoming edges will be from vertices with lower indices, but we took the first vertex with unknown edges.

Time: O(n + m)

Memory: O(n + m)

Implementation: C++, Java

Comments

The obvious "easy" solution is to run some maxflow algorithm and get the answer. However, such implementations failed on anti-maxflow pretest #6.

Div I D — Maximum Waterfall

Problem

We are given n horizontal segments on a plane, and 2 extra topmost and bottommost segments. These two segments are the source and the sink of the flow. A flow can pass from one segment to a lower segment, if their horizontal projections overlap and there is no other segment between them so their projections overlap. The value of the flow on such segment edge is equal to the length of the horizontal projection overlap. We must find the maximum possible value of the flow along a single segment path.

Solution

We will use a sweepline algorithm to solve this task. This horizontal sweepline runs from bottom to top, and holds the parts of the segments that are visible from the line this sweepline is currently at. Each part also holds the reference to its original segment. The sweepline itself is implemented with a binary search tree.

The events of the sweep are the segments. When a new segment is found, we want to find all the lower segments that we can direct the flow onto from this segment. These can be only the original segments of the parts currently in the sweepline whose projections overlap with this segment. Then we iterate over all such parts p (finding the first such part is an operation). How do we know that we can direct the flow onto p? Observe that if there is some segment that prevents this, there should be also a part q in the sweepline that also can be seen from the current segment. And since the projections of all three segments overlap, this part can only be directly to the left or to the right of p in the binary search tree. So we just check whether the original segments of the two parts next to p prevent the flow from the current segment to the original segment of p.

Afterwards, we remove all such parts from the sweepline, and insert a new part corresponding to the new segment. If the new segment only partially covered an existing part, we reinsert the remaining portion of that part. There are at most two such portions — one on each side of the segment. Thus each segment inserts at most 3 new parts and the size of the sweepline is O(n). Each part is handled just once before removal, so the total time of such operations is .

Once we know we can direct the flow through we can immediately update the maximum downwards flow of a:

When we reach the top, f_top will be the answer.

Time:

Memory: O(n)

Implementation: C++, Java

Comments

Another problem from our project. You can also first build a graph from the segments using the same sweepline and then find the path with the maximum flow in that graph. In the original problem you have to find this graph and there are no top and bottom segments.

Div I E — String Theory

Problem

In this problem we have an n × m rectange. Each unit midpoint is connected with a segment to some other midpoint not on the same side of the rectangle. We can change the order of the columns and rows, but the segments must remain attached to their midpoints. We should find such a rearrangement that no two segments intersect, or tell that there is no solution.

Solution

There are overall 6 types of segments that connect the sides:

1. left-top;
2. top-right;
3. right-bottom;
4. bottom-left;
5. left-right;
6. top-bottom;

If there are both left-right and top-bottom segments, there is no solution. Otherwise there remain only 5 types of segments. Without loss of generality suppose there are no left-right segments. Let’s take a closer look at what should the end picture of the rectangle be:

All left-top segments should be at the left top corner connecting positions (L,i) and (T,i), otherwise they surely would cross some other segment. Similarly must be positioned top-right, right-bottom, bottom-left segments. Finally, all top-bottom segments should be parallel. We also observe that the number of left-top segments must be equal to the number of right-bottom segments and the number of top-right segments should be equal to the number of bottom-right segments. Thus the important observation: the picture of the end arrangement is unique and can be determined from the input simply by counting the number of segments of each type.

Next we define a cycle to be the sequence of segments, where the second midpoint of some segment in the cycle is equal to the first midpoint in the next segment in the cycle. In the given example there are two such cycles (but the direction of each cycle actually matters):

Then we observe that the set of the cycles does not change with any permutation by the definition of the cycle. We can make a sketch of the solution: we should find the cycle sets in the given arrangement and in the end arrangement, and compare them for equality.

At this point we actually find all the cycles in both arrangements. There are only two types of cycles:

1. (left-top) (top-right) (right-bottom) (bottom-left);
2. other cycles.

We can easily check whether the sets of first type cycles match, since the length of such cycles is 4. If they match, we rearrange the columns and rows involved to match the end arrangement.

How to compare the remaining cycles. Consider a following example:

Let the difference in the number of left-top and left-bottom segments be i, and this number plus the number of top-bottom segments s. If we enumerate the midpoints as in the figure, we can see that each top midpoint k is connected to the bottom midpoint (top-right segments continue as corresponding left-bottom segments). Thus we can describe it as a permutation

Our cycles correspond to the cycles in this permutation, with top-right segment continuation to left-bottom segment corresponding to the case where permutation cycle element decreases. It is known that the number of such permutations is and their length is . So all these cycles have the same length. Denote the remaining segment types as some letters (in picture A, B, C). Then not only the length, but the strings describing the cycles are also the same, but can be shifted cyclically (here the direction of the cycles also is important). Besides, we know this string from the correct arrangement cycle. Thus we need to compare all the remaining given arrangement cycle strings to this string, considering cyclic shifts as invariant transformations. For each string this can be done in linear time, for example, using the Knuth-Morris-Pratt algorithm. When we find a cyclical shift for each cycle, we can position its relevant columns and rows according to the end arrangement.

Time: O(n + m).

Memory: O(n + m).

Implementation: C++, Java

Comments

This is a total killer task for coding. It took both of us around 5 hours to code the implementation. Congratulations again to kelvin, at the time of writing still the only one to solve the problem (and of course to anyone who will get this difficult problem accepted =) ).