544A - Set of Strings

In that task you need to implement what was written in the statements. Let's iterate over all characters of string and keep array used. Also let's keep current string. If current character was not used previously, then let's put current string to the answer and after that we need to clear current string. Otherwise, let's append current character to the current string. If array, that contain answer will have more then k elements, we will concatenate few last strings.

The jury solution: 11035685

544B - Sea and Islands

It's clear to understand, that optimal answer will consists of simple cells, for which following condition fullfills: the sum of indices of row and column is even. We will try to put k islands in such way, and if it's impossible, we will report that answer is NO. Try to prove that this solution is optimal.

The jury solution: 11035691

543A - Writing Code

Let's create the solution, which will work too slow, but after that we will improve it. Let's calculate the following dynamic programming z[i][j][k] — answer to the problem, if we already used exactly i programmers, writed exactly j lines of code, and there are exactly k bugs. How we can do transitions in such dp? We can suppose that we i-th programmer will write r lines of code, then we should add to z[i][j][k] value z[i - 1][j - r][k - ra[i]]

But let's look at transitions from the other side. It's clear, that there are exactly 2 cases. The first case, we will give any task for i-th programmer. So, we should add to z[i][j][k] value z[i - 1][j][k]. The second case, is to give at least one task to i-th programmer. So, this value will be included in that state: z[i][j - 1][k - a[i]]. In that solution we use same idea, which is used to calculate binomial coefficients using Pascal's triangle. So overall solution will have complexity: O(n³)

The jury solution: 11035704

543B - Destroying Roads

Let's solve easiest task. We have only one pair of vertices, and we need to calculate smallest amout of edges, such that there is a path from first of vertex to the second. It's clear, that the answer for that problem equals to shortest distance from first vertex to the second.

Let's come back to initial task. Let's d[i][j] — shortest distance between i and j. You can calculate such matrix using bfs from each vertex.

Now we need to handle two cases:

1. Paths doesn't intersects. In such way we can update the answer with the following value: m - d[s₀][t₀] - d[s₁][t₁] (just in case wheh conditions on the paths lengths fullfills).
2. Otherwise paths are intersecting, and the correct answer looks like a letter 'H'. More formally, at the start two paths will consists wiht different edges, after that paths will consists with same edges, and will finish with different edges. Let's iterate over pairs (i, j) — the start and the finish vertices of the same part of paths. Then we can update answer with the following value: m - d[s₀][i] - d[i][j] - d[j][t₀] - d[s₁][i] - d[j][t₁] (just in case wheh conditions on the paths lengths fullfills).

Please note, that we need to swap vertices s₀ and t₀, and recheck the second case, because in some situations it's better to connect vertex t₀ with vertex i and s₀ with vertex j. Solutions, which didn't handle that case failed system test on testcase 11.

The jury solution: 11035716

543C - Remembering Strings

First that we need to notice, that is amout of strings is smaller then alphabet size. It means, that we can always change some character to another, because at least one character is not used by some string.

After that we need handle two cases:

1. We can change exactly one character to another. The cost of such operation equals to a[i][j] (which depends on chosed column) After that we can remember string very easy.
2. We can choose some column, and choose some set of strings, that have same character in that column, By one move we can make all these strings are easy to remember.The cost of such move equals to cost of all characters, except most expensive.

As the result, we will have following solution: d[mask] — answer to the problem, when we make all strings from set mask easy to remember. We can calculate this dp in following way: let lowbit — smallest element of set mask. It's clear, that we can do this string easy to remember using first or second move. So we need just iterate over possible columns, and try first or second move (in second move we should choose set that contain string lowbit) Overall complexity is O(m2ⁿ), where m — is length of strings.

The jury solution: 11035719

543D - Road Improvement

Let's suppose i is a root of tree. Let's calculate extra dynamic programming d[i] — answer to the problem for sub-tree with root i We can understand, that d[i] equals to the following value: — where j is a child of the vertex i. It's nice. After that answer to problem for first vertex equal to d[1].

After that let's study how to make child j of current root i as new root of tree. We need to recalculate only two values d[i] and d[j]. First value we can recalculate using following formula d[i]: suf[i][j] * pref[i][j] * d[parent], where parent — is the parent of vertex i, (for vertex 1 d[parent] = 1), and array suf[i][j] — is the product of values d[k], for all childs of vertex i and k < j (pref[i][j] have same definition, but k > j). And after we can calculate d[j] as d[j] * (d[i] + 1). That is all, j is root now, and answer to vertex j equals to current value d[j]

The jury solution: 11035737

543E - Listening to Music

Let's sort all songs in decreasing order. We will iterate over songs, and each time we will say, that now current song will fully satisfy our conditions. So, let's s_i = 0, is song i was not processed yet and s_i = 1 otherwise. Let . It's clear, when we add new song in position idx then we should do  + 1 for all on segment [max(0, idx - m + 1), idx] in our array v. So, when we need to implement some data structure, which can restore our array v to the position when all strings have quality  ≥ q. It also should use very small amout of memory. So, answer to the query will be m - max(v_i), l_j ≤ i ≤ r_j.

We will store this data structure in the following way. Let's beat all positions of songs in blocks of length . Each time, when we added about songs as good, we will store three arrays: first array will contain value v_i of first element of the block of indices. second array will contain maximum value of v on each block and also we will keep about of ''small'' updates which doesn't cover full block. Using this information array v will be restored and we process current query in easy way.

The jury solution: 11035739

Hello Codeforces!

Soon you are lucky to participate in Codeforces Round #302, and I am writer of this contest.

I want to thank Max Akhmedov (Zlobober), Alexander Ignatyev (aiMR), Danil Sagunov (danilka.pro) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

Scoring will be next:

1. Div1: 500 — 1000 — 1750 — 1750 — 2500
2. Div2: 500 — 1000 — 1500 — 2000 — 2750

Contest finished, congratulations to winners:

Div1:

1. Petr
2. qwerty787788
3. -XraY-
4. kraskevich
5. Merkurev

Div2:

1. nka55
2. never_retired_phoenix
3. lowsfish

Editorial

Soon you are lucky to participate in Codeforces Round #284, and problems have been prepared by Vitaly Gridnev (gridnevvvit), Ilya Los (IlyaLos), Danil Sagunov (danilka.pro).

We want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

Scoring system will be dynamic. Problems will be arranged in ascending expected difficulty order.

Round finished, congratulations to winners!

Div1:

1. yeputons
2. rng_58
3. Endagorion
4. KADR
5. Egor
6. uwi
7. mmaxio
8. atetubou
9. RAVEman

Div2:

1. sorry_dreamoon
2. dreamoon_love_AA
3. dreamoon_fan

Editorial

Good luck!

Soon (on October 24, 21:00 MSK) you are lucky to participate in Codeforces Round #275 for both divisions. Pay attention to the round begining time!

Problems have been prepared by team Saratov SU #3 with members: Gridnev Vitaly (gridnevvvit), Danil Sagunov (danilka.pro), Roman Kireev (RoKi).

We want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

Scoring system:

Div1: 500 1500 1500 2000 2500

Dvi2: 500 1000 1500 2500 2500

UPD:

Contest finished, congratulations for winners!

Div1:

1. tourist
2. Petr
3. subscriber
4. uwi
5. PavelKunyavskiy
6. mmaxio
7. Ra16bit

Div2:

1. dickXD
2. meodorewan
3. charlie

Hello!

Soon (on June 8 at 19:30 MSK) you are lucky to participate in Codeforces Round for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by: Gridnev Vitaly (gridnevvvit) and Danil Sagunov (danilka.pro).

We want to thank Gerald for help in preparation of this round, Delinur for translation of statements and MikeMirzayanov for marvelous Codeforces and Polygon systems.

Scoring will be next 500 — 1000 — 1500 — 2000 — 2500.

Contest finished, congratulations to winners!

1. kuangbin10
2. ToumaKazusa
3. qiaoranpenxiang
4. rotoZOOM
5. umczca195

Editorials will be there

Good Luck!

402A - Nuts

Let's fix some value of boxes ans. After that we can get exactly cnt = ans + min((k - 1) * ans, B) of sections. So, if cnt * v ≥ a, then ans be an answer. After that you can use brute force to find smallest possible value of ans.

402B - Trees in a Row

Let's fix height of the first tree: let's call it a. Of course, a is an integer from segment [1, 1000]. After that, for the fixed height a of the first tree we can calculate heights of the others trees: a, a + k, a + 2k, and so on. After that you should find minimal number of operations ans to achive such heights. After that we can use brute force to find smallest possible ans for each a from 1 to 1000. For best height of the first tree you should print all operations.

402C - Searching for Graph / 403A - Searching for Graph

I will describe two solutions.

First. Consider all pairs (i, j) (1 ≤ i < j ≤ n). After you should ouput the first 2n + p pairs in lexicographical order.

It's clear to understand, that it is enough to prove, that 0-interesting graph is correct or  - 3 -interesting graph is correct. We will prove for  - 3 -interesting graph, that it is correct. This graph consists of triangles, which have an common edge 1 — 2. Let's fix some subset of vertexes, which does not contains vertexes 1 and 2. In such sets there are no edges. Let's fix some subset, which contains exactly one vertex (1 or 2). In such subsets there are exactly k - 1 edges, where k is the size of such subset. In other subset there are exactly 2 * (k — 2) + 1 edges, where k is the size of such subset.

Second. Let's use some brute force, to build graphs with 0-interesting graphs with sizes 5, 6, 7, 8, 9 vertexes. Now, to build p-interesting graph with n vertexes, We will build 0-interesting graph, and after that we will add to it p another edges, which is not in the graph. We will build 0-interesting graphs using the following approach: Let's took k disjointed components, from graphs with number of vertexes from 5 to 9, in such way that there are exactly n vertexes in graph.

402D - Upgrading Array / 403B - Upgrading Array

I will describe two solutions.

First. Dynamic programming approach. Let's calculate an DP d[i][j] — which is the best possible answer we can achieve, if current prefix has length i and we used operation of Upgrading last time in position j. It is clear to understand, that we should iterate i from n to 1, and j from n to i. There are only two transitions:

• First, d[i - 1][j] = max(d[i - 1][j], d[i][j]) — we will not use operation of upgrading of array in the current position.
• Second, d[i - 1][i - 1] = max(d[i - 1][i - 1], d[i][j] + f(tgcd[j]) * i - f(tgcd[i - 1]) * i — we are using an operation of upgrading. f(a) — is a beauty of the number. tgcd[i] — gcd of all numbers on the prefix of length i. You can use function, which works in to calculate the beauty. Also you can make your solution more faster, it you will precalculate some small primes. Also you can use map < int, int >  to store calculated values. DP base d[n][n] = curBeauty — is a current beauty of the array.

Second. Greedy. Let's find position r, which can upgrade our answer. If there some values of r — we will take most right position. We will add this position to the answer and upgrade our answer. Why it's correct? Let's fix an optimal solution (sequence of position, where we used an upgrading operation) r₁ > r₂ > ... > r_k. Also we have an solution which was built by using greedy l₁ > l₂ > ... > l_m. It's clear, that r₁ ≤ l₁, because all position with  > l₁ cannot upgrade anything (otherwise greedy will choose it as first position). In other hand, r₁ ≥ l₁, because otherwise we can upgrade in position l₁ and make answer better. So, r₁ = l₁, and after that we can use our propositions for big indexes i.

402E - Strictly Positive Matrix / 403C - Strictly Positive Matrix

Let's look at the matrix a as a connectivity matrix of some graph with n vertices. Moreover, if a_ij > 0, then we have directed edge in the graph between nodes (i, j). Otherwise, if a_ij = 0 that graph does not contains directed edge between pair of nodes (i, j). Let b = a^k. What does b_ij means? b_ij is the number of paths of length exactly k in our graph from vertex i to vertex j. Let pos is an integer, such that a[pos][pos] > 0. That is, we have a loop in the graph. So, if from the vertex pos achievable all other vertexes and vice versa, from all other vertices reachable vertex pos, then the answer is YES, otherwise the answer is NO. If reachability is missing, it is clear that for any k a^k_ipos = 0. If reachability there, we will be able to reach self-loop, use self-loop "to twist", and after that we will go to some another vertex.

403D - Beautiful Pairs of Numbers

First, we can note, that length of sequence is not greater then 50. Ok, but why? Because all numbers b_i - a_i are different, so 0 + 1 + ... + 50 > 1000. Let's imagine, that sequence from input is a sequence of non-intersecting segments. So, c_i = b_i - a_i + 1 is length of segment i. Also, . After that let's calculate the following DP: d[i][j][k] — — number of sequences for which following holds: c₁ < c₂ < ... < c_i, c_i ≥ 1 , c₁ + c₂ + ... + c_i = j and maximal number is less then k (upper bound of sequence). This DP will helps us to calculate number of ways to set length to each segment in sequence. It's simple to calculate such DP:

• base d[0][0][1] = 1,
• d[i][j][k + 1] = d[i][j][k + 1] + d[i][j][k] — we increase upper bound of sequence;
• d[i + 1][j + k][k + 1] = d[i + 1][j + k][k + 1] + d[i][j][k] — we are adding upper bound to the sequence.

We can calculate such DP, by using only O(N²) of memory, where N = 1000. After that we should multiply d[i][j][k] on i!, because we need number of sequences c_i, where order does not matter.

After that we can calculate answer for n, k. Let's , where x — some upper bound of sequences. After that we should calculate next number: how many ways to set to distances between segments? It's clear, that we can increase distance between some segments, but we have only n - len such operations. It's well known, that answer number of ways equals to C(n - len + k, k). So, for each n we should sum by len following values: sum[len] * C(n - len + k, k).

Note, that we need array C[n][k] (binomials) where n ≤ 2000, k ≤ 2000.

403E - Two Rooted Trees

First, for each vertex of the first and second tree we calculate two values in[s], out[s] — the entry time and exit time in dfs order from vertex with number 1. Also with each edge from both trees we will assosiate a pair (p, q), where p = min(in[u], in[v]), q = max(in[u], in[v]) (values in, out for each vertex we take from tree with another color). Now for each tree we will build two segment trees (yes, totally 4 segment trees). In first segment will store all pairs in following way: we will store a pair in node of segment tree if and only if (node of segment tree is a segment (l, r)) left element of pair lies in segment (l, r). In second segment tree we will store a pair if and only if right element of the pair lies in segment (l, r) All pairs in segment trees we will store in some order (in first segment tree — increasing order, in the second tree — decreasing order). Such trees use of memory, also you can build it in .

Good. How to answer on query (l, r) — erase all edges from tree for which exactly one vertex have value in[s] in segment (l, r)? We will go down in our segment tree. Let's imagine, that now we in some node of segment tree. Because we store all pairs in the first segment tree in increasing order of the right element, so answer to the query is a some suffix of the array of pairs. After we can add they to the answer (if it not erased yet). After that we should modify our segment tree: for each node, where we work with suffixes, we should erase all pairs from such suffix. So, this solution in .

My solution to E: 6052738

Soon (on March 16, 19:30 MSK) you are lucky to participate in Codeforces Round #236 for both divisions.

Problems have been prepared by me. It’s my first round for both divisions and I hope not last. I want to thank Gerald Agapov (Gerald) for help in preparation of this round, Ilya Los (IlyaLos) and Ignatyev Alexander (aiMR) for testing of problems, Mary Belova(Delinur) for translating the problems, Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

UPD: Scoring system:

Div. 2: 500 — 1000 — 1500 — 2000 — 2500

Div. 1: 500 — 1000 — 1500 — 1500 — 2000

UPD:

Contest finished, congratulation for winners!

Div.2 :

1. vladb
2. iceiceice
3. LoneFox
4. ofpsxx
5. adsz

Div. 1:

• 1 sillycross
• 2 KADR
• 2 vepifanov
• 4 Endagorion
• 5 glassices
• 6 cgy4ever
• 7 rowdark
• 8 snuke
• 9 ftiasch
• 10 fsouza

UPD:

Editorial.

UPD:

Round Statistics from DmitriyH.

387A - George and Sleep

I will describe the simple solution. Let George woke up in the h₀ hours and m₀ minutes, and he slept for h₁ hours and m₁ minutes. Let's get the number h_p = h₀ - h₁ and m_p = m₀ - m₁. If m_p < 0, then you should add to m_p 60 minutes and subtract from h_p one hour. After that if h_p < 0, then add to it 24 hours. You can print the answer in C++ by using the following line:

printf("%02d:%02d", h[p], m[p]).

The complexity is O(1) time and O(1) memory.

Author's solution: 5850831

387B - George and Round

Consider the number of requirements of the difficulties, which we will cover, and we will come up with and prepare new problem to cover other requirements. It is clear that if we decided to meet the i out of n requirements, it would be better to take those with minimal complexity. Let's simplify i most difficult problems to lightest requirements. If all goes well, then we update the answer by value n - i.

The complexity is: O(n²) time / O(n) memory. Note, that there is an solution with complexity O(n + m).

Author's solution: 5850888

387C - George and Number

Let's obtain the following irreducible representation of a number p = a₁ + a₂ + ... + a_k, where  +  is a concatenation, and numbers a_i have the form x00..000 (x — is non zero digit, and after that there are only zeroes). Let's determine largest index i, such that a₁ + a₂ + ... + a_i - 1 < a_i. If there are no such index i then i = 1. After that is k - i + 1. You can compare numbers by using length of number and first digit. You can prove these solution as home task : )

The complexity is: O(n) time / O(n) memory.

Author's solution: 5850919

387D - George and Interesting Graph

To solve this problem you should know about bipartite matching.

Let's consider the center of graph i. After that let's remove arcs that have form (i, u) or (u, i). Let's there are cntWithI arcs of such type. Let's Other = m - CntWithI — number of other arcs.

After that we should found maximal bipartite matching on the bipartite graph. This graph has following idea: left part of this graph is indegrees of all vertexes except vertex i, right part of this graph is outdegrees of all vertexes except vertex i. Also if there an arc (i, j) in our graph then in our bipartite graph there an arc (i, j), where i — vertex from left part, j — vertex from the right part. Let's size of bipartite matching on the bipartite graph equals to leng. Then answer for the current vertex i equals to 2n - 1 - cntWithI + Other - leng + (n - 1) - leng. After that you should update global answer. Why it is correct? It is simple to understand that if we will found bipartite matching on the bipartite graph we will cover maximal number of requirements on in/out degrees. Because of that, we will remove all other arcs, except of maximal matching, and after that we will add this maximal matching to full matching by adding (n - 1) - leng arcs. Note, it is important, that self-loops are not forbidden. Withoud self-loops problem is very hard, I think.

The complexity is: O(n²m) time / O(n + m) memory.

5850946

387E - George and Cards

Let's calculate arrays pos[i] — position of number i in permutation p and need[i] — equals to one if we should remove number i from permutation p, and zero if we shouldn't remove i from permutation p.

Let's a₁, a₂, ..., a_n - k — numvers, which we should remove. It is clear to understand that we should remove these number in increasing order. It is simple to proof this statement.

Let's iterate i from to 1 to n. Also we the current number we will have special set (set <>in с++, TreeSet in Java) of positions of non-erased numbers (which are smaller then i) of permutation. These position can create an ``obstacle'' for current position of number i. It is simple to support this special set. Also we can add to this set numbers  - 1 and n. Now it is easy to find length og the maximal sub-array, where current number is a minimum. You can prosess such query by using standart functions of programming language (lower and higher in Java). After that we should use Fenwick tree to determine quantity of numbers which are not removed on the maximal sub-array.

The complexity is: time / O(n) memory.

Very simple implementation on Java: 5850986

Hello!

Soon (on January 30 at 19:30 MSK) you are lucky to participate in Codeforces Round #227 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by me. I want to thank Gerald Agapov (Gerald) for help in preparation of this round, Mary Belova (Delinur) for translation of statements, Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

The main character of the tasks is the cat George.

UPD1: Scoring will be next: 500, 1000, 1500, 2000, 2500.

UPD2: Contest finished, congratulations to winners!

1. Sorto
2. graphis
3. InternationalGrandmaster
4. Skedar
5. mateusz

UPD: Editorial

UPD: Statistics

369A - Valera and Plates

We will use greedy algorithm. Let's now i-th day, and current dish is a dish of first type. Then if we have the bowl, let's use it. Otherwise we will increase the answer. If the current dish is a dish of the second type, we first try to get the plate, and then the bowl. If there are no plates/bowls at all, then we will increase the answer.

Author's solution: 5306397

369B - Valera and Contest

In this task you are to determine such array a₁, a₂, ..., a_n, that following conditions are met:

1. r ≥ a₁ ≥ a₂ ≥ ... ≥ a_n ≥ l;
2. ;
3. ;

It's clear to understand, that value s_k should be distributed evenly between the first k elements. For example, you can use following algorithm:

remainder = (s_k mod k);
for(int i = 0; i < k; i++) 
{
	a_i = s_k / k + (remainder > 0);
	remainder = remainder - 1;
}

If k ≠ n, you should use same algorithm with other elements, but there are to distribute value s_all - s_k.

Some participants forgot about test, where k = n. They received RE11.

Author's solution: 5306414

369C - Valera and Elections

Consider all the roads that we need to repair. Mark the ends of u, v white. After that, we will consider a simple dynamic programming d[v] (v is the vertex) on the tree that for each vertex in the tree determines the number of white vertexes in the subtree. It is easy to calculate this by using a recursive function calc(v, prev) (v is the current node, and prev its immediate ancestor):

calc(v, prev)
{
	d[v] = 0; 
	if (white[v])
		dv += 1; 
	for all vertexes u such that there is the edge (u,v) or (v,u), u != prev:
		calc(u, v);
		d[v] += d[u];  
}

After that we will add to answer all white vertexes v such that next condition is correct: d[v] = 1

Author's solution: 5306500

369D - Valera and Fools

Let's p[A] is the p_A from the statement.

It's clear to understand that you can discribe the state by using pair of integers (A, B), where A is a number of the fool with smallest index, B — the second fool from the left. It is clear to understand that fool with indexes j ≥ B will be living. After that we will use bfs on the states (A, B).

State (0, 1) is always visitable, because it is initial. We will push it in the queue. After that, there are only three transitions from current state (A, B).

1. (B + 1, B + 2) — this transition is possible if and only if p[A] > 0 and there are some fool with index j ≥ B, which has non-zero value p[j] > 0.
2. (A, B + 1) — this transition is possible if and only if p[A] > 0 и there are no fool with index j ≥ B, which has p[j] = 100.
3. (B, B + 1) — this transition is possible if and only if p[A] ≠ 100 and there are some fool with index j ≥ B, which has non-zero value p[j] > 0.

After that you are to determine number of states, which has distance from state (0, 1) less or equal to k. Also you should be careful, that if there are only one fool, that he doesn't shot.

Author's solution: 5306516

369E - Valera and Queries

Let's calculate sets xs[y] — all segments, whose right borders are exactly equal to y. Now we reduce our task to another. For each query we will count the number of segments that doesn't belong to any one point. Let's it will be the value v. Then the answer to the query is n - v. We add to our request the point 0 and a point MV + 1, where MV = 1000000. Let points request have the form x₁ < x₂... < x_n. Consider the x_i and x_i + 1. Let p_i is the number of segments that lie strictly inside x_i and x_i + 1. Then v = p₁ + p₂ + ... + p_n - 1. We will use following algorithm to find the values p_i. Let consider all such pairs (x, x_i + 1) for all requests and to add them to a second set xQ[y] — all pairs whose right boundary is equal to r. Then to find the values p of pairs (x_i, x_i + 1) we will iterate ascending the right border. Additionally, we will support Fenwick's tree, which can make  +  = 1 at the point, and can calculate sum of the prefix. Let i — the current right border. Then we can find out the value p for all pairs (l, r), with the right border is equal to the i (l, i). Let j left border of the pair. Then the answer for the pair is the value of S - sum(j), where S — all added to the Fenwick's left borders, and sum(j) — sum of the prefix j. After that, for the current coordinate i we need to consider all segments in the set xs[i]. Let j left boundary of the segment. Then we need to make  +  = 1 at the point j in our Fenwick's tree. The total solution complexity is .

Authors solution: 5306535

Hello!

A few hours later, on November 29th at 19:30 MSK, you are lucky to participate in Codeforces Round #216 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by: Gridnev Vitaliy (gridnevvvit) and Los Ilya (IlyaLos).

We want to thank Gerald Agapov (Gerald) and Sergey Sukhov (Serega) for help in preparation of this round, Mary Belova (Delinur) for translation of statements, Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

UPD1: Scoring will be next: 500, 1000, 1500, 2000, 2500.

UPD2: It was a misprint with scoring system, now it is correct.

UPD Contest finished, congratulations to winners!

1. Dshovn
2. WhitedarkWalker
3. hexor
4. Pandii
5. Ronnoc_2

Good Luck!

I'm not good in English. So, if you find an mistake in editorial, please, send me a private message.

359A - Table

If there are some good cell, which is located in the first row or in the first column, the answer is two. Similarly, if If there are some good cell, which is located in the last row or in the last column, the answer is two. Otherwise, the answer is four.

Авторское решение: 4968279

359B - Permutation

The answer is a slightly modified permutation 1, 2, ..., 2n. Let's reverse numbers 2i - 1 and 2i for each 1 ≤ i ≤ k. It's not hard to understand, that this permutation is good.

Авторское решение: 4968385

359C - Prime Number

Obviously, the answer is x^v. Let sum = a₁ + a₂ + ... + a_n. Also let s_i = sum - a_i (the array of degrees). After that let's find value v by the following algorithm: Let's consider a sequence of degrees as decreasing sequence. Now we will perform the following operation until it's possible to perfom it. Take the minimum degree v from the array of degrees and calculate the number of elements cnt, which have the same degree. If cnt multiples of x, then replace all cnt elements by cnt / x elements of the form v + 1. Since the sequence of degrees is a decreasing sequence, we can simply assign them to the end. If cnt is not a multiple of x, then we found the required value v. Also you need to check, that v is not greater then sum. Otherwise, v will be equals to sum.

Авторское решение: 4968346

359D - Pair of Numbers

Quite simple note: if the pair (l, r) satisfies the condition 1 from the statements, then min(l, r) = GCD(l, r), where min(l, r) is smallest number a_i from the segment (l, r) and GCD(l, r) is a GCD of all numbers from the segment (l, r). Calculate some data structure that will allow us to respond quickly to requests GCD(l, r) and min(l, r). For example, you can use Sparce Table. Solutuions, that uses segment tree, is too slow. So I think, you should use Sparce Table. So, now our task quite simple. Let's use binary search to find greatest value of r - l:

lf = 0;  //left boundary of binary search
rg = n;  //right boundary of binary search
while (rg - lf > 1) {
  int mid = (lf + rg) / 2;
  if (ok(mid))   //ok(mid)
    lf = mid;
  else
    rg = mid;
}

ok(mid) is the function, that determines, is there some segment where min(l, r) = GCD(l, r) and mid = r - l (mid — is fixed value by binary search). If there is some good segment, you should update boundaries of binary search correctly. After that, it's very simple to restore answer.

Some information about Sparce Table

Авторское решение: 4968587

359E - Neatness

You should write recursive function, that will turn on the light in all rooms, where it's possible. Also this function will visit all rooms, which it may visit. Let this function is called paint(x, y), where x, y is the current room. Paint(x, y) will use following idea: Let's look at all neighbors. If there is a light in the current direction (rule 3 from the statement), and the room (nx, ny) (current neighbor) has not yet visited, we will call our recursive function from (nx, ny). Also, we will turn on the light in all rooms, were we were. If some room is not visited by paint(x, y) and lights is on in this room, the answer is "NO". Otherwise, the answer is "YES". After that let's calculate value dist(x, y) by using bfs. dist(x, y) — is a minimal possible distance from the start to the current position (x, y). It's possible to use in our bfs only rooms, where lights is on. After that we will write the same function repaint(x, y). Repaint(x, y) will use following idea: Let's look at all neighbors. If there is a light in the current neighbor (nx, ny) and dist(nx, ny) > dist(x, y) ((x, y) — current room), let's call our recursive function from (nx, ny).After that we will come back to room (x, y). If there is no such neigbor (nx, ny), turn off the light in the room (x, y). Also you should look at my solution for more details.

Авторское решение: 4968657

Hello!

Soon (on November 2 at 12:00 MSK) you are lucky to participate in Codeforces Round #209 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition. Pay attention to the round begining time!

Problems have been prepared by me. I want to thank Gerald Agapov (Gerald) and Ilya Los (IlyaLos) for help in preparation of this round, Mary Belova (Delinur) for translation of statements, Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

UPD1: Scoring will be next: 500, 1000, 1500, 2500, 2500.

UPD2: Congratulations to winners!

1. cptbtptp
2. FancyCoder
3. Oyk
4. E.B.
5. orzkbc

UPD: Editorial

Good Luck!

350A - TL

Let's v = min(a_i), p = max(a_i), c = min(b_i). So, if max(2 * v, p) < c, then answer is max(2 * v, p), else answer is  - 1.

Author solution: 4632352

350B - Resort

Input data represents a graph, by using a array of parents of every vertex. Because every vertex has at most one parent, we can use following solution: we will go up to parent of vertex v (prev[v]) until not found vertex with the outcome degree  ≥ 2. It is better to calculate outcome degrees in advance. After all, we will update the answer.

This algorithm works in O(n).

Author solution: 4632399

350C - Bombs

First of all, Let's sort all point by increasing of value |x_i| + |y_i|, all points we will process by using this order. We will process each point greedily, by using maximum six moves. Now we want to come to the point (x, y). Let's x ≠ 0. Then we need to move exactly |x| in the dir direction (if x < 0 the dir is L, x > 0 — R). Similarly we will work with y-coordinates of point (x, y). Now we at the point (x, y), let's pick a bomb at point (x, y). After that we should come back to point (0, 0). Why it is correct to sort all point by increasing of Manhattan distance? If you will look at the path that we have received, you can notice that all points of path have lower Manhattan distance, i.e. we will process this points earlier.

This solution works in

Authors solution: 4632478

350D - Looking for Owls

It's possible to solve this problem by using only integer calculations. Normalization of the line Ax + By + C is following operation: we multiply our equation on the value , where g = gcd(A, gcd(B, C)), if A < 0 (orA = 0andB < 0) then sgn equals to  - 1, else sgn equals to 1.

Now the solution. We will have two maps (map<> in С++, TreeMap(HashMap) in Java) to a set of points (it's possible that some points will have multiply occurrence into the set). In first map we will store right boundaries of the segments, in second — left boundaries (in increasing order).

In advance for every segment we will build a normalized line, and for this normalized line we will put in our maps left and right segments of the segment.

After all, for every fixed line let's sort our sets.

Let's fix two different circles. After that, let's check that distance beetween them is greater then sum their radiuses, also you should check that circles has same radius. We can assume that we builded a line between centers of circles (x1, y1) and (x2, y2). Perpendicular to this line will have next coefficients (center of the segment [(x1, y1), (x2, y2)] also will belong to the next line) A = 2(x1 - x2), B = 2(y1 - y2), C =  - ((x1 - x2) * (x1 + x2) + (y1 - y2) * (y1 + y2)). After that you need to calculate values cntL, cntR by using binary search on set of points that lie on this line. cntL — amount of left boundaries that lie on the right side of point ((x1 + x2) / 2, (y1 + y2) / 2), cntR -- amount of right boundaries that lie on the left side of the point ((x1 + x2) / 2, (y1 + y2) / 2). After that you should add to answer value cntV - cntR - cntL,l where cntV — amount of segments, that lie on the nolmalized line.

Total complexity: .

solution: 4632546

350E - Wrong Floyd

Let's do the following: construct the graph with the maximum possible number of edges and then remove the excess. First of all, you can notice that if k = n answer is  - 1. Else let's fix some marked vertex, for example a₁. Let's put in our graph all edges except edges beetween a₁ and x, where x — an another marked vertex.

So, why this algorithm is correct? If Valera's algorithm is wrong, then there are a ''bad'' pair of vertexes (i, j). ``Bad'' pair is a pair for that Valera's algorithm works wrong. So, there are not marked vertex v on the shortest path from i to j, and v ≠ i, and v ≠ j. Without loss of generality, we can assume, that distance beetween i and j equals to 2, but Valera's algorithm gives greater answer. There are some cases, that depends on the type of vertexes i, j. But we can look only at the case where (i, j) are marked vertexes. First, add to the graph all edges beetween not fixed (i, j) vertexes. Second, add to the graph edges beetween some fixed vertex (i or j) and some not marked vertex. Third, add to the graph edges beetween i and some marked vertex v, where v ≠ j. It's simple to understand, that if we add some another edge, the Valera's algorithm will work correctly. Total amount of edges is .

BONUS Simple bonus. For same contrains (n, m, k) can you build a graph, where Valera's code works correctly?

Код: 4632600

Hello!

Soon (on October 1 at 19:30 MSK) you are lucky to participate in Codeforces Round #203 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by me. I want to thank Gerald Agapov (Gerald) for help in preparation of this round, Ilya Los (IlyaLos) for testing of problems, Alexander Ignatyev (aiMR) for testing of problems and for idea of one of the problems, Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems, Mary Belova (Delinur) for translation of statements.

Good luck!

UPD:Scoring will be dynamic. Problems are sorted by increasing order of difficulty.

UPD: Congratulations to winners:

1. fanhqme
2. FAU.COACH
3. Witalia
4. sokian

UPD: Editorial

336A - Vasily the Bear and Triangle

val = |x| + |y|. Then first point is (val * sign(x), 0), second — (0, val * sign(y)). Swap points if needed according to statement.

Let's see why this is the answer. Conditions x ≠ 0 and y ≠ 0 give us that one point is on X-axis, and the other on Y-axis. Let's see how it works for x > 0 and y > 0. Other cases can be proved in similar way. We need to show, that (x, y) belongs to our triangle(including it's borders). In fact (x, y) belongs to segment, connecting (x + y, 0) with (0, x + y). Line through (x + y, 0) and (0, x + y) is Y =  - X + x + y. Using coordinates (x, y) in this equation proves the statement.

Author's solution

336B - Vasily the Bear and Fly

Also you could iterate circles, adding distance for each of them and dividing by m² in the end. Let's see how the i-th iteration works 1 ≤ i ≤ m. Distance to m + i-th circle is 2R. Distance to m + j-th circle, where |j - i| = 1, is . For other circles it's quite simple to calculate sum of distances. There are i - 2 circles which located to the left of current circle. So, sum of distances for these circles is . In the same manner we can calculate answer for cirlcles which are located to the right of the current circle

Author's solution

336C - Vasily the Bear and Sequence

Let's check max beauty from 29 to 0. For every possible beauty i our aim is to find largest subset with such beauty. We will include in this subset all numbers, that have 1 at i-th bit. After that we do bitwise and as in statement, and if the resulting value is divisible by 2ⁱ, then there is the answer. Solution works in O(n).

Author's solution

336D - Vasily the Bear and Beautiful Strings

any — random binary string, s + g — concatenation of strings, MOD = 1000000007.

String 1 + any always transforms into 0, string 1 — into 1. String 01 + any always transforms into 1, string 01 — into 0. String 001 + any transforms into 0, string 001 — into 1, and so on. Using these facts let's consider following solution.

Cases like strings without ones or zeroes are easy. For every i (in zero-based numbering) let's assume that it is position of the first occurence of 1 in our string. Using already known facts we can understand what is the final result of transformations for such string. If the result equals to g, we add C(cnt[0] + cnt[1] - i - 1, cnt[1] - 1) to the answer. Calculation of binomial coefficients is following: fact[i] = i!%MOD, , C(n, k) = fact[n]inv(fact[n - i]fact[i]), where inv(a) — inverse element modulo MOD. inv(a) = a^MOD - 2, because MOD is prime number.

Author's solution

336E - Vasily the Bear and Painting Square

Pretty tough problem. Consider following DP dp[lvl][op][cur][type] — number of ways to take op triangles, if we have 2lvl + 1 squares. cur, type — auxiliary values. Answer will be dp[n][k][0][2]k!. type means type of transitions we make. cur — amount of used quarters (cur = 4 — 2 quarters, cur < 4 — cur quarters). It is important to distinguish cur = 2 from cur = 4, because amount of consecutive pairs of unused quarters is different.

About transitions. type = 2. Iterate amount of pairs (considering cur) of consecutive quarters that we will take. It is important for them to have no common quarters. We can get two pairs only in case cur = 0. Let's also take some quarters that are not in pairs. Calculate number of ways to select corresponding triangles and add to the current DP-state value dp[lvl][op - choosen][newcur][1] * cntwaystochoose. For better understanding of type = 2 check my solution (calc(n, k, cur, type) — isfordp[n][k][cur][type]).

type = 1. Now we take triangles at the borders (number of squares is 2*lvl + 1). "at the borders" means marked X, see the picture.

Iterate amount of pairs (considering cur) of consecutive triangles we take. It is important for pairs to have no common triangles. Let's also take some triangles that are not in pairs. Calculate number of ways to select corresponding triangles and add to the current DP-state value dp[lvl][op - choosen][cur][0] * cntwaystochoose.

type = 0. We take triangles at the borders (number of squares is 2*lvl). "at the borders" means marked X, see the picture.

Take some triangles, not in pairs. Calculate number of ways to select corresponding triangles and add to current DP-state value dp[lvl - 1][op - choosen][cur][2] * cntwaystochoose. Starting values: dp[0][0][cur][1] = 1, dp[0][cnt][cur][1] = 0, cnt > 0.

Author's solution

Hello!

Soon (on August 9 at 19:30 MSK) you are lucky to participate in Codeforces Round #195 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by me. I want to thank Gerald Agapov (Gerald) for help in preparation of this round, Eugene Sobolev (Seyaua), Vitaly Aksenov (Aksenov239) and Sergey Sukhov (Serega) for testing of problems, Alexander Ignatyev (aiMR) for testing of problems and for translation of tutorial, Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems, Mary Belova (Delinur) for translation of statements.

We wish everyone good luck and high rating!

UPD: English tutorial

UPD: Congratulations for winners:

1. Triolossus_3
2. WHITE2302
3. PM2.5

Separately, I want to congratulate Egor Kulikov (Egor) — the only person who had passed the all problems!

305A - Strange Addition

All you have to do is implement following algorithm:

1. If we have numbers 0 or 100, we take them to needed subset.
2. If we got number greater than 0 and less than 10, we take it.
3. If we got number divisible by 10 we take it.
4. In case we have no numbers of second and third type, we take a number that is not divisible by 10

Solution

305B - Continued Fractions

There are at most two ways to represent rational fraction as continued. Using Euclid algorithm you can do that for and then check equality of corresponding a_i.

Solution

305C - Ivan and Powers of Two

First of all, let's carry over all powers of two in the following way: if we have a_i = a_j, i ≠ j, carry 1 to a_i + 1. Now as all of a_i are distinct, the answer is max(a_i) — cnt(a_i) + 1, where max(a_i) — maximal value of a_i,cnt(a_i) — size of a

Solution

305D - Olya and Graph

First of all let's consider a graph on a number line. It's neccesary to have edges i -  > i + 1(first type). Also you can edges like i -  > i + k + 1 (second type). Other edges are forbidden. This allows us to understand whether the answer is 0 or not. Also answer is 0 when all edges of second type doesn't intersect, considering them to be segments of number line, except when k ≥ n - 1 — in this case answer is 1. Now we know that answer != 0. Frow all edges we have let's use only second type edges. If there aren't any of this edges we can add 1 to the answer, because of possibility of adding 0 edges to graph. For every vertex i, that has possibility of adding second type edges, let's add to answer 2^cnt, cnt — amount of vertexes on [i, min(i + k, n — k — 1)] without edges of second type out of them. Also it is necessary for all the second type edges to start in this segment.

Solution O(n + m) Solution O(m + log(n))

305E - Playing with String

Let's consider substring of s s[i... j], that all characters from i to j are palindrome centers, and i - 1, j + 1 are not. Every such substring can be treated independently from the others, and as we don't need to know it'sstructure let's consider only it length len. Let's calculate grundy[len] — Grundy function. If we want to cut character at position i 0 ≤ i < len then our game splits in to independent ones: first will have length i - 1, second — len - i - 2, as s[i - 1] and s[i + 1] are not centers of palindrome any more.

Solution

Hello!

A few hours later, on May 19th at 17:00 MSK, you are lucky to participate in Codeforces Round #184 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by: Gridnev Vitaliy (gridnevvvit), Ignatyev Alexander (aiMR). It’s our second round and I hope not last. We want to thank Gerald Agapov(Gerald) for help in preparation of this round, Michael Mirzayanov(MikeMirzayanov) for marvelous Codeforces and Polygon systems, Mary Belova(Delinur) for translating the problems.

We hope you will like these problems, and that it will be fun to solve them.

Also we strongly recommend you to read all the problems.

We wish everyone good luck and high rating!

UPD1: Scoring will be standart: 500, 1000, 1500, 2000, 2500.

UPD2: Editorial

UPD3: Congratulations to winners:

1. SillyHook06
2. hyplymac
3. HAPKOMAH

300A - Array

In this problem you just need to implement following algorithm. Split input data into 3 vectors: first will contain negative numbers, second positive numbers, third zeroes. If size of first vector is even move one number from it to the third vector. If second vector is empty, then move two numbers from first vector to the second vector. This solution works in O(n).

Аuthor's solution

300B - Coach

Input data represents a graph. If there is a connected component with at least 4 vertexes, then answer is  - 1. Every connected component with 3 vertexes is a complete team. Other teams are made from 1 or 2-vertex components. If amount of 2-vertex components is greater than 1-vertex answer is  - 1. Otherwise match 2-vertex components with 1-vertex. If there are some 1-vertex components left then split them into groups of three. This algorithm works in O(n + m). Also you could implement O(n⁴) solution.

Аuthor's solution

300C - Beautiful Numbers

Let's MOD = 1000000007. Let's precalc factorial values modulo MOD. fact[i] = i!%MOD, . Let i be an amount of digits equal to a in current excellent number. In this case we can find sum of digits in this number: sum = ai + b(n - i). If sum is good, then add C[n][i] to answer. In this problem it's impossible to calculate binomial coefficients using Pascal's triangle, because of large n. However it can be done this way C[n][i] = fact[n]inv(fact[n - i]fact[i]). inv(a) is multiplicative inverse element(modulo MOD). MOD is a prime number, so inv(a) = a^MOD - 2. Calculating this values for each i from 0 to n will give correct answer in O(nlog(MOD)).

Аuthor's solution

300D - Painting Square

This picture is helpful for understanding.

Let's consider problem D in graph terms:

We have matrix n × n, which represents a graph:

1. It is tree.
2. Every vertex, except leaves, has 4 children.
3. There are 4^k distinct vertexes, with distance k from root.

We need to color k vertexes of this graph. By that we mean also to color all vertexes on path from i to 1(root).

Knowing height of tree we can build it in unique way. Let's find height of tree in this way:

int height = 0;
while (n > 1 && n % 2 == 1) {
 n /= 2; height++;
}

Let's consider following DP: z[i][j] — number of ways to color graph height i in j steps.

Naive solution in O(k⁴log(n)):

z[0][0] = 1; z[0][i] = 0, i > 0; z[i][0] = 1, i > 0
z[i][j] = 0;
for(int k1 = 0; k1 <= j - 1; k1++) 
  for(int k2 = 0; k2 <= j - 1 - k1; k2++)
    for(int k3 = 0; k3 <= j - 1 - k1 - k2; k3++)
      {
         int k4 = j - 1 - k1 - k2 - k3;
  z[i][j] += z[i-1][k1] * z[i-1][k2] * z[i-1][k3] * z[i-1][k4];
  z[i][j] %= mod;
      }

But it is not what we whant in time terms. Let's consider current DP as polynomial coefficients: z[i][j] — coefficient of power j of polynomial i. In that case z[i + 1][j + 1] — coefficient of power j of polynomial i to the 4-th power. This approach allows to solve problem in O(k²log(n)). However this solution is quite slow, because of modulo operations. As you see, this modulo is not so big ( ≤ 10⁷), that allows us to reduce number of modulo operations, thus giving huge perfomance boost. Also it is possible to use FFT to solve in O(klog(k)log(n)).

Аuthor's solution. Uses FFT

Аuthor's solution. Without FFT

300E - Empire Strikes Back

Let's . val is upper bound for answer. val! is divisible by , you can easily prove it using facts about prime powers in factorial and following inequality . By the way, is called multinomial coefficient. So answer can't exceed 10¹³.

If n! divisible by den, then (n + 1)! is also divisible by den. That means that function of divisibility is monotonic and we can use binary search.

For every i, i = 2..., 10⁷, let's precalc max prime in i using linear sieve of Eratosthenes. For i it will be lp[i]. After that let's create a vector, with all primes less then 10⁷.

Now let's calculate following values cnt[i] — amount of numbers a, i <  = a.

Now me can factorize denominator like this:

for(int i = max; i>=2; i--) {
 if (lp[i] != i) 
  cnt[lp[i]] += cnt[i];
 cnt[i / lp[i]] += cnt[i];
}

Finally we use binary search from lf = 1 to .

Аuthor's solution

Hello!

A few hours later, 25 апреля в 19:30 MSK, you are lucky to participate in Codeforces Round #181 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by: Gridnev Vitaliy (gridnevvvit), Ignatyev Alexander (aiMR). We want to thank Gerald Agapov(Gerald) for help in preparation of this round, Michael Mirzayanov(MikeMirzayanov) for marvelous Codeforces and Polygon systems, Mary Belova(Delinur) for translating the problems.

About authors: me and Alexander are third year students of Mathematics Department, Saratov State University. It’s our first round and I hope not last.

We hope you will like these problems, and that it will be fun to solve them.

Also we strongly recommend you to read all the problems.

We wish everyone good luck and high rating!

UPD: Scoring will be dynamic. Problems are sorted by increasing order of difficulty.

UPD1: Editorial here

UPD2: Contest finished. Congratulations to winners:

1. ballmaids02
2. VIProgrammer
3. emachaidze