250A - Paper Work. For every folder you should take reports as much as possible. In other words, you should stop forming a folder either before the third bad report or in the end of sequence. You can easily prove that this strategy is optimal. This solution works in O(n).

Author is MikeMirzayanov

.

Adiv2. Consider an array A of integers in range from 1 to nk. Let's remove from A all numbers a_i and all other numbers store into an array B. The array B will have (n - 1)k elements. Now for i-th kid you should output numbers a_i, B[(n - 1) * (i - 1) + 1], B[(n - 1) * (i - 1) + 2], ... B[(n - 1) * (i - 1) + n - 1] (B is 1-based).

Author is Gerald

Hi all!

That's the 150th (anniversary?) Codeforces Round. For the 1st and the 2nd divisions both.

Round is prepared by Ripatti , Gerald , Delinur .

Enjoy!

UPD. Points are standard: 500-1000-1500-2000-2500 for both divisions.

UPD2. Contest complete. Cheaters are deleted. Ratings are updated.

Div1 winners:
1. scottai1
2. vepifanov
3. rng_58
4. Egor
5. Komaki

Div2 winners:
1. mochavic
2. hanamaki
3. mfv
4. shef_2318
5. TangJie

Thank you for your participation. Come again.

Editorial will be tomorrow.

UPD3. Editorial. Sorry for delay.

A. You should iterate over all dices from up to down and restore answer. You can easily find number of the bottom side of the 1st dice. Using known sides of the 2nd dice you can find pair of numbets on top and bottom side of the 2nd dice. If one of them equal to number on bottom of the 1st dice, you can restore all numbers on the 2n dice. Then using this idea you can try restore numbers on the 3rd dice and so on. If you restored all numbers, you should write YES. If for some dice you cannot uniquely determine order of numbers on the top and botton sides, there will be at least 2 placing of numbers. In this case you shoyld write NO.

Author is Ripatti .

B. Firstly you should generate all k-bonacci numbers less than n. For k ≤ 32 you can do it straightforward, for bigger k you can see that all k-bonacci numbers less 10⁹ are powers of two only (and 0). So you will have no more then 100 numbers.

Then you should use greedy algo. You should substract from n maximal possible k-bonacci numbers. You should repeat this operation while n is not decomposed. And in the end you will have answer.

Why all numbers will be different? One of possible proves:

F(k, n) = F(k, n - 1) + F(k, n - 2) + ... + F(k, n - k)

F(k, n - 1) = F(k, n - 2) + F(k, n - 3) + ... + F(k, n - k - 1)

You can substract the 2nd equation from the 1st one and you will recieve F(k, n) + F(k, n - k - 1) = 2F(k, n - 1), that equal to 2F(k, n - 1) ≥ F(k, n). This unequation also holds for n ≤ k.

Suppose than greedy also constricted 2 equal numbers F(k, x) in decomposition. But then in virtue of unequation we should take number F(k, x + 1) insead these 2 numbers. Сontradiction.

But you didn't need prove than greedy algo works, you might believe that it works:)

Authors are Gerald , Ripatti .

C. Firstly you should calculate number of white and black pixels in every column. After that you should calculate number of white and black pixels for every prefix in sequence of columns. Now you can calculate number of black or white pixels in every vertical line of any width in O(1).

Now you should use dynamic programming. Let's dp[i][j] will store numbers of repainted pixels in prefix from the 1st column to the j-th and color of the last column will be white for i = 0 and black for i = 1.

Than you can recalculate dp using forlulas: dp[0][0] = dp[1][0] = 0

Answer will be min(dp[0][m], dp[1][m]).

This solution works in O(nm + m * (y - x)).

Author is Ripatti .

D. There is just BFS. State is head place and mask that store place of tail: using 2 bits you can code position of every segment in relation to previous segment. Mask will contain no more than 16 bits, and number of all states will be no more than 4⁸ × 15 × 15 (also you can try understand that number of states no more than 3⁸ × 15 × 15).

Then you should just carefully implement it.

Author is Ripatti .

E. You have z = [x / 2] + y + xy. That is equivalent to

z = [2k / 2] + y + 2ky, where x = 2k, k > 0
or
z = [(2k + 1) / 2] + y + (2k + 1)y, where x = 2k + 1, k ≥ 0.

z = k + y + 2ky, k > 0
or
z = k + y + (2k + 1)y, k ≥ 0.

Still more steps:

2z + 1 = 2k + 2y + 4ky + 1, k > 0
or
z + 1 = k + 2y + 2ky + 1, k ≥ 0.

2z + 1 = (2k + 1)(2y + 1), k > 0
or
z + 1 = (2y + 1)(k + 1), k ≥ 0.

From the 2nd equation you can see than z should be 2^t - 1 because otherwise z + 1 will have odd divisor and we can build solution. From the 1st equation you can see that 2^t + 1 - 1 should be prime, otherwise we also can build solution. If z = 2^t - 1 and 2^t + 1 - 1 is prime, obliviously there are no solutions.

Prime numbers like 2^a - 1 are Mersenne primes. Only about 46 such numbers are found now. Powers of 2 for the firts 40 numbers you can find for example here.

Author is Ripatti .

Hello everyone!

That is Codeforces Round 139 for the second division only. Members of the first division can participate out of competition.

Round is prepared by Ripatti , Gerald , Delinur.

We will use dynamic score system. Problems will be ordered in order of expected increasing difficulty.

Good luck!

UPD. For technical reasons round delays in 15 minutes.

UPD2. Testing is complete. Winners:
1. wccy
2. ttl
3. shubhanshu
4. Atarashi_Ako
5. dvylfz921

2 members solved all 5 problems.

English editorial will be tomorrow. You can try to understand russian editorial.

UPD3. English editorial.

A. For solving this problem you might find some formula like
res = abc - (a - 1)(b - 1)(c - 1), res = ab + bc + ca - a - b - c + 1, or something else.
Also the problem can be solved in O(a + b + c) time — you can move from the top line to the bottom line of hexagon and sum number of tiles in every line.

Author is Ripatti .

B. You can build some graph where vertices are students and edges are enmities. You should drop some vertices and then paint them in two colors. Any edge should connect vertices of distinct colors and numbers of vertices of every color should be same.

You can see that graph consists chians, cycles and sepatated vertices. Every of that component can be painted in 2 colors except one case: cycles of odd length. So, you should drop one vertex from every odd cycle. After that you can get odd number of vertices. Then you should drop one more vertex (you can chose any of them). The obtained graph can be easily painted in 2 colors in the required manner.

Authors are Gerald , Ripatti .

С. The first solution: analysis of the cases
1. k = 1. For n ≤ m + 1 3 employees is enough (in most cases). For n > m + 1 answer is 2. Also, there are only one tricky corner case: for n = 2, m = 2, k = 1 answer is 4.
2. k > 1. If n = m, answer is 2k + 1, otherwise answer is 2k.
For any case it is easy to construct solution, and prove that this solution is optimal.

The second solution: greedy.
Let's create an array where we will store current number of employees for some number of the first days. Now you should iterate over all days from the first to the n + m-th and hire employees every time when it needed. You should hire workers if there are less than k people in the current day; also you should hire worker if there will be no people tomorrow (thet worker will bring the key to the workers that will work tomorrow).
This solution works in O((n + m)k).
This solution also works correctly for cases n < m, but then it has bigger complexity and requires more time.

Authors are Gerald , Ripatti .

D. For every sector you should sort bridges in order of increasing distance from the conter of the web. Now for every sector you should iterate over bridges of the current sector and two adjacent sectors using 3 pointers. During every pass you should carefully calculate number of bad cells. That is all solution.

Solition in , where m is total number of bridges.

Author is Ripatti .

E. Digital root of number is equal to that number modulo k - 1 for most cases. It is lie only for digital roots 0 and k - 1 — in that cases number modulo k - 1 will be 0. But you can get digital root 0 only for numbers like 00...00. Total number of numbers that type you can find using any other way. So, now you can find number of substrings that have some digital root, if you know number of substrings that equals some number modulo k - 1.

How to find number of substrings of some modulo? You should iterate over all digits of s from the left to the rigth and for every modulo store number of prefixes of that modulo in some array dp[] of size k. Let's current position is i. Then number of substrings modulo b that ends in position i equals to number of prefixes leftmost position i that have modulo (x - b)mod(k - 1), where x is modulo of s[1... i]. I.e. just dp[(x - b)mod(k - 1)].

To fit into memory limit, you should replace array dp[] by some associative array. For example, std::map from С++ or some hashtable.

So we have solution in O(nz), where z is complexety of access to dp[] ( for std::map and O(1) for hashtable).

Author is Ripatti.

Hello everyone.

That is the 133th Codeforces round. Specially for the 2nd division. Contestants from the 1st division can solve the round out of competition.

Round is prepared by Ripatti , Gerald , Aksenov239 , Delinur and MikeMirzayanov .

The round will use dymanic scoring system. Problems will be ordered in random manner (see UPD1). If you want get more happiness from solving that round, please, read statements of all problems.

Good luck!

UPD1. Jury members discussed and have decided to rearrange problems in expected order of difficulty.

UPD2. Contest ended. Winners:
1. karensun522
2. stostap
3. sisterX
4. BiliBili
solved all 5 problems. Congratulations!

Editorial will be soon tommorow (I am very tired =_=, but now you can try to read russian editorial here).

UPD3. Editorial in English.

Div2 A. You can just output "0 0 n".

Author is Alex_KPR

Hello everyone!

There is yet another Codeforces round. Now it is the 5³-th one.
The round will run for both divisions by classic rules of Codeforces format.

Points are standard: 500-1000-1500-2000-2500.

Round was prepared by Ripatti , Alex_KPR , Gerald , Aksenov239 , RAD , Delinur .

Good luck!

UPD. Round is ended.
Winners of div1:
1. Petr
2. tourist
3. SergeyRogulenko
4. bmerry
5. UESTC_Nocturne

Winners of div2:
1. gflegar
2. mylyanyk.ivan
3. arbesfeld

Petr is only who solved all 5 problems in the first division. No one solved all 5 problems in the second division.

UPD. Editorial.

A div2. Required row is row that have only one star inside. Requred column is comumn that also have only one star inside. So, you can iterate over all rows/columns, calculate number of stars inside them and find the answer.

Authors are MikeMirzayanov, Gerald

Hello everyone!

Today is the second round of the Open Moscow Programming Championship By CROC will be. Start is planned at 19:00.

Competition will happen by usual rules of Codeforces, with hacks and score falling in process of time. All contestants who passed score no less than contectant of the 300-th place in the Round 1, can participate in the Round 2. Every other contestants can patricipate the Round 2 out of competition. Specially for contestants of the second division we prepared more easy unofficial problemset. The official problemset and the unnoficial one have some common tasks.

Round will be rated for all participants.

Some number of problems are waiting you. They are roughly ordered by the increasing complexity. Score distribution is standard for both divisions (500-1000-1500-2000-2500). Don't forget that during contest your solutions will be tested on a small set of pretests. Testing on full testset will be after end of the round. Pretests can don't cover all cases of input data, so you should test your solutions very carefully.

It is strictly forbidden to publish statements/solutions of the problems before round will be end. Also you shouldn't to talk about problems, discuss some things about possible solutions of them. Let's be honest! You can discuss problems after the end of round.

Top 50 contestant will be allowed to the Final Round. Also all contestant with score not less than score of the 50-th contestant will be passed.

The round was prepared by Ripatti, havaliza, Gerald, RAD, MikeMirzayanov, Delinur.

Good luck for all!

UPD. We remind that the final of the Open Championship of Moscow and Moscow Region Programming (CROC) take place on April 27 in the office of the CROC. Note that CROC does not pay for the road and residence of the finalists. All participants must arrive at the final in the office of the CROC (Moscow) in the morning on April 27.

After the competition all participants will be provided to fill the form on the ability to participate in the finals of the competition. The first 50 participants on the results of the competition, which will confirm their participation in the finals, will be invited to final competition. You can confirm participation in the finals during the day after the end of Round 2.

It is recommended to fill the form, regardless of your results in Round 2, as large number of participants can reject the participation in the final.

A. Naive solution in O(n) (some simulation all of n rounds) gets TL. Let's speed up this solution. Let's consider rounds on segments [1..mk], [mk+1..2mk], [2mk+1..3mk] and so on. You can see that results of games on these segments will repeat. So you can simulate over exactly one segment and then take into consideration them [n/(mk)] times ([x] is rounding down). Remainder of n%(mk) last rounds you can simulate separately. So you have O(mk) solution that easily fits into time limits.

Authors are Ripatti and Gerald

div2 A. In this problem you should find length of polyline, multiply it by k / 50 and output that you will recieve. Length of polyline is sum of lengths of its segments. You can calculate length of every segment using Pythagorean theorem: .

Hello everyone!

I am glad to welcome you on today round of Codeforces. I hope that recent color revolution and a more later time for start of round will make some variety into process of solving problems:)

An author of today problems is me. RAD helped me to prepare this round, Delinur translated statements into English.

Good luck.

UPD.

The round ended, ratings was updated.

Winners of div1:

1. Egor

2. tourist

3. unicef

4. sevenkplus

5. ivan.popelyshev

Winners of div2:

1. RainbowDash

2. cjtoribio

3. miraliv

4. adrian.jaskolka

5. majia5

Yippee!

A. (link) Solution of this problem is written in the fourth paragraph of the statements. You should carefully read and implement it. Only one difficult part is how to to determine which card has higher rank. You can for every card iterate over array [ '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A' ] and determine numbers of ranks in this array. Finally, just compare them.

Good evening.

Today's round is mine, as the previous one. This round will be for participants of the second division. Participants of the first division can take part in the round out of competition.

RAD, Connector, it4.kp and MikeMirzayanov helped me to prepare this round. Delinur translated statements into English.

Contest will be in the good old tradition of Codeforces. No any innovations, pretty short and clear statements.

Points for problems are standard: 500-1000-1500-2000-2500.

Good luck everyone!

UPD. Round was ended, ratings was updated.

Winners:

1. tsundere

2. jte

3. abacadaea

4. ltaravilse

5. Billy_Herrington

A. (link) In this problem you should do just that is written in the statement. At the first you should read all skills and multiply all levels of them by koefficient k. Next you should drop all skills which have level less than 100. After that you should add all new skills from the second list but only those thah are not present in the second list. At the end you should sort all skills by thier names and output them.

Hello everyone!

I am the author of problems of today round. RAD, Connector, it4.kp helped me to prepere this contest. Delinur thanslated statements into english.

It will be a thematic contest. And the theme is Disgaea.

Etna, Laharl and Flonne - main characters of the game

A naive solution works in O(nmk). This solution stores all the start positions into an array and next iterates over all commands and shifts positions in needed directions. After every move it checks that all positions lie on the exit cell.

This solution doesn't fit into time limits.

An author's solution speed up the naive solution with using of bit masks.

A div2. In this problem you can simulate the process. You can consider all minutes and in dependence by a color of a current cablecar decrease size of corresponding group of students G by min(|G|, 2), where |G| is size of the group. After that you should determine the first minute t in that all three groups of students will be empty. So t + 30 is an answer. This solution works in O(r + g + b).

Hello everyone!

I am an author of problems of today round. This round is for both divisions. There will be 7 problems, the first 5 of them are for the second division and the last 5 are for the first one.

About points of problems. Today they are nonstandard:
for div2: 500-1000-1500-2000-2000
for div1: 500-1000-1000-1500-2500
Be careful.

RAD helped me for preparing the round. Delinur translated statements into English.

Good luck ans have fun.

UPD.
 winners of the first division
1. peter50216
2. tourist
3. ACRush

winners of the second division
1. iamcs1983
2. zyx3d
3. seanwupi

Editorial.

UPD.
Unfortunately, in author's solution of priblem E some bug was found. We thanks participant LinesPrower for detection of it. Author's solution was updated and all solutions were rejudjed. Ratings will be recalculated for all participants excluding Egor and Jacob. We apologize for this incident.

A. You should count a number of vowels for every of three phrases. Next, you should compare this numbers with numbers 5, 7 and 5. If all is matched, answer is YES, otherwise answer is NO.

Author of problem is Ripatti.