First, arrange the problems in order of their difficulties. The authors assume such order: A, D, B, C, E. Now make the tutorial of problems in their order in the contest.

208A - Dubstep

This problem was technical. First, you should erase all occurrences or word WUB in the beginning and in the end of the string. And then parse the remaining string separating tokens by word WUB. Empty tokens should be also erased. Given string was rather small, you can realize the algorithm in any way.

208B - Solitaire

In this problem you could write breadth-first search. The state is the following four elements: number of remaining piles and three strings — three rightmost cards on the top of three rightmost piles. We have two transitions in general case. We can take the rightmost pile and shift it left by 1 or 3 on another pile. If the number of remaining piles become 0 at some moment print YES, else print NO. The number of states is O(N⁴), the number of transitions 2, so the complexity of solution is O(N⁴).

208C - Police Station

In this problem we will find the sought quantity for every vertex and find the maximum value. For this for every vertex v count two values: cnt1[v] and cnt2[v] — number of shortest paths from vertex v to n-th and 1-st vertices respectively. For this you should construct graph of shortest paths and use dynamic programming on the constructed graph (because the new graph will be acyclic). To construct the graph of shortest paths you should leave only useful edges in original graph. It can be done, for example, using breadth-first search launched from vertices 1 and n respectively.

After values cnt1[v] and cnt2[v] are found consider every useful edge (u, v) and add to vertices u and v value (cnt2[u] * cnt1[v]) / (cnt2[n–1]), which is the contribution of this edge in the sought quantity for the vertices u and v. Note that value (cnt2[n–1]) is the number of shortest paths between 1 and n. All said values can be found in time O(N + M). The complexity of solution is O(N + M).

208D - Prizes, Prizes, more Prizes

In this problem every time you get points you should greedily get as much prizes as you can. For this, consider every prize from the most expensive and try to get as much as you can. If we have cnt points and the prize costs p points you can get prizes. So we get simple solution with complexity O(5 * N).

208E - Blood Cousins

In this problem you have some set of rooted down- oriented trees. First, launch depth-first search from every root of every tree and renumber the vertices. Denote size of subtree of vertex v as cnt[v]. In this way all descendants of vertex v (including v) wiil have numbers [v;v + cnt[v]–1].

Then we wiil handle requests (v, p) in their order. First, go up from vertex v on p steps to the root using binary rise like in LCA algorithm. Denote this vertex u. If u doesn’t exist print 0 else you should count the number of descendants of vertex u on the same height as vertex v.

For this write all numbers of vertices for every height in some array. Then you should determine which of these vertices are descendants of u. You can do it using binary search in corresponding array. Find the segment of appropriate vertices (because we know the numbers of all descendants of u), find the amount of them, subtract one (vertex v), and this is the answer. The complexity of the solution is O(Nlog(N)).

Welcome, friends)

We are glad to introduce you regular Codeforces round #130 for Div.2 participants. Everyone can traditionally participate in it. There were some problems with registration of Div.1 participants, but now everything is alright)

Problems are prepared by command of authors: Pavel Kholkin (HolkinPV), Nikolay Kuznetsov (NALP) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces system and Mary Belova (Delinur) for translating problems. Also thanks to Alexander Kouprin (Alex_KPR) and Pavel Kunyavskiy (PavelKunyavskiy) for their help.

And again score distribution will be dynamic) More information you can find here.

Note that all problems will be given in random order.

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

UPD: the contest is over, no matter what, we hope you enjoyed the competition

UPD2: The authors apologize for the situation with the problem E. The problem has affected a small number of participants from div2 (22 participants) and the solution of original version of the problem doesn’t differ a lot (in most solutions is sufficient to remove a couple of lines, solutions become more simple). Therefore, it was adopted the following decision:

• for all 22 participants,who has problems with problem E and will have decrease of rating, the round is unrated.
• for everybody else the round is rated

UPD3: after recalculation it was found that there are 20 such participants, not 22

UPD4: unsuccessful hacks, which answers differed from the correct whitespaces, are decided to ignore

UPD5: tutorial can be found here

195A - Let's Watch Football

The whole video will be downloaded in all = (c·a + b - 1) / b seconds. In this problem you can choose every 1 <  = t <  = all as an answer. To fulfill coditions of the problem it is enough to check the condition t0·b >  = (t0 - t)·a at the moment of time t0 = all.

195B - After Training

In this problem you should carefully implement the given process. Firstly note that ball number i > m will be in the same basket as ball number i - m. Therefore it is enough to distribute first m balls. It can be done using two pointers lf, rg from the middle. Alternately put one ball to the left and to the right and shift pointers. In only case you should shift left pointer twice in the first moment of time if m is odd.

195C - Try and Catch

In this problem you was to implement what was writen in the statement. In my solution I did the following. Erase all spaces from the text except spaces in messages in try-catch blocks. Then when we get word "try" we put number of the new try-catch block in stack. When we get word "throw" we remember it's type and current state of stack (that is what try-catch blocks are opened). For example, put these number in set. When we get word "catch" if it's type equals to type of operator "throw" and the number of current try-catch block is in your set then write the answer now else erase this try-catch block from stack. If there was no suitable try-catch block write "Unhandled Exception".

195D - Analyzing Polyline

Tutorial by author Igor_Kudryashov

In fact in this problem we were given lines y_i = k_i * x + b_i but negative values were replaced by zero. Your task was to find the number of angles that do not equal 180 degrees in the graph s(x), that is the sum of the given functions.

Firstly note that sum of two lines is also line. Indeed y = y₁ + y₂ is y = k₁ * x + b₁ + k₂ * x + b₂ = (k₁ + k₂) * x + (b₁ + b₂).

Consider points where y_i = 0, that is x_i =  - b_i / k_i. While we assume that k_i doesn't equal to 0. Then line number i is divided in two lines one of which identically equals to 0. Consider all different points x_i and sort them. Then, obviously, the sum of the given functions between two consecutive points is line. Find the equation of the line. Assume that we consider point i from the left. Then equation of the line between points i and i + 1 will not be equal to equation of the line between points i and i - 1. That is in point i is formed an angle that doesn't equal 180 degrees.

So we should find equations of lines between every pair of points i and i + 1. It can be easily done using two arrays with queries of increasing value on the interval offline.

195E - Building Forest

Tutorial by author Fefer_Ivan

The longest operation in this problem is to find the root of some vertex and the sum of the path to this root. To find these values fast we will use compression ways heuristics which is used in data structure "disjoint-set-union".

For every vertex v we keep two values : c[v] and sum[v]. c[v] = v, if v — root, else c[v] — next vertex on path from v to root. sum[v] = sum of lengths of edges on path from v to c[v].

To add new edge from u to v of length w it is enough to do c[u] = v and sum[u] = w.

Note that we only add new edges (we don't erase edges).

That is, if we find root(v) and depth(v) for some vertex v we can assign c[v] = root(v),

Unable to parse markup [type=CF_TEX]

int root(int v){  
   if(c[v] == v){  
       return v;  
   }else{  
       int u = root(c[v]);  
       sum[v] = (sum[c[v]] + sum[v]) % M;  
       c[v] = u;  
       return u;  
   }  
}  

It can proved that such implementation works using O(log(n)) time for every query. The complexity of the solution is O(n * log(n)).

Welcome, friends)

We are glad to introduce you regular Codeforces round #123 for Div.2 participants. Everyone can traditionally participate in it.

Problems are prepared by command of authors: Ivan Fefer (Fefer_Ivan), Igor Kudryashov (Igor_Kudryashov), Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Also thanks to Pavel Kunyavskiy (PavelKunyavskiy) and Alexander Kouprin (Alex_KPR) for their help. And traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating problems.

Score distribution is standard: 500, 1000, 1500, 2000, 2500.

We wish you success and high rating!

Congratulations to winners:

1. bmerry
2. adrian.jaskolka
3. cheshire_cat
4. alexej
5. psw

UPD: the tutorial is here

Welcome friends)

We are glad to introduce you regular Codeforces round #117 for Div.2 participants. Everyone can traditionally participate in it.

Problems are prepared by command of authors: Pavel Kholkin (HolkinPV), Ivan Fefer (Fefer_Ivan), Nikolay Kuznetsov (NALP) and Gerald Agapov (Gerald). Thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating problems.

And again score distribution will be dynamic) More information you can find here.

Note that all problems today will be given in random order.

Some Div.1 participants register for the contest before settings of registration were changed. Before the round it will be fixed and they will participate out of competition.

We hope that todays round would be succesful and everyone enjoys it. We wish you good luck and high rating!

UPD: the statement for problem 182E - Wooden Fence was formulated incorrect, correct variant of the statement will be soon, we apologize to the participants.

UPD2: the contest is declared unrated.

Welcome dear friends)

We are glad to introduce you regular Codeforces round #113 for Div.2 participants. Everyone can traditionally participate in it.

Problems are prepared by known command of authors: Kholkin Pavel (HolkinPV), Nikolay Kuznetsov (NALP), Artem Rakhov (RAD). Also thanks to Gerald Agapov (Gerald) for his help, Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating problems.

In todays contest would be one innovation. Score distribution would be dynamic. More information you can find here)

We hope that todays round would be succesful. We wish you good luck and high rating!

UPD: The contest is over. Hope you enjoy the problems) the editorial is already here)

Congratulations to winners:

1. Avalanche

2. seiya

3. Konon

4. yongheng5871

5. I_dont_have_girlfriend

6. ibra

7. Doriam30

8. unknown79

9. UESTC_Hetalia

10. lisang

165A - Supercentral Point

In this problem you should just code what was written in the problem. For every point you can check if it is supercentral. Consider every point consecutively and find neighbors from every side. The complexity is O(N²).

165B - Burning Midnight Oil

This problem can be solved using binary search for the answer. obviously, if number v is an answer than every number w > v is also the answer, because the number of written lines of code could only become more. To check some number v you can use formula given in the problem, because it will have less than O(logN) positive elements. The complexity is O(log²(N)).

165C - Another Problem on Strings

You was to find number of segments [lf;rg] of the strings on which the sum equals to k (we are working with array of integers 0 and 1). We will count array sum where the value sum[i] equals to sum on segment [0;i]. We will count the answer going from left to right. Let's say we are in position pos. Now we will add the number of segments on which the sum equals to k and ends in position pos. To do it we will count array cnt where cnt[i] — number of occurrences of sum[i]. Then in position pos we add cnt[sum[pos] - k] to the answer. The complexity is O(N).

165D - Beard Graph

Beard-graph is a tree. It consists of one root and several paths from this root. There is a single path between every pair of vertices. That's why you should check whether every edge on the path between two vertices is black. If some edge is white there is no path between two vertices now.

The distances could be found separately. For every vertex v precalc such information: index of path from the root where v is situated and d[v] distance between root and v. If you know such information you can find distance between any two vertices.

To check whether every edge on the path between two vertices is black we will use segment tree. Mark black edge with value 0 and white with 1. Than repainting some edge — update in some point. The query — sum on some segment (the path between two vertices). If the sum equals to 0 there is a single path. Else the answer is -1 now. Complexity is O(NlogN).

165E - Compatible Numbers

Consider some number x from the array. Inverse all bits in x and say it is number y. Consider an integer a[i] from array. It can be an answer to the number x if for every position of zero bit from y there is zero bit in a[i] in the same position. Other bits in a[i] we can change to ones.

Then we will use such dynamic programming z[mask] = {0, 1} which means if we can change some zero bits to ones in some integer from given array a and get mask mask. Initial states are all integers from array a (z[a[i]] = 1). To go from one state to another we consider every bit in mask and try to change it to one. The length of bit representation of all integers in a is less or equal than 22.

To answer the question YES or NO for some number x you need to get value [z(y)&(1«22) - 1] (inverse all bits in x and make the length of the number 22). If you want to know the exact answer what number a[i] you should choose you can save previous states for every state z[mask] or just save it in z[mask]. Complexity O(2^K * K), where K – length of bit representation of numbers (K <  = 22).

Good day!

We are glad to introduce you regular Codeforces round for Div.2 participants. Everyone can traditionally participate in it.

Problems are prepared by Kholkin Pavel (HolkinPV), Rakhov Artem (RAD) and Nikolay Kuznetsov (NALP). Also thanks to Michael Mirzayanov (MikeMirzayanov) for perfect system, Mary Belova (Delinur) for translating problems and Agapov Gerald (Gerald) and Alexander Kouprin (Alex_KPR) for their help.

We decide to tell you some secret about todays problems. To solve them, you wiil propably use sort algorithm)

Score distribution is standard: 500, 1000, 1500, 2000, 2500.

We wish you success and high rating!

UPD: The contest is over, the tutorial will be here soon.

UPD2: Thanks everyone for participation. We hope you enjoy your problems. Congratulations to the winners:

1. Touma_Kazusa
2. ZJUT_AA
3. wwhd
4. jikwao425
5. wtiger9999
6. Jolin
7. anmtcel
8. marspeople
9. ztxz16
10. CrazyRabbit

Special congratulation to Touma_Kazusa, who solves all problems of the round.

Welcome to Codeforces Beta Round #72.