320A - Magic Numbers

Although the input number is very small, solving the problem for arbitrary length numbers using strings is easier. It's easy to prove that a number meeting the following conditions is magical:

• The number should only consist of digits 1 and 4.
• The number should begin with digit 1.
• The number should not contain three consecutive fours (i.e. 444).

Here is a sample implementation in C++:

#include <iostream>
#include <string>

using namespace std;

bool is_magical(string number) {
	for (int i = 0; i < (int)number.size(); i++)
		if (number[i] != '1' && number[i] != '4')
			return false;

	if (number[0] == '4')
		return false;

	if (number.find("444") != number.npos)
		return false;

	return true;
}

int main() {
	string number;
	cin >> number;

	if (is_magical(number))
		cout << "YES" << endl;
	else
		cout << "NO" << endl;

	return 0;
}

320B - Ping-Pong (Easy Version)

Imagine the intervals as nodes of a graph and draw directed edges between them as defined in the statement. Now answering the second query would be trivial if you are familiar with graph traversal algorithms like DFS or BFS or even Floyd-Warshall!

Here's an implementation using DFS: 3951145

And here's an implementation using BFS: 3947426

Finally an implementation using Floyd-Warshall: 3945330

319A - Malek Dance Club

Solving this problem was easy when you modeled the assignment with two sets of points numbered from 0 to 2ⁿ - 1 (inclusive) paired with 2ⁿ line segments. Each line segment corresponds to a dance pair. And each pair of intersecting lines increase the complexity by one.

Imagine you now the solution for binary string x. Now we want to calculate the answer for 1x and 0x easily. Look at the figure below:

The figure shows what happens in a simple case. Whenever you append 0 before x the same structure appears twice in the result. But whenever you append 1 before x the same structure appears twice but the first half of points in right column are swapped with the second half. This increases the number of intersections by size of first half times size of the second half.

So if x has length n and f(x) is the complexity of the assignment then we have:

• f(0x) = 2f(x)
• f(1x) = 2f(x) + 2²ⁿ

An interesting fact is that f(x) is equal to x2^n - 1.

319B - Psychos in a Line

Will be fixed :)

Let's find the murderer! Well, if you look close you see that each psycho is murdered by the nearest psycho on his left which has a greater id.

Now let t_i be the number of the step which i-th psycho in the line is murdered (not the psycho with id equal to i). Assume j-th psycho in the line be the nearest psycho with a larger id than i-th psycho in the line in his left. As we know j-th psycho kills the i-th psycho. We also now that this happens when all psychos between j and i have been killed. So t_i = max(t_j + 1, ..., t_i - 1) + 1.

Now we have a simple O(n²) solution using the above observations. To make things run faster you should be familiar with a classic problem. This problem asks to find the nearest greater element to the left of each element in a array. This problem has a O(n) solution. You can solve it yourself or read about it here.

After knowing about all these things it wouldn't be hard to figure out a way to solve this problem efficiently. Here is a cute implementation of what is described above: 3945963

319C - Kalila and Dimna in the Logging Industry

This problem is equal to finding the minimum cost to cut the last tree completely. Because any cutting operation can be done with no cost afterward. Let dp_i be the minimum cost to cut the i-th tree completely. It's easy to figure out that we can calculate dp_i if we know the index of the last tree which has been cut completely (j-th tree). Knowing this dp_i would be equal to dp_j + b_ja_i. So dp_i = min_{j = 1..i - 1}(dp_j + b_ja_i).

Using the above information the problem has an easy dynamic programming solution in O(n²). There's a known method which can be used to improve recursive relations with similar form. It's called Convex Hull Trick. You can read about it here.

319D - Have You Ever Heard About the Word?

TODO

319E - Ping-Pong

TODO

Привет, Codeforces! :-{D

По случаю двух важных событий в мире спортивного программирования (IOI и ACM ICPC) я и мои друзья (команда Ирана на IOI) решили сделать подарок всем пользователям Codeforces, которые будут участвовать хотя бы в одном из этих двух соревнования, а также всем остальным. :)

Этот раунд подготовил я (havaliza), dani1373 и keivan, также нам помогал fab. Я хочу поблагодарить всю команду Codeforces за их усилия в поддержании этого веб-сайта.

Надеюсь вам понравится решать задачи так же, как нам понравилось их готовить! ^.^

Update 1. Распределение баллов по задачам в Div. 1: 500-1000-1500-2500-2500, в Div. 2 распределение стандартное.

Update 2. Большое спасибо пользователю Aksenov239, который очень много помогал нам в подготовке раунда.

Update 3. Here is the editorial. To be completed soon :)

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 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! :)

Всем привет! :{

Мы очень рады пригласить Вас поучаствовать в очередном Codeforces Round #173, который был подготовлен A.K.Goharshady, LGM и мной (havaliza). Я хочу традиционно поблагодарить Gerald, MikeMirzayanov и Delinur за помощь в подготовке раунда. Также большое спасибо dani1373, hhoomn, mruxim, MMJ и xorfire. Они тестировали задачи и в целом очень сильно нам помогли.

Кстати, сегодня день рождения у LGM's, а вчера был у gpac's. Давайте поздравим с днем рождения этих ребят! ^.^

Я надеюсь вам понравится сегодняшний раунд, и вы получите от него много фана! :)

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. :)

Всем привет! :)

Совсем скоро начнется Codeforces Round #168. haas и я (havaliza) авторы сегодняшнего контеста. Я хочу поблагодарить Gerald и Delinur за помощь в подготовке задач, а также MikeMirzayanov за его систему.

Надеюсь, что Вам понравятся задачи также сильно, как нам понравилось их готовить. ^.^

Good luck and have fun. :)

Это перевод оригинального поста автора, комментарии на английском приветствуются.

UPD1.

Распределение баллов по задачам:

Div2 = standard

Div1 = 500-1000-1500-2000-2000

Hi :)

Here is the editorial for round #148. I just tried to explain the ideas rather than detailed implementation explanation. I'm sorry for my bad English, so please tell me if something is not clear in the descriptions.

Two Bags of Potatoes

The author of this problem is Gerald. The total number of potatoes is a multiple of k and constraint there will be at most 10⁵ multiples of k in range 1 to n. So you can iterate on multiples of k and print the ones that satisfy the problem.

Easy Tape Programming

In this problem you just need to simulate every thing which is written in the statement step by step. You can see a simple implementation of this here: http://www.codeforces.com/contest/239/submission/2512422

Not Wool Sequences

Let a₁, ..., a_n be a not-wool-sequence. We define another sequence called b in which b_i is xor of the first i elements of a, and b₀ = 0.

Now xor of elements of a consecutive subsequence like a_i, ..., a_j will be equal to . So we know that all elements of b should be different. Therefore b is a sequence of distinct integers of length n + 1 starting with 0 made of numbers 0 to 2^m - 1. The number of such sequences is and this is the answer to problem.

Boring Partition

Coming soon...

World Eater Brothers

Consider we only want to change direction of minimum number of roads so that all other countries are reachable from a specific country x. This problem can be solved in O(n) and it's exactly what 219D - Choosing Capital for Treeland asks for. If you don't know how to solve it you can read the editorial of that contest.

Consider two countries A and B which can be chosen by world eater brothers to achieve the minimum number of road direction changes. After changing the direction of roads, there exists a country on the undirected path between A and B which is reachable from both A and B using roads. We call such country a middle-country.

We want to iterate on middle-countries and find the best two countries for ruling for each middle-country. For each neighbor of the current middle-country calculate the minimum number of road changes in the subtree rooted at that neighbor so that all countries will be reachable from some country in that subtree. Then from two of these subtrees we need to pick A and B and all other subtrees will have edges pointing to the root of subtree. This can be computed in O(n) for each middle-city. So the overall complexity will be O(n²).

Tape Programming

This problem was my favorite in the problemset. The primary point is that at any moment during the interpretation of a program only a prefix of the program is modified and used by IP.

Consider we want to calculate the output of subsequence s_l, ..., s_r. While running the original program s₁, ..., s_n if at any moment CP enters the interval [l, r] it should be pointing to position l and the direction of DP should be right. So it's like we have started interpreting s_l, ..., s_r independently. The termination of execution of s_l, ..., s_r is the first time CP points to somewhere outside interval [l, r].

Therefore what we need to solve the problem is to run the original program. And after each termination if the program is nonempty then run it again until program is empty. Then we should keep a log of positions we have visited and the time of each visit and the number of printed digits of each type until then. After this preprocessing the to calculate the answer of query (l_i, r_i) its enough to find the first time CP visited s_li and the first time CP visited s_ri + 1 or s_li - 1 after that.

The described approach can be implemented in O(nlog(n) + qlog(n)).

Meeting her

Consider a bus passing a shortest path from s_i to t_i. There are some points that are necessary to pass in order to obtain a shortest path. Firstly we compute them. This can be done in O(n³) with Floyd-Warshall and some processing after that. Urpal is sure that a bus from i-th company always passes such vertices on his path from s_i to t_i. So he can get on a bus from i-th company only at vertices the bus surely passes.

At any moment Urpal's status can be uniquely determined by his position on the map and the bus he's traveling with. So we have nk states (position, bus).

Our goal is to reach some (b, ...) state from a (a, v) state which bus v surely passes a (source states). So let's find all states that can reach a goal state. We call such states good states.

Consider Urpal is at junction x and he's traveling with a bus of type y. Let v₁, v₂, ..., v_w be the list of junctions the bus might go on its shortest path from s_y to t_y. And let c₁, c₂, ..., c_l be the list of companies that their bus surely passes junction x, excluding y-th company. For state (x, y) we know we can reach junction b (it's a good state) if one of the following is true:

• x = b, the minimum cost of solving the problem will be 0.
• All states (v₁, y), (v₂, y), ... and (v_w, y) are good states, the minimum cost of solving the problem will be the maximum of all these states.
• At least one of states (x, c₁), (x, c₂), ... or (x, c_l) is a good state, the minimum cost of solving the problem will be the minimum the good ones plus one.

At first the only good states we know are states with junction b, (b, ...). Now some new states might have become good states. So we add those states to the list of known good states. We do this until no state becomes good anymore.

At the end we print the minimum cost of source states which are good, and if they don't exist we print -1.

The process thing can be implemented in O(n⁴). :)

Всем привет! :)

Рад пригласить Вас на очередной Codeforces Round #148. Я (Hamed Valizadeh) автор этого раунда.

Я благодарю Gerald (Геральд Агапов), MikeMirzayanov (Михаил Мирзаянов), Delinur (Мария Белова), и Saeed_Reza (SaeedReza Seddighin) за помощь в подготовке этого раунда.

Распределение баллов по задачам стандартное в обоих дивизионах: 500-1000-1500-2000-2500.

Надеюсь задачи Вам понравятся.

Good luck and have fun ;)

Update. Соревнование закончилось. Мои поздравления победителям обоих дивизионов! :)

Div1:

1. tourist
2. cerealguy
3. Dmitry_Egorov
4. RAVEman
5. UESTC_Nocturne

Div2:

1. LiWenHaoTianXiaDiYi
2. goooooooopan
3. jthread
4. kolina
5. xcodevn

Поздравляю участника Endagorion — единственного, кто решил задачу 238D - Ленточное Программирование.

Кстати, я надеюсь, что вас не сильно расстроила скучная задача!

Update 2. Разбор готов. Прошу прощения за задержку. http://codeforces.net/blog/entry/5765

Today, I wrote the code for two different approaches of 220B - Little Elephant and Array (one O(nlgn) and one ) and both of them got verdict Wrong answer on test 33. Here are the submissions:

2097772

2096670

Also my friend LGM submitted his previously accepted code and also got Wrong answer on test 33.

2086826

2097755

Could admins please check if there is something wrong?