Problem I. Toys.

In this problem we need to output all partitions of the given set into subsets in the order which is very similar to the Gray code. Lets denote each partition by a restricted growth string. For a restricted growth string a₁a₂a_n holds that a₁ = 0 and a_j + 1 ≤ 1 + max(a₁, ..., a_j) for 1 ≤ j < n. Every partition can be encoded with such string using the following idea: a_i = a_j if and only if elements i and j belong to the same subset in the partition. For example, string representation of the partition {1,3},{2},{4} is 0102.

Now we will learn how to generate all restricted growth strings by making a change in exactly one position in the current string to get the next string. It is obvious that in terms of partitions it is what we are asked for in the problem. Rather easy way to build such list of strings was invented by Gideon Ehrlich. Imagine that we have the required list s₁, s₂, ..., s_k for the length n - 1, We will obtain a list for the length n from it. Lets s_i = a₁a₂... a_n - 1, and m = 1 + max(a₁, ..., a_n - 1). Then, if i is odd, we will obtain strings of the length n by appending digits 0, m, m - 1, ..., 1 to s_i, otherwise we will append digits in order 1, ..., m - 1, m, 0. Thus, starting from the list 0 for n = 1 we will consequently get lists 00, 01 for n = 2 and 000, 001, 011, 012, 010 for n = 3. Ehrlich scheme is decribed in Knuth's "The art of programming", volume 4, fascicle 3, pages 83-84.

Problem G. Shooting Gallery.

Lets solve slightly different problem: for every target we will determine the shoot that hits it. Sort the targets in increasing order of their z-coordinate and process them in that order. Each target is processed as follows. Consider all shoots that potentially can hit it. It is obvious that all such shoots belong to the rectangle, corresponding to the target. From these shoots, the earliest shoot will hit the target. We should find this shoot and remove it from the set of shoots, and then turn to the next target. It's easy to see that the following condition will be held: before we process a target, all shoots that were going to hit it but faced other targer, were already removed from the set of shoots.

Now we need to implement the algorithm efficiently. We will store the shoots in some data structure. This structure should be able to answer two types of queries:

In my solution I used two-dimensional index tree to manage these queries. I won't describe what the two-dimensional index tree is. I just want to make several remarks. First, the removing operation is not as easy to implement in a two-dimensional index tree as it mays seem. But we are lucky that we have no additions, just deletions! Time complexity of the model solution is O((N + M)log²N.

Problem F. BerPaint.

Imagine that all segments were drawn. We will refer to these segments as to initial segments. Lets divide the rectangle of drawing into the set of regions and segments such that there are no points of the initial segments strictly inside any region, and new segments separate the regions. Note that new set of segments can contain not only the parts of the initial segments, but also some dummy segments. Initially the color of all regions is white, while the color of each segment can be black of white (dummy segments are white). Please note that in such a partition the border of the region is not consider to belong to it. Lets build a graph where each vertice corresponds either to a region or to a segment, and add edges according to the following rules:

It is clear that every region that can be filled corresponds to some connected component of this graph. That gives us a solution. We will store a color for each vertice. When processing a filling operation, we search for all such vertices that the objects that correspond to these vertices contain the chosen point. For region, the point should lie strictly inside the region. For the dummy segment, the point should lie on it but should not coincide with it end-points. And for the non-dummy segment, the point should just lie on it. From each of the found vertices, we make a DFS or BFS which finds all vertices that are reachable from the statring vertice and have the same color, and paints them with new color. After all operations, we need to find sum of areas for such colors, that there are at least one vertice with this color.

The main difficulty in the problem is to divide the rectangle into regions and segments. In my solution it is done using vertical decomposition. First, divide the rectangle into vertical stripes such that inner area of any stripe doesn't contain neiher end-points of the initial segments nor points of their intersections. Then each of these stripes is divided into trapezoid by initial segments, intersecting the stripe. Then add necessary dummy segments to separate the regions and build the graph. I think that there may be some easier ways to construct such graph.