havaliza's blog

By havaliza, 7 years ago, , 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 - Уходя, гасите свет!

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 - Выпуклая фигура

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(n2m2) such pairs and each pair can be checked in O(n + m). So the time complexity will be O(n2m2(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-делимости

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 - Нулевое дерево

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 - Последняя Дыра!

Author: HamedSaleh

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(n4) with iterating through all triangles in O(n3) and checking them in O(n). Also there are at most O(n3) 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 - Прекрасная матрица

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(nm2) 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 - Зеркальная комната

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. :) Tutorial of Codeforces Round #168 (Div. 1) Tutorial of Codeforces Round #168 (Div. 2) Comments (33)
 » Oh, problems and editorial are really great) Thanks!
 » 274A — k-Multiple Free Set: You can sort all the numbers and do binary search or similar things to find the length of chains. How to find the length of chains with binary search?
•  » » Add: "You can sort all the numbers and do binary search or similar things to find the length of chains."This comes from author's editorial in paragraph 1 in 274A — k-Multiple Free Set.
•  » » If you have all the numbers sorted, for each number x which is divisible by k you can find x/k using binary search which is the previous element in the chain.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   using sets or maps is faster to code than binary search :)Edit: oops I meant "sets or maps" not "sets of maps" sorry for typing mistake.
•  » » » » I think he said this for the ones who didn't know how to use maps or sets. :)
•  » » » » » better for those programmer to learn about sets and maps.
 » 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! :Dbecause many programmers hate geometery problems, my friend tell me that hew closed the problem statement immediately after he realize that this problem is geometery even before completing reading the statment
•  » » 7 years ago, # ^ | ← Rev. 4 →   because many programmers hate geometery problems, my friend tell me that hew closed the problem statement immediately after he realize that this problem is geometery even before completing reading the statmentHating something is not a good reason for not to think about it. In my opinion programmers participate in contests to be ready for any given problem in the real world, including geometry problems. So I highly recommend your friend not to give up when face a geometry problem.HF & GL!
•  » » » I totally agree with you, but I'm afraid that my friend don't.I always tell him the same words.anyway I just wanted to tell a reason why D solved more than C problem.
 » 275B — Convex Shape: "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." look at a sample of the input: 3 5 WWBBB WBBBB WBBBW it satisfied the explanation,but obviously,it should output:"NO".
•  » » 7 years ago, # ^ | ← Rev. 2 →   interesting, you're right. So, is there an O(n*m) algorithm?
•  » » » I'm thinking why my (n^2 m^2) approach failsFor every black item (i,j) I check if it can reach all remaining black item by at most 1 turn. To do this, I check the black cell at top of (i,j) i.e. i-1,j i-2,j... until it hits the boarder or white cell. Then, I make a turn for all reachable cell, i.e. For every (k,j) that k=i-1, i,2 that is reachable before hits the boarder, I check (k,j-1) (k,j-2) ... (k,1) or until it hits a white cell. Then, For every (k,j) I find the reachable cell (k,j+1) (k,j+2) ... (k,m) or until it hits a white cell. I labelled all reachable cell. I repeat the above process by extend it left,bottom,and right, and find all reachable cell. Then, I find if any black cell is missing and in case of this I set answer='NO'But I got WA :(
•  » » » » http://codeforces.com/contest/275/submission/3154825 here is my submission.It supposed to have a (nm * ((n*m)+(n*m)+(n*m)+(n*m))) complexitiy :(
•  » » Oh, you're right! Actually I thought of this solution without coding it. Now it seems it's wrong. Thanks for mentioning. :) I'm sorry about this.
•  » » » It really takes me a long time to recognize that.Looking forward to another brief solution.:)
•  » » » Actually there is an O(nm) solution, but the condition should be (apart from being connected...): The intersection of each pair of black cell intervals for each non empty row should be equal to the smallest interval, (each interval sould contain or be contained by all the others), the same must hold for the columns. The simplest counter example to your solution is board containing the most evil tetris piece.
•  » » There exists a O(n*m) solution. The solution link. https://codeforces.com/contest/275/submission/42017353
 » Thanks a lot for your good contest and also for great editorial!! ^.^
 » waaaah, this is a great editorial, really helpful, thanks :)
 » 275B — Convex Shape There are O(n2m2) such pairs and each pair can be checked in O(n + m). So the time complexity will be O(n2m2(n + m)) which is enough to get accepted.but,n2m2(n+m) is O(625000000)...Calc left[x][y]=how many balck block on the left of (x,y) can go without turn. and up[x][y]. left[x][y]=left[x-1][y]+1 if (block[x][y] is black) up[x][y]=up[x][y-1]+1 if (block[x][y] is black) then, it's easy to check can (x0,y0) goto (x1,y1) with one turn.(left and turn up) or (up and turn left)... time is O(n^2m^2)...
•  » » 7 years ago, # ^ | ← Rev. 2 →   actully worst case for each pair is O(n+m) but not all pairs need O(n+m) the close pairs need less than n+m.so is it a bit less than O(625000000)anyway O(n+m) can be O(1) if you use pre-calculations
 » I'm still waiting for div1 C solution
•  » » I think voronoi graph can solve it (only need Half-plane intersection to work out the graph) but I 'm not vary sure..
•  » » Also waiting :(
 » Can you tell me why potential hole only accurs in acute triangle? And why common quadrilateral will not form a potential hole? It's obvious that any quadrilateral has a non-acute angle.
 » Hello, can i take tests of 274B problem ? i want to check my solution :P
 » Hey, In the lovely matrix problem, is there a constraint that nm ?
 » 4 years ago, # | ← Rev. 5 →   Ignore
 » I am very sure that your second solution to the problem D is wrong. Me myself I thought of that solution. It isn't always esentially to take the minimum. Sometimes it's good to save some '?' for the future the other columns
•  » » I think so too.I think it can't be done in O(nm log m)
 » Can anyone explain the solution to 275A - Lights Out more clearly ? The editorial does not explain about the neighbours being affected when we toggle the switch.
 » 3 months ago, # | ← Rev. 2 →   I foolishly misread the problem and solved it by dynamic programming link : https://codeforces.com/contest/274/submission/58131078