July 2011 Contest Problem Editorials

NETWORK (written by David Stolp)

 

I'll be the first to admit that needless optimization problems are not very fun. In this case, however, the intended solution complexity was either O(C*S^2) or O(C^2), so the 2 second time limit was actually quite generous. Unfortunately, many passing solutions had worse complexity but relied on constant-factor optimization tweaks, which is why it might have felt like a needless optimization problem.

 

We treat the problem as a network flow problem. There is a node for each access point, and one for each computer, as well as a source node and sink node. There's an edge from the source to each of the access points with capacity equal to the access point's capacity. There's an edge from each computer to the sink with capacity 1. Initially, there are no other edges. For each computer, we will add edges to the graph until an augmenting path is possible. These additional edges correspond to connections from a computer to an access point, and are added in ascending order by distance. Once an augmenting path is found, the length of the longest edge is output. The augmenting path algorithm used is the key to this problem, and 2 different versions follow.

Solution 1

This is the solution used by the setter. Consider paths of length 2 in the residual graph of the flow network. Construct a secondary graph with S+1 nodes: one for each of the access points, and one for the sink. The number of edges between any two nodes in this graph is constructed as the number of paths of length 2 between the corresponding nodes in the residual graph of the flow network. Additionally, we keep a (S+1)*(S+1) boolean matrix, where cell (i,j) indicates whether there exists any path from node i to node j in the secondary graph. This matrix is stored as an array of bitsets.

Now consider the operation of adding an edge to the flow network. At most 1 edge is added to the secondary graph, and at most S bitset operations are needed to update the matrix. We can now check if an augmenting path exists by checking the matrix at positions (i,j) where i is an access point not yet at capacity, and j is the sink. If an augmenting path exists, the path can be found in O(S^2) using a depth-first search, the secondary graph updated in O(S^2), and the matrix rebuilt using the Floyd-Warshall algorithm in O(S^2) bitset operations. Thus, adding an edge to the graph takes O(S), and augmenting the graph takes O(S^2). Since O(C*S) edges are added to the graph, and O(C) augments are performed, the total complexity is O(C*S^2), where bitset operations are assumed to take constant time.

Solution 2

This is the solution used by the tester. When adding a new computer to the network, we place the computer in a queue, and mark all access points as unvisited. We then repeat the following process until either the queue is empty, or we visit an access point which is not yet at capacity: Take a computer from the queue, and find all unvisited access points which have an edge to this computer (this can be done in a single bitset operation). If any of these access points is below capacity (which can be checked with a single bitset operation), we've found an augmenting path. Otherwise, for each of these access points, mark it as visited and add all of the computers it services to the queue. If the queue is emptied before an augmenting path is found, another edge is added to the graph. If the computer corresponding to the new edge was previously queued, it is queued again, and the above process continues. Since each computer is queued at most once per augmenting path plus once per edge added, the total runtime is O(C^2), where bitset operations are again assumed to take constant time.

 

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

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

YALOP (written by Ivan Mistreanu)

 

Of course the problem is very much alike the famous Lights Out puzzle. However the size of the board can be big enough and we can’t just tap any cell, but adjacent ones in any 8-directions. Let’s see how it changes the solution. Remember that we only need to find out if the puzzle is solvable.

First we can see that if both dimensions of the board are greater than 1, than the fact that we can tap only adjacent cells doesn’t matter. For example if we consider 2x2 board then starting from any initial cell and from any configuration we can achieve any other configuration and finishing in any other cell. So for bigger boards we can divide the board into 2x2 sub-boards (maybe overlapping) and we can have any configuration we need. The situation is different when one of the dimensions is 1. We will look into it later.

So now both dimensions are more than one and also the statement has it that one of the dimensions is less than 40. Let us consider that 1 < m < 40 and m <= n. Let us work with single lights independently. For each single light turned on (red cell) we can use light chasing method to move the lights to the lowest row. However the number of rows can be large, so we can’t just simulate the steps. We can see that when we eliminate each row there are at most two rows in which the light can be on. And the configuration of these rows on the next step depends on the previous. So the state of the light chasing can be represented by 2*m bits. And those states go in cycles. Also despite that there are 2*m bits the actual lengths of the cycles are not large for m < 40. So, for example for the light on in x-th row and y-th column, the calculate the cycle for light chasing starting from the light in y-th column and the take the state number n-x modulo the length of the cycle. Then we merge all the configurations of the last row for all the red cells. We do the same starting from configurations we get after tapping each cell in the first row. No the puzzle can be solved by the standard method for Lights Out involving Gaussian elimination. Alternative way to chase all the lights to the bottom row is using matrix exponentiation.

As it was said before when one of the dimensions in 1 the situation is different. We can see that when Johnny start movement he stepped on 0 cells and his position is 1. When he makes the step he changes the position and step count by one. So we can see that the step count and his position will always have different parity. So not all the configurations are reachable unlike when dimensions are greater than 1. Now we need to check: 1) if it’s possible to turn all the cells blue; 2) how many steps it is needed to do this; 3) if the parity of the final position is different to the parity of number of steps. After checking this and alternatively trying to tap the very first cell we can decide if the puzzle is solvable in this case.

 

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

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

AEHASH (written by Ashar Fuadi)

 

This problem can be solved using dynamic programming approach.

Let DP(V, A, E) be the number of binary strings containing A 'A' characters and E 'E' characters, and have hash value V.

The base cases are

* DP(0, 0, 0) = 1, DP(*, 0, 0) = 0 (* other than 0)

* DP(1, 1, 0) = 1, DP(*, 1, 0) = 0 (* other than 1)

* DP(0, 0, 1) = 1, DP(*, 0, 1) = 0 (* other than 0)

Then, we must define the recurrence formula. Let N = A + E. After the split, let the first half (N/2) of the string contains A1 'A's, E1 'E's, and has hash value V1. Let the second half (N - N/2) of the string contains A2 'A's, E2 'E's, and has hash value V2. Because they are independent, we can simply take the product.

So, the recurrence becomes

DP(V, A, E) = sum { DP(V1, A1, E1) * DP(V2, A2, E2) }

for all

A1 + A2 = A

E1 + E2 = E

A1 + E1 = N/2

A2 + E2 = N - N/2

max(V1, V2) = V - A

So, the idea is to try all possible values of A1, A2, E1, E2, V1, V2, then take the sum of the products. First, we try all possible values of A1. We automatically get A2, E1, and E2 by exploiting the above equation. After that, try all possible values of V1 and V2 whose max value is V - A.

This is our current solution in pseudocode.

for A1 := 0 to A

A2 := A - A1;

E1 := N/2 - A2;

E2 := E - E1;

for V1 := 0 to V - A

for V2 := 0 to V - A

if max(V1, V2) = V - A

DP(V, A, E) += DP(V1, A1, E1) * DP(V2, A2, E2);

The above algorithm is not very efficient, since there are only O(V - A) pairs of (V1, V2) that satisfy max(V1, V2) = V - A, i.e. when one of them is V - A. So, we can improve that into

for A1 := 0 to A

A2 := A - A1

E1 := N/2 - A2

E2 := E - E1

// both are V - A

V1 := V - A;

V2 := V - A;

DP(V, A, E) += DP(V1, A1, E1) * DP(V2, A2, E2);

// V1 is V - A, V2 < V - A

V1 := V - A;

for V2 := 0 to V - A - 1

DP(V, A, E) += DP(V1, A1, E1) * DP(V2, A2, E2);

// V2 is V - A, V1 < V - A

V2 := V - A;

for V1 := 0 to V - A - 1

DP(V, A, E) += DP(V1, A1, E1) * DP(V2, A2, E2);

The algorithm can still be improved further, by replacing the two for's by partial sum, like this:

for A1 := 0 to A

A2 := A - A1

E1 := N/2 - A2

E2 := E - E1

// both are V - A

DP(V, A, E) += DP(V-A, A1, E1) * DP(V-A, A2, E2);

// V1 is V - A, V2 < V - A

DP(V, A, E) += DP(V-A, A1, E1) * SUM(V-A-1, A2, E2);

// V2 is V - A, V1 < V - A

DP(V, A, E) += SUM(V-A-1, A1, E1) * DP(V-A, A2, E2);

where SUM(V, A, E) = sum {DP(V, A, E)} for all v := 0 to V.

The complexity then becomes O(A^2 E V). If you have completed the solution, you can easily check that the maximum value of V is 152.

 

You can view solutions here:

Problem Tester Solution

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

LOKBIL (written by Ashwin Jain)

 

Most of the people helped our cook to find the most popular friend and he is very happy now. Facebook walls didn't get spammed. But some of you got stuck in finding him, and thus, our cook wants to explain how to find " the most popular friend". It's quite simple, create a matrix of friends such that if 'i' is a friend of 'j' then friend[i][j] =1, else friend[i][j]=0. Now, run Breadth First Search on each friend to find the distances of each friend from him. After finding this, calculate the average distance of everyone from him. After calculating it for all, print the friend with the smallest average. Yes, he is the one.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

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

BB (written by Gennady Korotkevitch)

 

First, let's reformulate the problem a bit. In fact, we have to find how many different bit strings of length N exist such that among every M consecutive bits there are at least K 1's and the total number of 1's is minimal possible for such strings.

Consider the case when N is divisible by M. In this case the string consists of N/M blocks of bits of length M, and by the problem statement we have to put at least K 1's in each of these blocks, giving a total of N/M*K 1's. But note that this is also minimum, since we can put these 1's at the ends of blocks and thus satisfy the needed restrictions.

Now let's make a table of size K x (N/M), where each column contains the positions of 1's in the corresponding block from the start of that block in increasing order (so the maximal possible number in this table is M). For example, if N = 24, M = 6, K = 3 and our bit string is 000111 001101 100110 110100, then the table should look like this:

4 3 1 1

5 4 4 2

6 6 5 4

Obviously, the numbers in each column strictly increase. An important thing to note now: if there are two neighbouring numbers in one row such that the leftmost one is strictly less than the other one, then this string doesn't meet the condition from the problem statement -- between the corresponding 1's there will be K-1 1's and at least M positions, so any block of length M between them will have less than K 1's. The reverse thing also holds: if the numbers in every row weakly decrease, then the bit string corresponding to the table will be correct. Thus if we find a way to count the number of such tables, we'll also be able to count the number of needed bit strings.

From this moment on you may either try to find some pattern and finally get the needed formula (this has been successfully implemented by several contestants) or try to search the internet for something on this topic. In the latter case it's useful to know that standard Young tableaux look similar to these tables. Then, Wikipedia article on the topic tells us that what we're searching for are actually semistandard Young tableaux! (see http://en.wikipedia.org/wiki/Young_tableaux#Tableaux). A bit of further searching leads us to a hook-content formula which is exactly what we need (for example, it is described here). So we're done. (and yes, searching "bijective proof of hook-content formula" gives quite a lot of results)

Well, not really. We still have to multiply and divide about a billion numbers. Fortunately, a lot of these numbers cancel each other. For example, let's look what happens when N = 48, M = 6 and K = 3. The numbers to multiply are:

13 12 11 10  9  8  7  6

12 11 10  9  8  7  6  5

11 10  9  8  7  6  5  4

and the numbers we should divide the result by are:

10  9  8  7  6  5  4  3

9  8  7  6  5  4  3  2

8  7  6  5  4  3  2  1

It's easy to see that a lot of columns cancel each other. Actually, there will be no more than M columns remaining in both tables, so there will be no more than M*K numbers to multiply and divide (note that division modulo prime number is also a well-known topic, for example look here).

Another way to perform this is precalculating factorials modulo 1 000 000 007 of all numbers, say, divisible by 500 000 (or less, still considering the source code limit). Now it's easy to find any needed factorial in at most 500 000 multiplications, and we require no more than 100 of these factorials. This approach should be optimized well, though.

And we're almost done. Don't forget that we've solved the problem only when N is divisible by M. But in reality every possible case can be reduced to the case above. Suppose there are floor(N/M) blocks and P leftover positions. If P <= M-K, it means that there should be only 0's in the first P positions of each block. If P >= M-K, it means that there should be only 1's in the last M-P positions of each block (note that we must add one more block for those P positions then). Once P = M-K, both these cases are equivalent and the answer is always 1. This paragraph is easy to understand if you spend some time with a pen and paper.

This time, we're absolutely done. Still there were some solutions using matrix exponentiation and possibly some other ideas. I would be happy to hear any alternative solutions or ideas to this problem in comments :)

 

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

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

KITCHEN (written by Gennady Korotkevitch)

 

 

This problem is not NP-hard almost for sure, but still for sure it is hard! Even though the input given is just two numbers up to 100 each, no one found the optimal solution for all cases (or maybe only Tomasz did :)). Let's see what we can do with this problem.

Consider cells with '#' characters as vertices of a graph, and pairs of neighbouring cells as edges of the same graph. You can understand from the problem statement that this graph should be a tree. A simple and well-known fact is that for any tree V = E+1, where V is the number of its vertices and E is the number of its edges. Suppose we put '#' in every cell of the grid. In this case we have V = N*M and E = (N-1)*M + N*(M-1) (it's easy to see why this is so). Now let's remove K cells and put '.' in them. Then we'll have V = N*M - K and E = (N-1)*M + N*(M-1) - 4*K + B + 2C + P, where B is the number of '.' cells on the border of the grid, C is the number of '.' cells at the corners, and P is the number of pairs of neighbouring '.' cells -- generally, each removed cell removes 4 edges, but sometimes there are unexisting and twice-removed edges among those. From V = E+1 we can get a formula for K: K = ((N-1)*(M-1) + B + 2C + P) / 3. If we say that Q = B + 2C + P, it can be easily seen that instead of minimizing K we may minimize Q. Also note that for all trees on the N*M grid the remainder of division of Q by 3 is the same (otherwise in some case we would get a non-integer K). Another thing to notice is that Q can't be equal to 0, since in this case the border of the grid will form a cycle. So if we find a solution with Q equal to 1, 2 or 3, it will be optimal! The easiest case where the optimal solution can be found is when N is even and M equals 1 modulo 3 (or vice versa). The grid might look like this:

.#####################

##.#.#.#.#.#.#.#.#.#.#

#.###.#.###.#.###.#.##

##.#.###.#.###.#.###.#

#.###.#.###.#.###.#.##

##.#.###.#.###.#.###.#

#.###.#.###.#.###.#.##

##.#.###.#.###.#.###.#

#.#.#.#.#.#.#.#.#.#.##

####################.#

Here we have B = 1, C = 1 and P = 0, so Q = 3. It can be easily seen how to build a similar grid for other N and M satisfying the conditions above.

This actually covers about 11/36 of all possible test cases, so there are still about 2/3 of the test cases left unsolved. The key is in searching for and optimizing different patterns for given N' and M', where X' is the remainder of division of X by 6.

Another useful thing is hardcoding the answers for the cases when one of the dimensions is small using dynamic programming, but this is quite difficult.

 

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

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