Codeforces Round #178 Editorial

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

294A - Shaass and Oskols

Although Oskol is not really name of a specie of birds, In Iran it's known as a kind of bird which is very forgetful and can't even remember his way back to home when he flies away! It's commonly used instead of the word "stupid" among the kids! :D

In this problem you just have to now how many birds are there on each wire after each shot. A good trick for the first and the last wire would be to define wires 0 and n + 1. In this way the birds that fly away sit on these wires and you don't need to worry about accessing some element outside the range of your array.

Here is a neat implementation in C++ from contestant rpslive: 3484601

294B - Shaass and Bookshelf

As said in the statement, the thickness of each book is either 1 or 2. Think about when we want to arrange v₁ books of thickness 1 and v₂ books of thickness 2 vertically and arrange all other n - v₁ - v₂ books horizontally above them to achieve a configuration with total thickness of vertical books equal to v₁ + 2v₂. Is it possible to find such arrangement? Because the total thickness of vertical books is fixed it's good to calculate the minimum possible total width of horizontal books. As the width of a book doesn't matter in vertical arrangement it's good to use the books with shorter width horizontally and the ones with longer width vertically. So pick out v₁ books with longest width among books of thickness 1 and do the same with books of thickness 2. The sum of width of n - v₁ - v₂ remaining books should be at most v₁ + 2v₂.

The solution would be to try the things we explained above for all possible values of v₁ and v₂. And print the best answer. :)

There exists other ways to solve this problem mostly using dynamic programming but this was the intended solution of the problem.

Here is a nice implementation in C++ from contestant bayram: 3485189 (You should also know that 'bir' means 'one' in Turkish and 'iki' means two!)

294C - Shaass and Lights

I just want to solve the third sample of this problem for you and you can figure out the rest by yourself. :)

The third sample is ...#...#... where # is a switched on lamp and . is a switched off lamp. As you can see we have three different types of lights. The first three lights (Type A), the 5th to 8th lights (Type B) and the last three lights (Type C). We have to switch on the lights three times for each type of lights. Aside from the order of moves for each type there are $\text{[math]}$ possible permutations of the string AAABBBCCC which tells us how to combine the steps of different types. Switching on the lights is done uniquely for types 1 and 3. But for type 2 each time we have to possible options until we're left with one off light. So there are 2^3 - 1 ways to do this. So the answer would be 1680*1*4*1 = 6720.

The general solution would be to find all groups off consecutive switched off lamps and calculate the number of ways to combine all these groups. Then for each group you should calculate in how many ways it can be solved.

The implementation needs some standard combinatorial computations which you can see here: 3485187

294D - Shaass and Painter Robot

TODO

294E - Shaass the Great

TODO

I promise the editorial will be completed come soon soon soon! :)

Comments (24)

Show archived | Write comment?

zxybazh

11 years ago, # |

E can be solved by selecting an edge and move it to the right place of the split trees. The right place can be found by calculating sums of all nodes in O(N) time, then select nodes in split trees that have the minimum sum to other nodes.

→ Reply

No_stop

11 years ago, # ^ |

Do you know how to solve problem D ? Thank you very much .

MinakoKojima

+15

There is a conclusion that as long as all the grids on edge have been visited, all the grids were visited. Although I don't know how to prove it.

Thank you .But the task is to paint the floor until there is no two side-adjacent tiles have the same color .

-8

But the starting point may not be on edge...Is that really right?

matrix

In this question it is guaranteed that it's on one of the edges.

About the proof maybe this helps : Suppose A is the set of all of tiles on the edges which must be colored in the final coloring(which is uniquely determined based on the tile robot is standing on in the beginning) and suppose all of tiles in A is colored right now and no other tile which is on an edge is colored.

now for each tile (x, y) inside A(but the tile which robot stops on), we know that the robot once entered it from one of the diagonals and exited from the other one. which means tiles in both of these diagonals are colored.

Now take any diagonal which the tiles on it must be colored in the final coloring. We call such diagonals good diagonal. Since each good diagonal has two tiles on it which are on the edge, there exist at least one tile that isn't the one that robot stops on. So for each good diagonal we know that the tiles on it are colored. which means that all of the good diagonals are colored.

And of course if any other tile in any other diagonals be colored then one of that diagonal's ends are colored as well which contradicts the fact that only tiles insides A got colored.

This means that if we reach such state the robot must stop and since the final state is counted such state, it's enough to check when we'll reach such state and if we don't print -1.