Hi :)

Here's the editorial for round #168. This time I tried to do my best to prepare a good contest. In some parts I failed but I still learned many things which will surely help me to do better next times! ^.^ I hope you've liked the problems. :)

275A - Lights Out

Author: havaliza

For each light you should count the number of times it’s been toggled. Consider a light is toggled k times. If k is even then the final state of the light is ‘on’ otherwise it’s ‘off’. The implementation would be easy. You may look at the accepted solutions as reference.

275B - Convex Shape

Author: havaliza

Consider a pair of black cells. There exist at most two different valid paths we can take between these two cells. The naïve solution would be to check the existence of at least one of these paths for each pair of black cells. There are O(n²m²) such pairs and each pair can be checked in O(n + m). So the time complexity will be O(n²m²(n + m)) which is enough to get accepted.

But there exists a O(nm) approach. It’s obvious that each row of the grid either doesn’t have any black cell or the black cells are a consecutive part of the row. The same holds for every column. For every non-empty row consider the interval of its black cells. The intersection of intervals of all non-empty rows should be non-empty. If the same holds for all columns then our grid is convex. The proof of this solution is not hard and is left for the reader.

274A - k-Multiple Free Set

Author: havaliza

Consider an integer x which is divisible by k. At most one of the integers x and x / k can appear in the maximum k-multiple free subset. Also for any integer y at most one of the numbers y and yk appears in the answer. If you look like this you can see the input as chains of numbers so that for each chain no two adjacent elements can appear in the output. For example, If k = 2 then 6, 12, 24, 48, 96 forms a chain. It’s easy to see that from a chain of length l we can choose at most (l + 1) / 2 elements in the answer. So the solution would be to compute the lengths of the chains and pick as much numbers as we can from each chain. You can sort all the numbers and do binary search or similar things to find the length of chains. Here’s a cute greedy solution which picks numbers greedily from the chains:

First sort all the numbers. Also consider an empty set of integers S, which represents the output. For each integer x in the sequence, If it’s not divisible by k, just pick it and insert it into S. Otherwise if it’s divisible by k check if x / k is in S or not. If it’s not in S insert x into S otherwise skip x.

I’d also like to note that this problem comes from an old problem in UVa Online Judge, with the same the name.

274B - Zero Tree

Author: havaliza

In the problem statement vertex 1 is not mentioned as root of the tree. But it seems if we make it the root of the tree we can figure out the solution easier. For the leaves of the tree we can see the least number of steps needed to make each of them equal to zero. Consider a vertex which all its children are leaves. The minimum number of times that we should increase this vertex is at least as the maximum times one of the children of this vertex is increased. Also the minimum number of times this vertex is decreased is at least as maximum times one of the children of this vertex is decreased. Now we know some necessary plus or minus steps that this vertex is included in them. So after all of the children of this vertex reached zero, this vertex itself has some new value. If the current value of the vertex is positive we should decrease this vertex certain times otherwise we should decrease it. So we can find the minimum number of times this vertex should be decreased and the minimum number of times this vertex should be increased. As we showed above if we know these pair of numbers for each child of a vertex then we can calculate these numbers for that vertex too.

This can be implemented using a simple DFS on the rooted tree. And the answer to the problem would be the sum of increments and decrements of vertex 1. The time complexity of the solution is O(n).

274C - The Last Hole!

Author: haas

In the solution we will try to find the position of all points which are the last moments in holes. Here we claim that each minimal potential hole is one of these two forms:

1. For each three centers that form an acute triangle it’s obvious that they form a potential hole. The last point in this hole would be the in triangle’s circumcenter.

2. For each four centers which are sides of a square it’s also obvious there’s a potential hole with last point being the square’s center.

For each potential hole we should check if the last point is not covered with any other circle in the last moment. The solution would be the hole with maximum distance from the centers which won’t be covered by anything else.

Let’s remind some geometry facts. We know that circumcenter of a triangle is the point where the three perpendicular bisectors of the triangle meet. Also the circumcenter of the triangle lies inside the triangle if and only if the triangle is acute. Circumcenter is the point which has equal distance from each vertex of the triangle.

Using above information it’s easy to prove that three circles make a hole if and only if the triangle they form is acute. Now what remains is to prove that in the last moment which the hole is disappearing there are 3 triangles or four forming a square enclosing the hole. I’m not going into details but the proof would be like this. Consider the last point of a hole. There are some circles which form the border of the hole in the last moment. These centers have the same distance from the last point. We need to prove that only three of the centers or four of them which form a square do the same job. And all others can be ignored. Consider the circle which these centers lie on its perimeter. Here’s a way to pick at most four of these points which make that hole. As long as there are three consecutive points which form make a obtuse triangle delete the middle point (why?). It’s easy to see what will remain at the end is either a square or an acute triangle.

The implementation can be done in O(n⁴) with iterating through all triangles in O(n³) and checking them in O(n). Also there are at most O(n³) squares, because once you’ve picked three of its vertices the fourth will be unique.

We’ve seen other coders implementing this solution or other solutions in better time complexities. So please share your solutions in the comments. :)

274D - Lovely Matrix

Author: havaliza

The naïve solution for this problem would be to make a graph were each vertex represents a column of the grid. Then for each two not erased integers x and y in the same row where x < y we can add an edge from the column of x to the column of y in our graph. Then topological sorting on the built graph would give us the sought order of the rows. But there can be as much as O(m^2) edges in our graph and thus a O(nm²) solution won’t pass the time limit.

But still the idea to solve this problem is to implement topological sort in a such way that the graph we make has less edges or to make less processing to find the topological sort. Here I present two solutions which use topological sorting. One implements topological sorting explicitly in a graph of columns as its vertices with some extra vertices but fewer edges. The other one does some kind of topological sorting without building the graph and by deciding which column can come as the first column of our ordering, and doing the same thing until all columns come in order.

The first solution relies on decreasing the number of edges we used in the graph of our naïve solution. Consider the numbers of a row sorted. We insert an extra vertex between each pair of adjacent different numbers. Then each column gets connected to the next extra vertex and each extra vertex gets connected to the columns before the next extra vertex. In this way the sorted order of this row would be preserved in topological sorting. We do the same thing for each row, so topological sort on the final graph would give us the sought ordering of columns. This can be implemented in O(nmlgm).

In the second solution for each row we color all the minimum not erased elements of that row. The first column in the output permutation should be a column where all of its non erased elements are colored. So we put this column as the first column. Now the rest of the columns can be ordered by the same way. If at some point we can’t find a suitable column then there’s no solution. This also can be implemented in O(nmlgm).

It seems the problem was easier than a usual D problem, but before the contest I didn’t think so. I myself found the idea to solve this problem after some time, so I thought it wouldn’t be suitable for a C. Any ideas on how to measure the hardness of a problem better for next times? Because it doesn’t feel so good not to see the problems solved according to the foreseen difficulty level! :D

274E - Mirror Room

Author: havaliza

The blocked cells can make lots of complicated patterns. So it’s obvious that the solution in includes simulating the path the laser beam goes. But the dimensions of the gird are large and the beam might travel a long path before entering a loop. So naïve simulation will surely time out (See note!).

It’s kind of obvious that the beam finally comes back to its initial position and direction. Here were going to prove that the maximum number of times the beam might reflect until it reaches its first state is O(n + m + k). Consider an empty grid, It has O(n + m) maximal empty diagonal segments. When we block a cell, the two diagonal segments which pass this cell split. So the number of maximal empty diagonal segments increases by two. There for there are O(n + m + k) of these segments. Also If you look at the behavior of the beam it passes some of the segments one after another. So if you simulate the beam, it reflects O(n + m + k) times. Instead of naïve simulation we can find the next position the beam reflects.

Now we’re going to prove that no cell will be visited twice. A cell gets visited twice in the cycle if we pass it in both NE-SW direction and NW-SE direction. Consider the grid colored in black and white like a chessboard. There are two types of diagonal segments the NE-SW ones and NW-SE ones (property 1). At each reflection we alternate between these two. Also there are two types of segments in another way, black segments and white segments (property 2). As you can see each time one of the properties changes the other one also changes. As a result we’ll never pass a black cell in both directions, and the same is for a white cell.

So this problem can be solved with simulation in O((n + m + k)lgk).

You'd like to read Petr's solution for a clean implementation of this approach. 3162462

Note: The random tests I had generated before the contest were weak and I didn’t notice that naïve simulation solutions would pass the test. Now the tests are more powerful. :)