490A - Team Olympiad

The teams could be formed using greedy algorithm. We can choose any three children with different skills who are not participants of any team yet and form a new team using them. After some time we could not form any team, so the answer to the problem is minimum of the number of ones, twos and threes in given array. We can get O(N) solution if we add children with different skills into three different arrays. Also the problem could be solved in O(N²) — every iteration find new three children for new team.

490B - Queue

This problem can be solved constructively. Find the first student — it is a student with such number which can be found among a_i and could not be found among b_i (because he doesn’t stand behind for anybody). Find the second student — it is a student standing behind the first, number a_i of the first student equals 0, so his number is a number in pair [0, b_i].

After that we will find numbers of all other students beginning from the third. It can be easily done using penultimate found number. The number of the next student is a number b_i in such pair where a_i equals to number of penultimate found student number (that is a number in pair [ans[i - 2], b_i]). Look at the sample to understand the solution better.

490C - Hacking Cypher

At first, let’s check all prefixes of specified number — do they have remainder 0 when divided by the a? It can be done with asymptotic behavior O(N), where N -length of specified number C. If we have remainder of division by a of prefix, which ends in position pos, we can count remainder in position pos + 1: rema[pos + 1] = (rema[pos] * 10 + C[pos + 1]) % a.

Then we need to check suffixes.If we have remainder of division by b of suffix, which begin in position pos, we can count remainder of position pos - 1: remb[pos - 1] = (C[pos - 1] * P + remb[pos]) % b, where P — it is 10^(L - 1) module b, L — length of suffix (P we can count parallel).

Now let’s check all positions pos — can we cut specified number C in this position. We can do it if next four conditions performed: prefix of number C, which ends in pos is divisible by a; suffix of number C, which begin in pos + 1 is divisible by b; length of prefix and suffix more than 0; first digit of suffix is different from 0. If all four conditions performed we found answer. If we did not find any such positions, than print NO.

490D - Chocolate

We can change the numbers by dividing their by two or by dividing their by three and multiply two. Firstly remove all 2 and 3 from factorization of chocolate and determine equals their square or not. If their squares are not equals answer doesn’t exists. Otherwise calculate of difference between number of three in factorization, we should remove this amount of threes from the some chocolate, it depends from the sign, and recalculate difference between number of two in factorization and do the same.

490E - Restoring Increasing Sequence

Let’s iterate on specified numbers and try to make from current number minimal possible, which value more than value of previous number. Let’s current number is cur, previous number is prev.

If length of number cur less than length of number prev — let’s print NO, this problem has not solution.

If length of number cur more than length of number prev — replace all signs ? in number cur to digit 0, except case, when sign ? in first position — replace him on digit 1, because numbers in answer must be without leading zeroes.

Another case when lengths of numbers a and b are equal. Let’s iterate on positions pos, in which prefix number cur more than prefix of number prev. Now we need to try for this position make minimal possible number, which more than prev. In all positions pos_i, which less than pos, replace all ? on prev[pos_i]. In all positions pos_i, which more than pos, replace all ? on digit 0. If cur[pos] =  = ? than make cur[pos] = max(prev[pos] + 1, 9).

If received number less or equal to prev — this position is bad. From all good positions choose minimal number, received with operations above and assign him number cur and will continue iteration. If count of such positions is 0 we need to print NO.

490F - Treeland Tour

The problem is generalization of finding maximal increasing subsequence in array, so it probably can be solved using dynamic programming. We will calс dynamic d[(u, v)], the state is directed edge (u, v) in tree. Value d[(u, v)] means the maximum number of vertices where the band will have concerts on some simple path ended in vertex v going through vertex u. Also the concert in vertex v must be certainly.

To calc d(u, v) we should consider all such edges (x, y) that there is simple path started in x, going through y, u and ended in v. These edges can be found using dfs from vertex u which is not going through vertex v. All edges used by dfs should be reoriented. So if r[y] < r[v] then d[(u, v)] = max(d[(u, v)], d[(x, y)] + 1). The solution needs O(N²) time and O(N²) memory. The memory could be O(N) if you get indexes of directed edges without two-dimensional array.

435A - Queue on Bus Stop

The problem could be solved in one cycle by groups. The solution could be implemented in this way:

int result = 1;
int people = 0;

for(int i = 0; i < n; i++)
{
    if (people + a[i] <= m)
        people += a[i];
    else
    {
        result++;
        people = a[i];
    }
}

cout << result << endl;

435B - Pasha Maximizes

The problem could solved by greedy algorithm. We will try to pull maximum digits to the beginning. The algorithm could be described in this way:

1) Consider every position in the number from the first, assume that the current position is i
2) Find the nearest maximum digit from the next k digits of the number, assume that this digit is on position j
3) If this maximum digit is greater than current digit on position i, then make series of swaps, push this digit to position i, also decrease k, that is do k = k - (j - i)

435C - Cardiogram

This problem is technical, you should implement what is written in the statement. First, you need to calc coordinates of all points of the polyline. Also create matrix for the answer. Coordinate y could become negative, so it is useful to double the sizes of the matrix and move the picture up to 1000. In the end you should print the answer without unnecessary empty rows.

To paint the cardiogram you should consider every consecutive pair of points of the polyline and set characters in the answer matrix between them. If the polyline goes up then set slash, otherwise set backslash. To understand the solution better please paint the first test case on the paper, mark coordinates of the points and find what values to set in cycles in your program.

435D - Special Grid

Values n and m are not so large, so the solution with complexity O(max(n, m)³) should pass. It means that you should consider all triangles and check all conditions in O(1).

To make this check you should precalc arrays of partial sums on all diagonals, rows and columns. After that you could check, that there is no black nodes on the side using one sum-query.

Some hints about this problem and the implementation:

• all correct triangles are isosceles right triangles;
• either all legs or hypotenuse of the triangle is parallel to the sides of the grid;
• if you know how to solve the problem for two types of the triangles, you can get the whole solution making 4 rotates of the matrix.

435E - Special Graph

To solve this problem you have to paint different correct colorings on the paper. After it you could observe that there are two types of them: vertical and horizontal.

Vertical colorings looks like this:

acbcbd...
bdadac...
acbcbd...
bdadac...
acbcbd...
bdadac...
......

In other words, each vertical has only two colors, odd verticals have equal colors, even verticals have two others. The order of the colors on every vertical could be arbitrary.

Horizontal colorings are the same, they are rotated by 90 degrees. Of course, there are both vertical and horizontal colorings, but it doesn't change the solution.

So, you should consider every type of described colorings and check them. That is, you could choose what colors are on the verticals or what colors are on horizontals and check that obtained coloring matches the given matrix.

The solution's complexity is O(n × m).

Hi all)

Tomorrow at usual time will be held regular Codeforces round #249 for Div.2 participants. Traditionally we invite Div.1 participants to take part out of the competition.

The problems were again prepared by authors Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). As always, we express our gratitude to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

UPD: Score distribution will be standard — 500-1000-1500-2000-2500.

We wish all participants good luck, high rating and enjoyment of solving problems)

UPD2: the contest is over, we hope you enjoy it)

UPD3: link to editorial is already here)

UPD4: Congratulations to winners!:

1) JiangZemin_JiangHaha
2) Rafbill
3) Yukinoshita_Yukino
4) kuangbin9
5) spartacus

432A - Choosing Teams

In this problem you should count number of students who can participate in ACM, divide it by 3 and round down. It could be done like this:

int cnt = 0;

for(int i = 0; i < n; i++)
    if (5 - a[i] >= k)
        cnt++;

int ans = cnt / 3;

432B - Football Kit

Count for every team number of games in home kit. For team i it equals to sum of n - 1 games at home and some away games with such teams which home kit color equals away kit color of team i. To count number of such away games you could calc array cnt[j] — number of teams with home color kit j. The solution could be implemented in this wasy:

for(int i = 0; i < n; i++)
    cnt[ x[i] ]++;

for(int i = 0; i < n; i++)
{
    ans_home[i] = n - 1;
    ans_home[i] += cnt[ y[i] ];

    ans_away[i] = 2 * (n - 1) - ans_home[i];
}

432C - Prime Swaps

The solution can be described by pseudo-code:

1. Consider elements of permutation from 1 to n

2. While current element i is not sutiated on position i

3. Let the position of element i equals pos

4. Find maximum prime integer p which is less or equal than $pos — i + 1

5. Swap element in positions pos and pos - p + 1

It could be proved that such algorithm makes less than 4n swaps (for example, by implementing the algorithm)

This algorithm should be implemented optimally. You should maintain positions of elements of permutation. Swap function in author's solution:

void doSwap(int i, int j){
    int x = a[i], y = a[j];
    a[j] = x, pos[x] = j;
    a[i] = y, pos[y] = i;
    result.push_back(make_pair(i, j));
}

432D - Prefixes and Suffixes

The problem could be solved using different algorithms with z and prefix functions. Let's describe the solution with prefix function p of string s.
Calc prefix function and create a tree where vertices — integers from 0 to |s|, edges — from p[i] to i for every i. The root of the tree is 0. For every vertex v calc the number of values p[i] = v — that is cnt[v]. Then for every v calc the sum all values cnt[u] for every u in to subtree of v.

The general answer to the problem is:

Find all lenghts of the prefixes which matches the suffixes — these values are |s|, p[|s|], p[p[|s|]], p[p[p[|s|]]]... For every such length L the answer to the problem is sum[L] + 1.

432E - Square Tiling

This is popular test 6 :)

13 5

AAAAA
AAAAA
AAAAA
AAAAA
AAAAA
BBBBB
BBBBB
BBBBB
BBBBB
BBBBB
AAACA
AAABB
AAABB

The problem could be solved in a standard way — try to fill the table from the first cell to the last and try to put the miminum letter.

Consider the first row. Obviously it begins from some letters A (to be exact min(n, m) letters A). When we put some letters A in the first row, we should put several letters A in some next rows to make a square. The next letter could be only B.

Describe the solution in general. Assume that we have already considered some rows. Consider row i. Some cells in this row could be already painted. Consider unpainted cells from left to the right. For every such cell consider its color from A to Z. Two cases should be considered:

1. Put in this cell the minimum possible letter (neighbours have no such letter)

2. If the previous cell in this row was not painted at the beginning of considering row i, now it is already painted. We should try to merge the current cell with the square of the previous cell.

Choose the best case from these cases. Try to get the answer on test n = 13 m = 5 to understand the algorithm better.

Good day, codeforces)

Welcome to regular Codeforces round #246 for Div.2 participants. As always Div.1 participants can take part out of the competition.

The problems were prepared by authors Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Is not the first and definitely not the last time when we tried our best for you. Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

UPD: Score distribution will be standard — 500-1000-1500-2000-2500.

UPD2: The contest is over, we hope you enjoy it)

UPD3: the editorial is here

Congratulations to winners!:

1) PopovkinAndrey
2) FTD2009
3) Gulan14no
4) Kozakai_Aya
5) Mikael

We wish all participants good luck and enjoyment of solving problems)

413A - Data Recovery

Count min and max values in given array of length m. If the min value is less then given min or the max value is greater the given max the answer is Incorrect.

Count value 0 ≤ need ≤ 2, which equals to minimal number of elements which should be added in given array so that the min value will become min and the max value will become max. Then answer is Correct if n - m ≥ need. Otherwise answer is Incorrect.

413B - Spyke Chatting

Process all queries and count some values: for each employee we will count number of messages which weer sent by this employee and for each chat we will count number of messages which were sent to this chat. Then the answer for some employee equals to sum of messages sent to all chats in which he participates minus all messages sent by him to some chats.

413C - Jeopardy!

Firstly choose all not auction questions and answer on them. So we have only auctions. Sort them in non-decreasing order. Consider each size of suffix of auctions and answer them on their initial price and try to answer other questions by multiplying by 2.

It could be explained in this way: less than the cost value, the less you need to multiply your balance by 2. Also more than the cost value more profitable to take it for initial value.

413D - 2048

Consider some state in your game. Note that, we should maintain the maximum suffix if values in descending order. Also, we will maintain only first k - 1 powers of two and keep in mind if have already k-th power of two or greater. In fact in violation of this order we can not use these numbers because values could only increase.

So, we will count dynamic dp[i][mask][j], where i — size of considered elements, mask — mask of first k - 1 powers of two in descending order, j — do we have already the k-th power of two or greater (0 or 1). There are two possible transitions by 2 or 4. If the current element equals to 0 make both transitions.

413E - Maze 2D

We will consider queries one by one. Firstly check if the one cell of the query is reachable from the second. Find all connected components. If the cells are in different connected components, the answer is -1.

Otherwise assume that both cells are situated in columns with exactly one obstacle. To find the answer for such cells we should count the length of the path between these columns using array of partial sums.

To count this array consider all columns from left to right and store the last type of column with exactly one obstacle (down obstacle or up obstacle). If in column j the type changes set in the cell j of the array value 1, otherwise set value 0. In this case of query the length of the path between cells equals to sum of absolute differences between column indexes and counted partial sum between these columns.

If the column with the left cell has no obstacles find the nearest column with exactly one obstacle to the right. If the column with the right cell has no obstacles find the nearest column with exactly one obstacle to the left. So we get the situation considered above. Be careful if there is no columns with exactly one obstacle between given cells.

382A - Ksenia and Pan Scales

This problem is just a technic problem. So, you should take weights one by one and place the current one into the side of the scales that contains lower number of weights. At the end you should output answer in the correct format.

382B - Number Busters

In the problem you should understand, what is the structure of Artur's operation. You can see that this operation is near operation (b + x) % w (To see that just apply b = w - b - 1). There is nothing hard to get the formula of changing a during the operation. So, if you have k operations, you can see, that b = (b + k·x) % w, a = a - (b + k·x) / w, c = c - k. When you've got all the formulas, you can solve the problem using binary search.

382C - Arithmetic Progression

This problem is about considering cases:

1) If n = 1, the answer is -1. Because of any two numbers is arithmetical progression.
2) If array is constant, the answer if that constant.
3) If you have arithmetical progression initially, you can compute its difference d. In this case you should just to output minVal - d, and maxVal + d, where minVal is minimum value among a[i], and maxVal is maximum value among a[i]. But in case of n = 2, also you should check (a[0] + a[1]) / 2. If this number is integer, it is needed to be output.
4) Else, the answer has at most one integer. You find this integer you should sort the sequence, and find the place where the number is missed. If such a place exists you should add the corresponding number to the sequence, else, the answer is 0.
5) In all other cases the answer is 0.

382D - Ksenia and Pawns

In this problem from every cell except # there is one next cell. That's why this graph is almost functional graph. If this graph contains a cycle, then answer is -1 because the length of the cycle is at least two.

In the other case, there are no cycles in the graph. Let's find the longest path in it, denote is as len. Then is answer is at least 2·len - 1 because we can put the two pawns in the first two cells of this path.

But in some cases we could get the answer 2·len if there are two non-intersecting by vertices (not #) paths of length len. They are non-intersecting because if they intersect in some cell then they will be equal to the end (and the statement says that such moves are invalid).

So, we should check if the graph contains two non-intersecting by vertices (not #) paths of length len. It could be done in any way. For example, using dfs searches.

382E - Ksenia and Combinatorics

In this problem you should count trees with some properties. It can be done using dynamic programming. The main idea is that the maximum mathing in tree can be found using simple dynamic dp[v][used] (v -- vertex, used — was this vertex used in matching). So you should to count the trees tou should include in state of the dynamic values dp[v][0]$ and dp[v][1].

In other words, you should use dynamic programming z[n][dp0][dp1] — number of rooted trees with n vertices and values of dynamic in root dp[root][0] = dp0 and dp[root][1] = dp1. But in simple implementation this solution will get TL. There are two ways to get AC. The first is to opltimize code and make precalc. The second is to optimize asymptotics.

The author's solution uses the second way. To optimize solution you should mark that values dp0 and dp1 differs at most by one. That is dp0 = dp1, or dp0 = dp1 + 1. So the first dynamic becomes r[n][dp0][add]. Another optimization is there are not so many triples (n, dp0, add) with non-negative values (about 250), so you can you use lazy programming to calculate this dynamic.

Comments that describe other solutions:

http://mirror.codeforces.com/blog/entry/10423#comment-158177
http://mirror.codeforces.com/blog/entry/10423#comment-158182

Good day everybody)

Welcome to regular Codeforces round #224 for Div.2 participants, first Div2 Only in new 2014 year:). As always Div.1 participants can take part out of the competition.

The problems were prepared by authors Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). I can't already remember exactly in how many rounds I participate as author, co-author of just active assistant) Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

UPD: Score distribution will be dynamic, but the problems will be in supposed order of increasing complexity. The first dynamic round in this year)

We wish everyone good luck, high rating and excellent mood)

UPD2: the contest is over, we hope you enjoy it) the editorial is already here)

Congratulations to winners:

1) tankmagiciangirl
2) NagaiNatsuyasumi
3) lijian3256
4) TankKiller
5) dashabi

342A - Xenia and Divisors

In this problem you should guess that exists only three valid groups of three

1) 1, 2, 4

2) 1, 2, 6

3) 1, 3, 6

(You can see that integers 5 and 7 are bad).

So, we will greedy take these groups of three. If some integers will be not used, the answer is -1. In other case, print found answer.

342B - Xenia and Spies

The problem is solved by greedy algorithm. We will pass the note only in correct direction. Also, if we can pass the note at the current moment of time, we do it. In other case, we will hold it and don't give it to neighbors (we can make this action at any moment of time). Obviously this algorithm is correct. You should only implement it carefully.

342C - Cupboard and Balloons

In the problem you should carefully get formula. The optimal solution put marbles by two in a row. And then put one marble upon others if it possible. The most difficulties were to deal with this last phase.

In comments to the post were given formulas how to put the last marble (exactly in the middle). And there was a good beautiful illustration, which describes the situation.

342D - Xenia and Dominoes

In the problem you can count number of correct puzzles or substract number of incorrect puzzles from number of all puzzles. In any case you should count DP, where the state is (j, mask) — j — number of the last full column, mask — mask of the last column. This problem is equivalent to the well known problem about domino tiling or the problem about parquet.

To get the solution of the whole problem I did the following. I try to attach one domino to each of 4 directions, then paint all three cells in black and count the number of correct puzzles. But in this case you will count some solutions several number of times. So you need to use inclusion exclusion formula for these 4 directions.

342E - Xenia and Tree

The problem can be solved in different ways. The most easy idea is sqrt-optimization. Split all queries into sqrt(m) blocks. Each block we will process separately. Before processing each block, we should calculate minimum distances from every node to the closest red node using bfs. To answer the query we should update this value by shortest distances to red nodes in current block.

The solution becomes simple. Every sqrt(m) queries we make simple bfs and for every node v WE calculate value d[v] — the shortest distance to some red node from node v. Then to answer the query of type 2 you should calculate min(d[v], dist(v, u)), where u — every red node, which becomes red in current block of length sqrt(m).

Distance between two nodes dist(u, v) can be got using preprocessing for lca.

Good day)

Welcome to regular Codeforces round #199 for Div.2 participants. As always Div.1 participants can take part out of the competition.

The problems were prepared by authors Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

UPD: Score distribution is standard — 500-1000-1500-2000-2500.

We wish everyone good luck, high rating and excellent mood)

UPD2: the contest is over, hope you enjoy it)

Congratulations to winners:

1) chixianglove
2) Logvinov_Leon
3) Yoshiap
4) _moonlight

UPD3: the editorial is published here

Good day)

Soon is coming Round 1 of the All-Russian Programming Championship CROC-2013. Contestants who gain a score equal to the 400-th place finisher score or greater will advance to the Round 2 (also you need to gain positive score).

Round will be held by usual Codeforces rules (with hacks and decreasing values of the problems). During the round the problems are judged only on pretests and system testing will take place after the end of the contest. The pretests do not cover all possible cases of input data, test your programs carefully.

Before the end of the round it is strictly forbidden to publish the problem statements/solutions/any thoughts and ideas about them elsewhere. It is forbidden to talk about the problems, discuss the statements, solutions and so on.

The problems were prepared by the group of authors: Pavel Kholkin (HolkinPV), Gerald Agapov (Gerald) and Michael Mirzayanov (MikeMirzayanov). I will add that our team have already prepared for you qualification round and answered the questions during the whole competition. Traditionally thanks to Mary Belova (Delinur) for translating the problems.

UPD1: The problems are sorted by increasing of estimated difficulty. The score dustribution is decided to be not standard a little bit : 1000, 1000, 1500, 2000, 2500.

UPD2: due to the large number of participants, it is decided that it will not be able to participate out the competition. For official contest participants the round will be rated.

We wish all the participants good luck and successful advance to the next round of competition.

285A - Slightly Decreasing Permutations

As the answer you can print such permutation: n, n - 1, ..., n - k + 1, 1, 2, ..., n - k. For example, if n = 5, k = 2, then the answer is: 5, 4, 1, 2, 3. If k = 0, you should print 1, 2, ..., n. Such solution can be written in two loops.

285B - Find Marble

It is known that a permutation can be considered as set of cycles. The integer i moves to p[i] for all i (1 ≤ i ≤ n). You can start moving from integer s along the cycle. If you find integer t, then print the length of the path. If you return to s, then print  - 1.

285C - Building Permutation

The solution of the problem is rather simple. Sort all integers a and then make from integer a[1] integer 1, from integer a[2] integer 2 and so on. So, integer a[i] adds to the answer the value |a[i] - i|. The answer should be count in 64-bit type. You can simply guess why such solution is correct.

285D - Permutation Sum

For a start, describe bruteforce solution. Firstly, we will always assume, that a is identity permutation, that is a[i] = i. In this case, the answer should be multiplied by n!. Or in other way your bruteforce will not be counted. Secondly, using our bruteforce we can see, that for even n the answer is 0.

What do you also need to get accepted? First case is to calculate answers for all n on your computer and write them in constant array. In other words you can make precalc. Second case is to make you solution faster. The soltuion using meet-in-the-middle idea works fast for n ≤ 15. If you remember that for even n answer is 0 then you can get accepted using such solution. But other simple bruteforces and dynamic programmings on maps work slower than 3 seconds.

285E - Positions in Permutations

Good day, friends)

Welcome to regular Codeforces round #175 for Div.2 participants. Traditionally Div.1 participants can take part out of the competition.

The problems were again prepared by the group of authors: Pavel Kholkin (HolkinPV), Artem Rakhov (RAD), Fefer Ivan (Fefer_Ivan) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

Score distribution is published in advance) today it is standard: 500, 1000, 1500, 2000, 2500.

We open the little secret of this competition, in all today's problems you find permutations)

We wish everyone good luck, successful hacks, high rating and good mood)

UPD1: the contest is over, hope you enjoy it)

UPD2: the tutorial is already published here)

UPD3: congratulations to winners:

1) hechuan
2) TroyI118
3) BekzhanKassenov
4) ahmed_aly
5) lxgsbqylbk

Hello, friends)

Soon is coming regular Codeforces round #171 for Div.2 participants. Traditionally Div.1 participants can take part out of the competition.

Again and again the problems were prepared by the familiar group of authors: Pavel Kholkin (HolkinPV), Igor Kudryashov (Igor_Kudryashov), Nikolay Kuznetsov (NALP) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

UPD: score distribution will be not standard a little bit: 500, 1000, 1500, 2000, 2000.

We wish everyone good luck, successful hacks, high rating and good mood)

UPD2: the contest is over, we hope you enjoy it)

Congratulations to winners:

1) study_english
2) ipip2005
3) rng_50216
4) bfrcns197
5) csavky103

UPD3: the editorial will be published soon

Good day, friends)

Soon is coming regular Codeforces round #166 for Div.2 participants. Traditionally the others can take part out of the competition.

And again the problems were prepared by the group of authors: Pavel Kholkin (HolkinPV), Nikolay Kuznetsov (NALP), Rakhov Artem (RAD) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

UPD: Score distribution will be not standard a little bit — 500, 1000, 1500, 2000, 3000.

We wish everyone good luck, successful hacks and high rating)

UPD2: the contest is over, we hope you enjoy it)

Congratulations to winners:

1) xrvpud221
2) xyz111
3) nanoha
4) wyx528
5) GuyUpLion

UPD3: the editorial is published, you can find it here

266A - Stones on the Table

In this problem you should count number of consecutive pairs of equal letters. It can be done using one cycle and O(N) time.

266B - Queue at the School

In this you should realize the given process. You should t times swap elements i and i + 1 if on the place i was a girl and on the place i + 1 was a boy. You should not push some girl to the left multiple times at once. The solution can be written using O(N·T) time.

266C - Below the Diagonal

This problem can be solved using constructive algorithm. We will use inductive approach. At first, we have matrix of size n and n - 1 ones in it. Therefore, there is a column with no ones in it. So, we put this column to n-th place. In this case, the lower right element will be 0. Then find any row with at least one integer one and put it to the n-th place.

After these operations the element in cell (n, n) equals to 0 and the last row has at least one integer one. Therefore, we can reduce the dimension of our problem, that is n:  = n - 1. In our new problem we have no more than n - 2 ones. So, we can solve this problem using the same algorithm. When n equals to 1 you should finish algorithm, because there is no ones left. This algorithm uses O(N) swap operations, no more than two for every n.

266D - BerDonalds

I'll tell a few ideas how to solve this problem. Firstly, describe the solution with time O(N⁴). Consider every edge (u, v) of length len where could be the answer point. Let this point lie at a distance x from vertex u. So, the distance from this point to vertex i would be min(x + d[u][i], len–x + d[v][i]), where d[x][y] — distance between vertices x and y. Equate these values and get the critical value x for vertex i, x = (len + d[v][i]–d[u][i]) / 2. It follows that the answer to the problem is half-integer. So, for every edge and every other vertex we get set of critical points. We should check them all include the vertices of the graph (ends of the segments). This solution may probably pass with some optimizations.

Another solution with complexity O(N³·log²). Multiply all weights by 2. Consider every edge where should be the answer and make binary search for the answer (in integers). To check some current value you should consider every vertex i and assume that the answer is achieved in this vertex. In this case, the answer point must lie on this edge <= some value l[i] or >= some value r[i]. This subproblem is solved using offline algorithm using sorting events and maintaining the balance.

Also, you can use ternary search on every edge of the graph. But you should divide every edge on several segments and find the answer on every segment, because the ternary search is incorrect in this problem.

The last two solutions can provide accepted, if you realize them carefully. Also note, that there is the solution with complexity O(N³) by the author RAD.

266E - More Queries to Array...

This problem can be solved using data structure. We would use segment tree, we will support k segment trees for every power. At every vertex we will calculate weighted sum of the appropriate power, also we will save some number that indicates the color of the whole segment, if any.

User Egor in comments to the post and user mexmans in comments to the tutorial tell their formula to get the answer. I try to describe how to get them by yourself. Firstly, you should write what value your segment tree gives. The tree can calculate the sum . You need to calculate the sum , you can write it also as . Then you should write the last sum for some first powers (at least three) (at piece of paper) and subtract the second sum (what you need) from the first sum (what your tree can calculate). You get an expression that describes what should be subtracted to get the answer from the value what you tree can calculate. This is just the Newton binomial without the highest power.

So, the answer for power j is expressed as the subtraction of the value of query to your segment tree and the Newton binomial, with all powers that are less than j (these values can also calculated using your segment tree). Partial sum of the powers and binomial coefficients can be precalced. The solution has the complexity O(N·K·log(N)).

Hello everybody)

Today is coming regular Codeforces round #163 for Div.2 participants. Traditionally the others can take part out of the competition.

The problems were prepared by authors: Rakhov Artem (RAD), Kudryashov Igor (Igor_Kudryashov), Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating the problems.

UPD: It is decided to use dynamic scoring system. The problems will be sorted from low difficulty to high by authors' opinion.

We wish everyone good luck and high rating)

UPD2: the contest is over, hope you enjoy it)

Congratulations to winners:

1) Aharon

2) marcoskwkm

3) ChaosLogic

4) Imsbuno

5) Conny

UPD3: the editorial can be found here)

Hello everybody)

Today is coming regular Codeforces round #161 for Div.2 participants. Traditionally the others can take part out of the competition.

The problems were prepared by authors: Pavel Kholkin (HolkinPV), Nikolay Kuznetsov (NALP) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating the problems. Also thanks to Rakhov Artem (RAD) and Vitaly Aksenov (Aksenov239) for their help.

UPD: Today it is decided to use dynamic scoring system. But the problems will be sorted from low difficulty to high by authors' opinion!

We wish everyone good luck, successful hacks and high rating!

UPD2: the contest is over) hope you enoy it

Congratulations to winners:

1) poao900
2) persianpars
3) Sert
4) valentin.harsan10
5) MeinKraft

UPD3: the tutorial is published, you can find it here

260A - Adding Digits

At first try to add to the right one digit from 0 to 9. If it is impossible write -1. In other case, the remaining n–1 digits can be 0 because divisibility doesn’t change.

260B - Ancient Prophesy

In this problem you have to consider every date from 2013 to 2015 year (there is no leap years in this interval), count occurrences of this date and find maximum. In one year there is 365 days, so the complexity of the solution (3·365·N).

260C - Balls and Boxes

Firstly describe simple solution. We will get by one ball from boxes (we begin from box x) from right to left (action back). At some moment there will be 0 balls in current box. This box is the first box in our initial problem (from which we took all balls and begun to put). In this box we put all balls, which we get from all boxes.

But we can’t solve the problem in such a way, because it is too long. Note, that before we meet the situation when in some box will be 0 balls, we will go through every element of array several times and subtract 1. So we can make our solution faster. We can subtract from every element of array minv - 1, where minv — minimum in array. After that you should do O(N) operations, that were mentioned above.

260D - Black and White Tree

The problem can be solved constructively maintaining the following invariant (rule) — the sum of the white vertices equals to the sum of the black vertices. The tree is a bipartite graph, so we build bipartite graph with no cycles, which will satisfy the conditions of the problem. Parts of graph will be black and white vertices.

On each step we will choose vertex v with minimum sum from white and black vertices. Then find any vertex of opposite color u and add edge (u, v) with weight s[v], and subtract from sum of u sum of v, that is s[u] = s[u]–s[v]. After each step one vertex is deleted. That’s why there will be no cycles in constructed graph. When we delete last vertex of one of colors, all other vertices can be joined in any correct way with edges of weight 0.

260E - Dividing Kingdom

Consider 9! variants of location of integers a[i] on 9 areas. When we consider some location (some grid), we can easily find amount of cities to the left of the left vertical line, to the right of the right vertical line, below the lower horizontal line and above the upper horizontal line. All these numbers is sum of three values a[i].

We assume that the lines of the answer are always in half-integer coordinates. Then, knowing the above 4 numbers, we can uniquely determine separately for x and y how to accommodate all the 4 lines. It remains only to check that in all areas there is desired number of points.

For each of four zones (to the left of the left vertical line, to the right of the right vertical line, below the lower horizontal line and above the upper horizontal line) separately check, that all three areas have correct number of cities. It can be done offline using scan-line and segment-tree, which can find sum on interval and change value in some point. You should put all queries in some array, sort them and process from left to right. Note, when you check 8 from 9 areas for every 9! variants of location, the last area (central) could not be checked, it will be correct automatically.

Welcome, friends)

New year is coming and meanwhile we are glad to introduce you regular Codeforces round #158 for Div. 2 participants, may be the last in this year). Traditionally Div. 1 participants can take part out of the competition.

Today's problems were prepared by authors: Nikolay Kuznetsov (NALP), Fefer Ivan (Fefer_Ivan), Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

Score distribution will be standard.

We wish everyone successful hacks, high rating and happy new year!

UPD: the contest is over, we hope you enjoy it)

Сongratulations to winners:

1) ballmaids01
2) betalife37
3) showtime
4) vlyubin
5) bardek

UPD2: the tutorial is published, you can find it here)

246A - Buggy Sorting

In this problem you should hack the sorting algorithm, of course it was incorrect. It was correct only for arrays with n <  = 2. In other cases you could print n, n–1, ..., 1 as a counter-example. To make the sorting right, the second cycle should be from 1 but not from i.

246B - Increase and Decrease

Note, that you can always get the answer n–1. To get this result you should make first n–1 equal using the last element as the second element in pair of given operation. But after it, the whole array could become equal. It could happen if the sum of array’s elements is divisible by n. So the answer is n–1 or n.

246C - Beauty Pageant

This problem was rather mathematical. The correct solution is: firstly take every element once, then take the maximum and any other, then two maximums and any other, then three maximums and any other and so on. In this case, you get as many sets as you need in this problem. It is easy to check, that all sums will be different.

246D - Colorful Graph

This problem could be solved in this way: create new graph where vertices are the colors of the given graph. The edge between vertices u and v belongs this new graph if there are two vertices a and b in the given graph such that c[a] = u and c[b] = v. So, the answer is such color k with minimum number, that the degree of the vertex k in the new graph is maximum (without multiple edges). Such solution could be written using O(M·log(N)) time.

246E - Blood Cousins Return

This problem had little in common with problem 208E - Blood Cousins. In comments to this problem there was given a solution using structure deque (array in which you can add or delete elements from both endings). Let’s describe solution using this structure.

Firstly all different names change with different integers and for every vertex v save all queries with this vertex. Then for every vertex, which is root of some tree make dfs, the parameters of dfs are vertex v and deque <set > z. This deque for every depth i of the subtree of v save set — all different names (integers) on depth i.

This deque could be calculated simply. Consider all sons of v and calculate such deque for them. Obviously, the size of our deque z will be maximum of sizes of descendants’ deques. Then consider every descendants’ deques and merge appropriate sets of integers. Of course, we will merge smaller set to a larger set. After that you should insert to the beginning of deque z the set of size 1 — color of vertex v.

After this, you can at once answer all queries of vertex v. Answer is 0 if v has no descendants on the depth k or the size of z[k]. It is known that such method has good asymptotic, the author’s solution works about one second. The asymptotic is O(N·log²(N)).

The solution should be realized carefully. You must not copy every element of your set or deque. You should do swap of smaller and greater set or deque without copying elements ant than merge smaller to greater.

Welcome, dear friends)

We are glad to introduce you regular Codeforces round #151 for Div.2 participants. Traditionally the others can take part out of the competition.

Today's problems were prepared by authors: Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

Score distribution will be standard.

We wish everyone good luck, successful hacks and high rating!

UPD: the contest is over, hope you enjoy it)

Congratulations to winners:

1. a58 (he solved all 5 problems)
2. thangpc
3. Minecraft
4. xiaoshua3
5. Noskov

UPD2: you can find the editorial here

228A - Is your horseshoe on the other hoof?

In this problem you should count different numbers from input cnt and print 4–cnt. You could do it in different ways. For example, you could use set.

228B - Two Tables

In this problem you should carefully consider every shift  - N <  = x, y <  = N, count the answer and find the maximum value. The complexity of solution is O(N⁴).

228C - Fractal Detector

This problem could be solved using dynamic programming. State z[x][y][st][mask] means if the square with upper left corner (x, y) is fractal with nesting level st and colors mask. The value z[x][y][st][mask] is 0 or 1. There are O(N²·Log(N)·2⁴) states in this dynamic programming.

The transitions from state to state are rather simple. If st = 1 you should fairly check that the square 2*2 with upper left corner (x, y) matches colors of mask. If st > 1 you should divide the square into four parts and check them separately. If the value in mask in one quarter means black color, you should check that the whole quarter is black. It could be done using partial sums on rectangles using O(1) of time. If the quarter is white, you should check that it is a fractal with nesting level st - 1 with the same mask. So, there are less than 4 transitions from every state.

To get the answer to the problem you should consider every upper left corner of squares, every mask and every nesting level of fractal and check this square. It is done using your dynamic.

228D - Zigzag

In this problem we will use that sequence s is cyclic because of its structure. Also, it is important that 2 <  = z <  = 6. For every z we will write the sequence s and note that its period is 2 * (z–1).

So, for every z and modulo 0 <  = mod < 2 * (z–1) we will build separate segment tree or Fenwick tree. You should be careful with memory, it needs O(Z·(2·Z)·N) of memory. So, if the query is to update some value, we should update z values of trees with correct modules. If the query is to find sum, we should consider every 2·(z–1) modules, count the sum and multiply by correct coefficient from sequence s. The complexity is O(Z·N·Log(N)).

228E - The Road to Berland is Paved With Good Intentions

This problem can be solved in different ways. It was expected the solution that solved the system of modular equations using Gauss algorithm. Here is another simple solution.

The vertices from the result call switched-on. Firstly, note that every vertex should be switched-on no more than once. Then, consider every edge (x, y) of color c. We want to make its color 1. So, if c = 1 we should switch on vertices x and y or don’t switch them on simultaneously. If c = 0 we should switch on x or y. So, consider some vertex v and try to switch it on or not. Thus, we can uniquely determine the state of every vertex of the same connected component as v. If we face some collision, we can’t get the solution, you should print Impossible. The solution can be realized using bfs with complexity O(N + M).

Welcome, friends)

We are glad to introduce you regular Codeforces round #141 for Div.2 participants. But traditionally the others can take part out of the competition.

Problems are prepared by command of authors: Pavel Kholkin (HolkinPV), Ivan Fefer (Fefer_Ivan), Igor Kudryashov (Igor_Kudryashov) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces system and Mary Belova (Delinur) for translating problems.

Score distribution is standard.

We wish you good luck, successful hacks and high rating!

UPD: the contest is over, hope you enjoy it) Congratulations to winners:

1) AntiFate

2) alicechennan

3) honeyofsistercha

4) Fride

5) bla_bla_bla

UPD2: the editorial was already published, you can find it here