June 2011 Contest Problem Editorials

CLONES (written by Ivan Mistreanu)

Let the number of variables be n. We will calculate the amount of functions in different possible intersection of our clones. There are a total of 2^2^n different n-ary Boolean functions. This is derived from the fact that there are 2^n different binary sequences of length n. We can set a certain function to have value 0 or 1 for each sequence. So we have 2^2^n possibilities to do so.

Now considering 0-preserving functions we have to set each such function a value of 0 for the sequence (0, …, 0). So we are left with one less sequence and there 2^(2^n-1) such functions. The same goes for 1-preserving function.

For the self-dual function we can see that setting the value f(a1, …, an) = b, forces us to set the value f(!a1, …, !an) = !b. So we have only half of the choices. That gives the amount of such functions to be 2^2^(n-1).

It can be shown that the affine function are those that can be represented in a form: f(x1, …, xn) = a0 + a1x1 + … + anxn, where ai = {0, 1}. We can choose each ai to be either 0 or 1. We have 2^(n+1) possibilities to do so. So there are 2^(n+1) affine function.

Using the same logic we can derive the cardinalities for any intersection of those clones. We can use the calculated cardinalities to count the number of functions in any set formed by those clones.

Now let’s consider the following sets: function belonging to none of those clones, functions that belong to Z only, that belong to P only, that belong to D only, that belong to A only, that belong to both and Z and P only, …, that belong to all of Z and P and D and A. There will be a total of 16 such sets. Those sets will be disjoint and their union will be the set of all Boolean functions. The cardinalities of those sets can be calculated using inclusion-exclusion principle using the cardinalities calculated before.

So now we parse the given expression and calculate of what sets it is formed and just sum the cardinalities of those sets. This can be easily done using the bitmask (as there are just 16 disjoint sets) and bitwise logical operations.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

RG_01 (written by Rahul Gulati)

The problem is of finding a path such that the weight of the edge with minimal weight, on the path, is maximized for all pairs of distinct vertices (u, v). Let us call such a path, a maximal path for (u, v). Let's first try to understand a simple and slower dynamic programming solution similar to that of Floyd-Warshall's All Pairs Shortest Paths. Let minimal[u][v][k] denote the minimal weight of an edge for a path that starts at node u, ends at node v, and the only intermediates are vertices 1, 2, ..., k where the nodes are numbered from 1. We set minimal[u][v][0] to the weight of the edge (u, v), if it exists, or otherwise we set it to 0. We can compute minimal[u][v][k + 1] given minimal[x][y][k], for all x, y in V, as follows:

Clearly, the maximal path either passes through vertex k + 1, or it does not. This allows us to write:

minimal[x][y][k + 1] = MAX(MIN(minimal[x][k + 1][k], minimal[k + 1][y][k]), minimal[x][y][k])

So we can use O(V ^ 3) time and O(V ^ 3) space to solve the problem, but clearly the constraints are much higher.

Let us look at a next approach: Let us maintain a disjoint set data structure to keep track of vertices which are in same/different components. We start with the heaviest weight edge, and process edges in order of decreasing weight. Each time we find an edge that connects two vertices u and v, with different components, we merge the two components and for each vertex x that is in the first component, and for each vertex y in the second component, we set the value of minimal[x][y] to the weight of the edge (u -> v). We do this since there will be always be an edge on a path connecting x and y such that the weight of this edge will be lesser than or equal to the weight of the edge (u -> v), and so we know that this strategy will result in an optimal solution. We can reduce this problem further by seeing that we are computing nothing but the maximum spanning tree of the graph. We can compute the maximum spanning tree of the graph using Kruskal's Algorithm in O(E * log(V)) time by sorting the edges, but this is likely to timeout because sorting the edges will take O(V ^ 2 * log(V)) time. We can use Radix Sort in base 2 ^ 15 (to speed up modulus calculations) and sort the edges in linear time, O(E) (2 ^ 15 is much less than the maximal number of edges). If we use path compression, and the union by rank heuristic, we'll get a running time of O(V ^ 2 * alpha(V)), where alpha(n) is the inverse of the ackermann function. Once the maximum spanning tree has been computed, we can run a dfs/bfs from each vertex of the graph and fill the entries of the minimal array in O(V ^ 2) time. The time limits of this problem were kept strict so that solutions using weaker methods could not pass the system tests.

You can view solutions here:

Problem Setter Solution: Fast Solution & Slow Solution

Problem Tester Solution

-------------------------------------------------------

CAVE (written by David Stolp)

This problem is a variant of the longest-path problem, which is NP-hard. The simplest solutions simply attempted to find any path from the northwest to southeast corner, for example using a modified version of Dijkstra's algorithm.

A better algorithm proceeds in two phases:

The first phase is to construct a graph where the vertices correspond to torches, and edges exist between 2 torches that can be reached within K steps of eachother. Then a longest-path algorithm is used to find a path that picks up as many torches as possible. For small values of K, it is difficult to visit all the torches, but for larger values of K it is quite common to be able to visit all or almost all of the torches.

The second phase is to then translate this path into a path in the original graph. The goal here is to visit as many cells as possible between each torch, and also minimize the number of cells that are visited multiple times. This can be accomplished by starting with a simple path, then augment it by adding unvisited cells to it.

You can view solutions here:

Problem Tester Solution

-------------------------------------------------------

CTEAMS (written by Tomaz Hocevar)

Lets have a look at what happens with existing teams when a new chef enters the kitchen. Depending on his age, he is assigned to the old or to the young team. But this change might throw the size of our teams off balance. Note that a single reassignment of a chef from the young to the old team or the other way around is enough to restore the balance. To perform the first mentioned reassignement we need to find the oldest chef in the young team and move him to the old team. We can perform these operations efficiently if we maintain both teams sorted by age. For example, in C++ you can make use of a STL set to achieve time complexity O(N*log N). The same thing can be accomplished with two heaps - max heap for the young team and min heap for the old.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

MINESREV (written by Tomaz Hocevar)

If you're not familiar with minesweeper, you might want to play around with it before attempting this problem. Start by marking every cell with the number of neighbouring mines. Let's take a look at what do these sets of simultaneously opened cells look like. Each such set consists of a connected component of zeroes and a set of cells a with positive number of neighbouring mines, which are the border of this connected component - let's call them border cells. Clicking on some zero cell will close the connected component and its border. But if you click on some border cell, you might close several components and their borders. Therefore, it's always optimal to aim for the border cells unless there is no border - be careful with entirely empty grids. You have no choice but to click on all cells which have no neighbouring zeros (this includes cells with mines).

You still have to choose minimum number of border cells to close all the components. This looks very much like the set covering problem. Next important observation is that each border cell can close at most 2 components. Try drawing a valid example with three components of zeroes around some positive cell and don't forget that you have to include at least one mine in its neighbourhood. You can model this situation with a graph. Nodes represent components of zeroes and if it's possible to close two components with a single click on some border cell, draw an edge between them. Notice the correspondence between a valid set of clicks and a matching in this graph. Look at it in the following way. You could use one click for every component. In comparisson, you can save one click by closing two components using a matched edge. What you're looking for is a maximum matching in this general graph, which is easier said than done. The famous algorithm for general matchings is Edmonds' blossom algorithm. It was probably a relief if you had a prewritten version. In case you don't, it might be worth reading Gabow's "Efficient Implementation of Edmonds' Algorithm".

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

RESTOCK (written by Tomaz Hocevar)

The request that the distance has to decrease with every pass is a very nice property although it might seem like a complication at first. Begin by sorting the cells by their distance to the storage. Now you can take a dynamic programming approach. Define f(i,j) as the cost of moving an item to the storage from position (i,j). You can compute f(i,j) from the previously computed costs of other closer positions which are within the passing range. You could simply scan the entire passing range and get a complexity O(N*M*D^2), which is too slow. But this query operation "which solution within passing range is the cheapest?" can be done faster with a data structure that supports updates and range queries in logarithmic time. A 2-dimensional segment tree is a good candidate. You have to pay some attention to equidistant cells. Process them in batches and perform the updates of the data structure at the end of the batch. The intended time complexity for this problem was O(N*M*(log D)^2). The timelimit is a bit on the strict side to prevent solutions with 1-dimensional segment trees, which would iterate over all rows within the passing range and perform 1-dimensional range queries within a row.

However, many contestants came up with a different solution. It is based on Dijsktra's shortest path algorithm with some optimizations. The important thing to notice is that all edges in the graph have the same weight. Therefore, when you process a node and insert adjacent nodes into priority queue, you will never have to update them again so you can simply remove them. You can maintain a sorted list of cells for each row and when you update some cell and push it into priority queue, you can also delete it from its row list. For small passing range D you only have to iterate over a few rows. This solution also works for large D. The cell lists will shrink rapidly because you will be deleting big rectangular chunks of cells with each update.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------