Hello CodeForces Community,

I’d like to invite you to CodeChef November Cook-Off at https://www.codechef.com/COOK64.

Time: 22nd November 2015 (2130 hrs) to 23rd November 2015 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/COOK64

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Problem Setter: Sergii Nagin
Russian Translator: Sergii Nagin
Editorialist: Sunny Aggarwal
Problem Tester: Istvan Nagy
Mandarin Translator:: Hu Zecong
Contest Admin: Praveen Dhinwa
Vietnamese Translator: VNOI Team
Language Verifier: Rahul Arora

It promises to deliver on an interesting set of algorithmic problems with something for all.

Good Luck! Hope to see you participating!!

426A - Sereja and Mugs

Lets count the sum of all elements Sum and value of the maximal element M. If Sum - M ≤ S then answer is yes, otherwise — no.

426B - Sereja and Mirroring

Lets solve problem from another side. We will try to cut of matix as many times as we can. Cut means operation, reversed to operation described in statement. To check, can we cut matrix we need to check following conditions:
1). n mod 2 = 0
2). a_i, j = a_{n - i + 1, j} for all 1 ≤ i ≤ n, 1 ≤ j ≤ m.

425A - Sereja and Swaps

Lets backtrack interval on which will contain maximal sum. To improve our sum we can swap not more then k minimal elements from the interval to k maximal elements that don't belong to interval. As n isn't big we can do it in any way. Author solution sort all elemets from interval in increasing order and all elements that don't belong to interval by descreasing order. We will swap elements one by one while we haven't done k swaps and we have some unswaped elements in first set and we have some unswaped elemets in second set and swap is optimal(we will optimize the answer after this swap). Author solution works in time O(n³·log(n)).

Is there some ideas how to solve this problem in time O(n) or O(n·log(n)) ?

425B - Sereja and Table

Note, that if we have two arrays x[1..n], 0 ≤ x_i ≤ 1 and y[1..m], 0 ≤ y_i ≤ 1, then described matrix can be showed as next one: a_i, j = x_i xor y_j.
If n ≤ k, then we can backtrack array x and using greedy find best y. Otherwise there will be atleast one i, such that we will not change any cell in row number i. So we can simply bruteforce some row and use it like x. Then we use greedy and find y. From all possible rows we choose most optimal. Such row will be as number of mistakes is lower then number of rows, so it isn't possible to have atleast one mistake in each row.

Greedy means next algorithm: for every element of y we will look, will it be better to choose it like 0 or 1. To find better choise, we will count number of different bits in x and current(lets it be j) column. If number of different if lower then count of same cells we will set y_j = 0, otherwise y_j = 1.

425C - Sereja and Two Sequences

In thgis problem we will use dynamic programming: dp_i, j — minimal pozition of deleted element in second array, such that we have made first operation j times and have deleted not more then i elements from first array.

Lets decided how to calculate transfers. Standing in pozition dp_i, j we can change nothing and go to pozition dp_{i + 1, j}, by other words make transfer dp_{i + 1, j}:  = min(dp_{i + 1, j}, dp_i, j). What happens when we make first operation with fixed prefix(by i-th element) in first array? We should find element in second array with number greater dp_i, j and value equal to a_i, lets its pozition is t, so we need to make transfer dp_{i + 1, j + 1}:  = min(dp_{i + 1, j + 1}, t).

How to find required element quickly: lets just do vector of pozition in second array for all different elements that contains in second array. Then we can simply use binary search.

425D - Sereja and Squares

Lets line x = k contain not more then points. Then for each pair of points on this line (lets it be (k, y₁) and (k, y₂)) check: is there squere that contain them as vertexes. So we should check: is there(in input) pair of points (k - |y₂ - y₁|, y₁) and (k - |y₂ - y₁|, y₂), or pair (k + |y₂ - y₁|, y₁) and (k + |y₂ - y₁|, y₂).

Lets delete all watched points, and reverse points about line x = y. Then each line x = k will contain not more then points. Will solve problem in the same way.

Now we should learn: how to check is some pair of points(on one vertical line) in input. Lets write all of this pairs in vectors. Each vector(for every line) will contain pairs that we should check on it. Suppose, that we check it for line number k. Lets mark in some array u for all points with x-coordinate equal to k u_y = k. Now to check is our pair with y-coordinates (y₁, y₂) on line we can simply check following condition: u_y1 = u_y2 = k.

425E - Sereja and Sets

First, lets look at F(S). First, we sort all intervals by second coordinte and then go by them in sorted order. And if current interval don't intersected with last taken to the optimal set, we get our current to the set.

Our solution will be based on this greedy. Solution of the problem is next dynamic:
1). number of position of second coordinte of interval
2). number of intervals in good set
3). second coordinate of last taken interval to the optimal set

How should we make transfers? Lets note that when we know dp_{i, count, last} we can change last by i, or not change at all. Lets look what happens in every case. In first case last is changed by i, so we should take to optimal set atleast one of the inervals: [last + 1, i], [last + 2, i], ..., [i, i], number of such intervals i - last, number of ways to get at least one of them is 2^i - last - 1. All other intervals: [1, i], [2, i], ..., [last, i] we could get as we wish, so we have 2^last ways. So total number of transfers from dp_{i, count, last} to dp_{i + 1, count + 1, i} is (2^i - last - 1)·(2^last). If we count number of transfers from dp_{i, count, last} to dp_{i + 1, count, last}, we can simply use number 2^last(as described early).

Also we shouldn't forget about trivial case dp_i, 0, 0.

So now we have quite easy solution.

Hello everyone!

Codeforces Round #243 will take place on Sunday, April 27th at 19:30 MSK. This is my eleventh Codeforces round and I hope not the last.

I'd like to thank Gerald and KADR for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

Problem point values in first division 500-1000-1500-2000-2000. In second division — standard.

Gl & hf ! :)

Tutorial.
Statistics.

381A - Sereja and Dima

Simply do the process described in the statment.

381B - Sereja and Stairs

Calculate the amount of each number. For all the different numbers — maximum possible times of use isn't more than 2 times. For the maximum is is only — 1.

380A - Sereja and Prefixes

Generate the first number 100000. Will in turn handle the requests, if the request gets to the point of adding one number, just print it. Otherwise see what element will meet our and just print it from precalculated array.

380B - Sereja and Tree

Lets generate a tree as described in the statment. For each request to add items we just add a segment for a certain level. At the request of the number of items we just go through all the lower levels, considering the leftmost and the rightmost vertex in the subtree. To each level will take all intervals that it owns and for each check — whether it intersects with the interval that we have generated in the current stage. If so, simply add items to the set. The complexity of solving O(n·m).

380C - Sereja and Brackets

We will support the segments tree. At each vertex will be stored:
a_v — the maximum length of the bracket subsequence
b_v — how many there it open brackets that sequence doesn't contain
c_v — how many there it closed brackets that sequence doesn't contain
If we want to combine two vertices with parameters (a₁, b₁, c₁) and (a₂, b₂, c₂), we can use the following rules:
t = min(b₁, c₂)
a = a₁ + a₂ + t
b = b₁ + b₂ - t
c = c₁ + c₂ - t

380D - Sereja and Cinema

In order that no one would be upset, every person except first should sitdown near someone else. Now when any human comes we know that for one side of him there will not be any people. Will use it. We will support the interval exactly occupied seats. If the first person is not known, it is possible that we have 2 such intervals. Now only remains to consider carefully all the cases that could be, because at each iteration we know exactly how many people will sit on some certain place.

380E - Sereja and Dividing

Note that at any particular segment we are interested not more than 60 numbers. The greatest number enters with a coefficient of 1/2, the following — 1 /4, 1 /8, and so on. Thus to solve the problem we need to know for each number: how many segments to include it as a maximum , as a second maximum , a third , and so on until the 60th .

What to know such information is sufficient to find 60 numbers large jobs left and right. This can be done carefully written the set or dsu.

Now, with this information we can calculate by countind number of segments which contain our element. It is not difficult to do, knowing the positions of elements , large then current . Let the position of elements on the left: p₁> p₂> ... > P_s1. And positions right: q₁ < q₂ < ... < q_s2. So we should add value .

All details can be viewed in any accepted solution.

Hello everyone!

Codeforces Round #223 will take place on Sunday, January 12th at 19:30 MSK. This is my tenth Codeforces round and I hope not the last.

I'd like to thank Gerald for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

This is the first round this year. Incidentally, the first round last year for both divisions was also mine (by statistics +1/-1 is was the coolest of rounds that I gave). I hope that this time the problems will be even more interesting for you. Will it? Will find it out after the round :)

Gl & hf ! :)

Problem point values will be standart for both divisions.

Разбор задач Codeforces Round #215

368A - Sereja and Coat Rack

Each time we will go through the array and look for the minimal element which is not yet marked. If we find an item, we add it to the answer and mark it, otherwise we will subtract the penlty from answer.

368B - Sereja and Suffixes

We will count value ans_i — number of different elements on the suffix from i. For calculation will walk from the end of the array, and we count ans_i = ans_i + 1 + new_ai, new_ai equals to 1, if element a_i has not yet met and 0 otherwise.

367A - Sereja and Algorithm

If you look at what is written in the statment, it becomes clear that the algorithm finishes its work, if we can get a string like: xx, yy, zz, zyxzyxzyx... and all its cyclic shuffles. To check you just need to know the number of letters x, y and z separately. Quantities can be counted using partial sums.

367B - Sereja ans Anagrams

We will divide the sequence on min(n, p) sequences. 1-st, (1 + p)-th, (1 + 2·p)-th, ... element will go to the first sequence, 2-nd, (2 + p)-th, (2 + 2·p)-th... will go to the second sequence and so on. Now you need to find an answer for each of them, considering that p = 1. This can be solved by a simple method. You can go along the sequence from left to right and count the number of occurrences of each number. If the number of occurrences of each number will match the number of occurrences of the same number in the second sequence, then everything is OK.

367C - Sereja and the Arrangement of Numbers

Clear that we need to collect as many of the most expensive properties that would have been possible to build the array. Note that having n numbers, we have m = n·(n - 1) / 2 binding ties. See that this is a graph in which to do Euler path, adding as little as possible edges. For n%2 = 1 — everything is clear, and for n%2 = 0, you need to add an additional n / 2 - 1 rib. Why? This is your homework :)

The detailed explanation can be found here.

367D - Sereja and Sets

Replace out sets by array, where the element — the number set to which its index belongs. Now take all the consequitive sub-arrays with lengths of d and find a set of elements that were not found in that sub array. Clearly, if we as a response to select a subset of such set, it does not fit us. Remember all those "bad set." As we know all of them, we can find all the "bad" subsets. Now we choose the set with maximum count of elements which is not a bad set. It is better to work here with bit masks.

367E - Sereja and Intervals

We assume that the intervals are sorted, and in the end we will multiply the answer by n!, We can do so, as all segments are different.

Consider two cases n > m and n ≤ m. It would seem that you need to write different dynamics for them, but not difficult to show that in the first case the answer is always 0 . The second case is the following dynamics : dp_i, l, r, i — how many numbers we have considered , l, r — only in this interval will be present number i. Also, we will need an additional dynamic s_i, l, i — how many numbers are considered , l — how many segments are already closed , and i does not belong to any segment . There will be 4 transfers, since every number we can not begin and end with more than one segment.

Now we should add x to our solution, it is quite simple: just add another parameter 0 / 1 in our dynamics, if we had such a element in the beginning of some interval or not. With out dynamics, it is not difficult.

For more details check out any solution that passed system tests.

Hello everyone!

Codeforces Round #215 will take place on Tuesday, November 26th at 19:30 MSK. This is my ninth Codeforces round and I hope not the last.

I'd like to thank Gerald, Berezin, Aksenov239, MikeMirzayanov and Cenadar for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

Problem point values div1: 500-1000-1500-2000-2000
Problem point values div2: 500-1000-1500-2000-2500

Gl & hf ! :)

Contest is over, thank you for participation. Sorry for mistake in problem A. Hope, that problems were interesting for you, also I hope that bugs didn't spoil your mood.
Have a nice evening! :)

Also I'd like to congratulate rng_58, he have 3010 rating now!

Tutorial.

358A - Dima and Continuous Line

Author — Berezin

If our line has self-intersections, that some pair of semi-circles exists, which intersect each other.
Let points x₁ < x₂ are connected with a semi-circle and points x₃ < x₄ are connected with another semi-circle. Then this semis-circles intersect if one of the conditions is true:

1). x₁ < x₃ < x₂ < x₄
2). x₃ < x₁ < x₄ < x₂

Let’s iterate trough all pairs of semi-circles, and check if the semi-circles intersect each other. So, the solution will have complexity O(N²) what satisfied the constrains.

358B - Dima and Text Messages

Author — Berezin

It’s clear, that adding new random symbols means, that we can simply omit them, they don’t change the structure of the phrase:  < 3word₁ < 3word₂ < 3... word_N < 3. Let’s determine the phrase before inserting random elements: s = " < 3" + word1 + " < 3" + ... + " < 3" + wordN + " < 3". Lets i —is an index in s, we are waiting for. At the beginning i = 0; we will iterate though the sms and when we will meet the symbol which equals to s_i we will simply increment i.

if at some moment |s| ≤ I we found all needed symbols and answer is yes, otherwise – no.

358C - Dima and Containers

Author — Berezin

We know all the numbers at the beginning, so, it’s clear, that we want pop three maximums. We can “precalculate “ maximums with finding next zero and iterating through all numbers between two zeroes.
We should do pops from different containers, so let’s save maximums in the top of the stack, in the beginning of the queue and on the beginning of the dek. (you can do this in some other way) We should determine, where will be stored the 1st, 2nd and 3rd maximum. For example, the first(the biggest one) – in the stack, second – in queue, and the third – in dek. “trash” – other numbers we can save into the end of the dek.
Also you need to catch cases, when two or less numbers are between zeroes.

358D - Dima and Hares

Author — Sereja

Let’s look at the first hare: we chose them befoe second, or after. If it is chosen after the second, than the solution from the 2nd hare to the last doesn’t depend on the first one, otherwise, we will receive the same but before the second hair will be obviously the feed hair. So, we have two dinamics:
1). d0i — answer for suffix as a separate task.
2). d1i — answer for suffix if the previous hair for this suffix is feed already.
Movements:
d0n  =  an
d1n  =  bn
d0i  =  max(ai  +  d1i  +  1,  bi  +  d0i  +  1)
d1i  =  max(bi  +  d1i  +  1,  ci  +  d0i  +  1)
answer is d01;

358E - Dima and Kicks

Author — Sereja

The first thing to understand is that the answer is the divisor of maximal-length sequence of standing one by one ones. (1111…11)
Let’s iterate trough this number. Now we should check the table knowing the value of K. Let’s find the most left of ones, and choose from them the most top. Let it be (X, Y). then after each step Dima can appear inly in cells which look like: (X + K * a, Y + K * b). Let such cells are the vertexes of the graph. And sequences of ones – the ribs. We will build the graph. We should check that there are no additional ones in table. We should also check if the graph is connected and has en Euler’s path. The value of K is the next answer under the all conditions. The correct implementation will have the complexity O(N * N * log(N)). In reality it will be never achieved.

Editorial for Codeforces Round #204

352A - Jeff and Digits

Solution is looking for few cases:
1. If we do not have zeros, then the answer is -1.
2. If we have less than 9 fives, then the answer is 0.
3. Otherwise, the answer is:
4. 1. The maximum number of fives divisible by 9
4. 2. All zeros, we have

352B - Jeff and Periods

We will go through the array from left to right. At each step, we will store the arrays:
1. next_x — the last occurrence of the number x
2. period_x — period, which occurs x
3. fail_x — whether a time when the number of x no longer fit

Now, when we get a new number we considering the case when it is the first, second or occurred more than twice.
All the cases described in any past system testing solution.

351A - Jeff and Rounding

Initially, we should remember the number of integers — C. On next step we will round down all numbers and count the sum. Now we can change the sum, rounding up some numbers, with those not matter what kind of, the main thing — how many. Consider a couple what we could get:
1. (int, int) (c₁)
2. (int, double) (c₂)
3. (double, int) (c₃)
4. (double, double) (c₄)

Iterate over the number of pairs of the first type. Then we know the total number of second and third type and number of the fourth type:
1. c₂ + c₃ = C - 2c₁
2. c₄ = N - (c₁  +  c₂  +  c₃)
Check to see if you can get such numbers (enough for us count of integers and real numbers, respectively). We find that we can round up from c₄ to c₄ + c₂ + c₃ numbers. We will find the best choise.

351B - Jeff and Furik

ote that after each step, the number of inversions in the permutation is changed by 1. Let us turn to the inversions of the permutation — let them be I pcs. It is clear that when we have one inversion, then the answer — 1. Now we will see how to use it further:
1. it is clear that after a Jeff's step inversions will become lower by 1
2. it is clear that after a Furik's step inversions will be on 1 lowerwith porbability of 0, 5, and on 1 greater with probability of 0, 5.
3. we have the formula for an answer ans_I = 1 + 1 + ans_{I - 1 - 1} × 0.5 + ans_{I - 1 + 1} × 0.5
4. after transformation we have ans_I = 4 + ans_I - 2.

351C - Jeff and Brackets

How to solve the problem for small NM? Just use the dynamic programming dp_i, j — minimum cost to build i first brackets with the balance j. Transfers are simple:
1. dp_i, j + a_i + 1 -> dp_{i + 1, j + 1}
2. dp_i, j + b_i + 1 -> dp_{i + 1, j - 1}
3. we make transfers only when balance will be non-negative
4. starting state dp_0, 0 = 0

In this problem, we can assume that the balance will never exceed 2N. The proof is left as homework.

And by using this fact problem can be done by erecting a matrix to the power:
1. lets T_i, j — cost of transfer from balance i to balance j, using N brackets
2. (T^M)_0, 0 — answer to the problem

351D - Jeff and Removing Periods

After the first request we can sort the numbers and for further moves will be able to remove all occurrences of a certain number. So the answer is the number of different numbers + 1 if there is no number, occurrence of which form an arithmetic progression.

Number of different numbers on a segment — standart problem, can be done O(N^1.5) with offline algorithm.

The problem about finding the right number will be solved in a similar algorithm:
1. lets sort queries like pairs (l_i / 300, r_i), we use integer dividing
2. learn how to move from the interval (l, r) to intervals (l - 1, r), (l + 1, r), (l, r - 1), (l, r + 1) with complexcity O(1)
3. by means of such an operation will move from one segment to the next, in the amount of the operation algorithm will works O(N^1.5)

It remains to learn how to make the change on the interval by 1 element. Such a problem can be solved quite simply:
1. we craete deque for all value of numbers in array
2. depending on changes in the segment will add / remove items to the start / end of the respective deque
3. check whether the resulting deque is arithmetic progression. it will be homework.

351E - Jeff and Permutation

We make the zero step, replace the elements on their modules.

The first thing you need to understand the way in which we will build our response. After selecting a few ways to understand the fact that initially you need to determine the sign of the largest numbers.

Consider the case where the current step we have only one maximal element. It is clear that if you put a sign - all the elements on the left of this will form an inversion, while on the right there will be no inversions. If we do not put a sign - it will all be the opposite. We select the best one and cross out the number of the array, it will not affect to some inversion.

Now we should understand how to read the response when the highs more than one. We write the dynamics dp[i][j] — how much inversions can you get, when we looked at the first i higest values and j from them lefted as possitive. Of these dynamics is not difficult to make the transition and get the answer.

And so we have a simple and short algorithm:
1. Iterates until the array is not empty
2. Find all the maximal elements
3. Calculate dynamics and find right signs
4. Remove elements from an array

For more details view any passed system tests solution.

Hello everyone!

Codeforces Round #204 will take place on Friday, October 4th at 19:30 MSK. This is my eights Codeforces round and I hope not the last.

I'd like to thank Gerald, yvasyliv, Cenadar and Zlobober for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

Problem point values for the first division: 1000-1000-1500-2000-2000.
Problem point values for the second division: standart.

Tutorial.

Gl & hf ! :)

315A - Sereja and Bottles
Just check for each bottle, can I open it with another. In this task can pass absolutely any solutions.

315B - Sereja and Array
We will support all of the elements in the array, but also we will supprt additionally variable add: how much to add to all the elements. Then to add some value to every element we simply increase the add. In the derivation we deduce the value of the array element + add. When you update the item we put to a value, value that you need to put minus the current value of add.

314A - Sereja and Contest
Note that if we remove some of the participants, we never remove the participants with lower numbers as theirs amount will only increase. So just consider the sequence of all the participants, and if the participant does not fit we delete him.

314B - Sereja and Periods
It is clear that we can use greedy algorithm to look for the number of occurrences of the 2nd string in the first string, but it works too slow. To speed up the process, you can look at the first line of the string that specifies the second period. And the answer is divided into how many string you need to set the second string. Next, we consider our greedy algorithm. We are going by the first string, till we find the first character of the second string, then the second, third and so on until the last, then again find the first, second, and so the cycle. It is clear that if we stand in the same twice in a state in which the positions in the first string corresponds to one character string that determines the period and the position of the second string are the same, then we obtain the period. When we find this period, we can just repeat it as many times as possible.

To better understand, I advise you to read any accepted solution.

314C - Sereja and Subsequences
It is clear that we need to calculate the sum of the products of elements of all the different non-decreasing subsequences of given sequence. Let's go through the sequence from left to right and maintain the array q[i]: what means the sum of all relevant sub-sequences, such that their last element is equal to i. Clearly, if the next number is x, then you need to put q[x] = sum (q[1] + q[2] + ... + q[x]) * x + x. The answer to the problem is the sum of q[i]. To find all the amounts you can use Fenwick tree.

314D - Sereja and Straight Lines
Roll all at 45 degrees using the transformation: (x, y) -> (x ', y'): x '= x + y, y' = x-y. Next you need to place two lines parallel to the coordinate axes. Sort the points by the first coordinate. Next, we use a binary search for the answer. May we have fixed a number, you now need to check whether it is enough or not. Note that now we need to put two strips of width 2 * fixed amount that they would have to cover all the points. Suppose that some point should be close to the left side of the vertical strip, then for all points that do not belong to the strip we find the minimum and maximum second coordinate. If the difference between the found coordinates no more then 2 * fixed quantity, the strip can be placed, otherwise — no.

soon...

Hello everyone!

Codeforces Round #187 will take place on Friday, June 7th at 19:30 MSK. This is my seventh Codeforces round and I hope not the last.

I'd like to thank Gerald, Furko and Aksenov239 for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

Gl & hf ! :)

tutorial.

302A - Eugeny and Array
If the length of the given segment is even and count of 1 in input is not lower then half of the length of the segment and count of -1 in the input is not lower then half of the length of the segment so we have answer 1, otherwise 0.

302B - Eugeny and Play List
For each song we will count moment of time, when it will be over (some sums on the prefixes, for example). Further, we will use binary search of two itaratos method to solve the problem.

301A - Yaroslav and Sequence
Using dfs we will find number of numbers that we can set as positive. Note that we can either set all of the numbers as positive or leave one number(any) as negative. If we can obtain all numbers as positive, we just return sum of modules of the numbers, but if we cannot we will count the same sum and will subtract minimal modular value multiple 2 from sum.

301B - Yaroslav and Time
We will use binary search to find the answer. Further we will use Ford-Bellman algorithm. On each step we will have an array of maximum values on timer, when we stand in some point. On in transfer we will check: will our player stay alive after travelling beetwen points. If we can make transfer, we will update value of the final destination point. Becouse of a_i<=d and integer coordinates we haven't optimal cycles, and solution exists.

301C - Yaroslav and Algorithm
We will use ? as iterator. In the begin we will set ? before the number. Then we will move it to the end of the string. Then we will change ? to ?? and we will move it to the begin, while we have 9 before ??. If we have another digit, we just increase it, and finish the algorithm. If we have ?? at the begin, we change it to 1, and end the algorithm.

Look for accepted solutions for better understanding.

301D - Yaroslav and Divisors
Lets add all pair: (x,y) ((d[x]%d[y]==0) || (d[y]%d[x]==0)) to some lest. We can count such pairs using Eretosphen algorithm. Here will be O(n*log(n)) sych pairs using fact, that we have permutation. We will sort all this paairs using counting-sort. Also we will sort given in input intervals. For each given interval we should count number of pairs that countained in given them . Such problem we can solve using Fenvik tree. On each step we will add segments(that are sorted by right side). On each step we will update Fenfick-tree that count number of added pairs on some suffix. Using such tree if it easy to count the answer. So we have O(n*log^2(n)) solution.

301E - Yaroslav and Arrangements
We will build the needed arrays sequentially adding numbers. Let's look at what states we need. First, it is obvious that you need to keep the number of ways to build an array of already added numbers, secondly you need to know the total amount of added numbers. Now let's look at what happens when we add a new number (that is greater than all of the previous in a certain amount). It is clear that the added numbers should stand between the numbers 1 to less. In this case, if we put two new numbers in a row, between them should stand more (since we already have placed less). It is obvious that you need to cover all the previous numbers (among which must stand newly added). Thus, we have another state: the number of integers between which we should put the new ones. Thus we have the dynamics of the four parameters: dp [all] [ways] [lastnumber] [counttoadd]. Transfer. It is clear that you need to add at least counttoadd numbers, but how will this affect the number of ways to arrange the numbers? It's simple. Suppose we added number x, then the number of ways to be multiplied by the value of Q (x-counttoadd, counttoadd), where Q (x, y) — the number of ways to assign the same x balls in y different boxes. Q (x, y) = C (x + y-1, y-1) where C (x, y) — binomial coefficient.

Hello everyone!

Codeforces Round #182 will take place on Sunday, May 5th at 19:30 MSK. This is my sixth Codeforces round and I hope not the last.

I'd like to thank Gerald and sdya for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

Gl & hf ! :)

Because of technical issue the start of the contest was unsuccessful. Sorry about it. The contest will be UNRATED.

Tutorial.

296A - Yaroslav and Permutations
Note that after applying the operations of the exchange, we can get any permutation of numbers. Not difficult to understand that the answer is "YES", if you can place a single number that it would not stand in the neighboring cells. Thus, if a some number is meeted C times, it must fulfill the condition C <= (n+1) / 2.
296B - Yaroslav and Two Strings
Будем решать обратную задачу: посчитать количество способов сделать сравнимые пары.
Для начала посчитаем количество способов сделать первую строку меньше равной второй.
Это количество равно произведению количества способов сделать это для каждой позиции по отдельности,так как они все позиции независимы. Посчитаем такую же величину, но когда вторая строка меньше-равна первой. И аналогично посчитаем количество способов сделать две строки равными. Для каждого символа величины можно считать простым циклом.
Теперь возьмем величину 10 в степени количества знаков вопроса во входном файле и отнимем полученный ответ на обратную задачу, это и будет ответом.
295A - Greg and Array
Для того, что бы прибавить значение d на отрезке [x,y] достаточно завести массив b и поставить значения
b[x] += d
b[y+1] -= d
Дальше за один проход по массиву легко восстанавливаются все числа.
Применим данный метод дважды: сначала для запросов, а потом для операций(зная сколько раз мы ее выполним).
295B - Greg and Graph
Для решения задачи нужно хорошо понимать принцип работы алгоритма Флойда.
Общий вид алгоритма Флойда:
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
a[i][j] = min(a[i][j], a[i][k]+a[k][j]);
То есть на каждом шаге мы пытаемся пропустить путь через вершину К.
Будем не удалять вершины, а добавлять(идя с конца).
На каждом шаге будем пробовать пропустить путь между всеми вершинами через новую.
Таким образом мы получим решение, работающее за кубическое время.
295C - Greg and Friends
Заметим, что на каждом шаге нас интересует только положение лодки(номер берега) и количество людей веса 50 и 100 на каждом береге. При чем количество людей на одном береге полностью определяется через другой.
Для поиска минимального количества переправ будем использовать волновой алгоритм, основанный на этом состоянии.
Для нахождения количества способов просто добавим сумму всех переходов в состояние при переходе будем переносить все способы из одного состояния в другое умножая на количество способов выбрать людей, которые нужны для перехода из одного состояний в другое.
295D - Greg and Caves
Будем пользоваться динамическим программированием: dp[i][j] — сколько существует способов построить фигуру, что в строке i будет ровно j столбцов занятыми черными клетками и всем, что между ними. При этом фигура должная не убывать (иными словами мы берем только верхнюю часть фигуры).
Как делать переход? Заметим, что dp[i][j] = 1+dp[i-1][2] * (j-2+1)+ ... +dp[i-1][l] * (j-l+1)+ ... +dp[i-1][j].
Распишем это: dp[i][j] = 1+dp[i-1][2] * j+ ... +dp[i-1][l] * j+ ... +dp[i-1][j] * j — dp[i-1][2] * 1 — dp[i-1][3] * 2 — ... — dp[i-1][j] * (j-1).
Понятно, что если завести частичные сумму, то данные величины считать становится очень просто.
Как посчитать полный ответ: будем перебирать номер максимального подходящего t(обозначенного в условии).
Теперь единственное отличие, это то что следующая строка должна содержать строго меньше столбцов. То есть имеем аналогичный переход, с -1 слагаемым.
Так же заметим, что зафиксировав "основу" мы должны домножить количество способов на число способов разместить ее на плоскости, то есть основу шириной j мы можем поставить (m-j+1) способами.
295E - Yaroslav and Points
Научимся решать задачу: найти сумму расстояний между точками.
Если расписать, что происходит при добавлении одной точки, то получим формулу: x_i*(2*i-n) Где x_i — отсортированные координаты, а n общее количество точек.
Научимся зная ответы для двух отрезков точек знать ответ для их объединения.
Понятно, что для подсчета такой информации нужно всего лишь сложить два ответа,
и добавить сумму координат первого множества умноженное на некоторое число и
и добавить сумму координат второго множества умноженное на некоторое, возможно другое, число.
Таким образом зная ответы для некоторых отрезков общий ответ.
Будем использовать корневую декомпозицию или декартово дерево для хранения таких отрезков.
Не сложно понять, что вставка и удаление делается достаточно быстро для этих структур.
Например для корневой декомпозиции можно каждый раз просто вырезать и вставлять точку в нужные отрезки, а если множество стало содержать длинные отрезки или много отрезков, то просто перестроим его заново. Асимптотика решения не меняется.

Hello everyone!

Codeforces Round #179 will take place on Thursday, April 11th at 19:30 MSK. This is my fifth Codeforces round and I hope not the last.

I'd like to thank Gerald for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

Problems point values for 1 division will be standart. For the 2 division it will be: 500-1500-1500-2000-2500.

Gl & hf ! :)

Contest is over. I hope that problems vere interesting for you.

Division 1 winners:
1). marcina007
2). yeputons
3). gawry
4). KADR
5). enot110

Division 2 winners:
1). goie
2). Koblyk
3). Beriand

Ideas of the solutions are here.

Hello everyone!

Codeforces Round #167 will take place on Wednesday, February 13th at 19:30 MSK. This is my fourth Codeforces round and I hope not the last.

I'd like to thank Seyaua, sdya and Gerald for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

Problems’ point values will be standard in both divisions.

I strongly recommend you to read ALL the problems.

Gl & hf ! :)

Contest is over. Congratulations to div1 winners:
1). tmt514
2). tourist
3). scott_wu
4). rng_58
5). dreamoon_love_AA

and div2 winners:
1). yefllower
2). Harlos
3). pseudopodia

You can view tutorial here.

272A - Dima and Friends

We will bruteforce number of fingers that will be show Dima, then if total sum of fingers = 1 modulo (n+1), Dima will clean the room. So we should increase answer if the remaining part after division by (n+1) is not 1.

272B - Dima and Sequence
First of all — f(i) is number of ones in binary presentation of number. We will repair all numbers to functions of them. Now we have to find number of pairs of equal numbers. Lets Q[i] — number of numbers with i bits, the answer will be sum of values Q[i]*(Q[i]-1)/2 for all i.

273A - Dima and Staircase
Lets L will be the answer after last block, last block was (w1, h1), next block is (w2, h2). Next answer will be max(L+h1, A[w2]), where A — given array. At the beggining we can suppose that L = 0, w1 = 0, h1 = 0.

273B - Dima and Two Sequences
Not hard to understand that answer will be (number of numbers with first coordinate = 1)! * (number of numbers with first coordinate = 2)! * ... * (number of numbers with first coordinate = 10^9)!/(2^(number of such i = 1..n, that Ai=Bi)). The only problem was to divide number with non prime modulo, it can be easely done if we will count number of prime mulpiplies=2 in all factorials. Then we can simply substract number that we need and multiply answer for some power of 2.

273C - Dima and Horses
Not hard to understand that we have undirected graph. Lets color all vetexes in one color. Then we will find some vertex that is incorrect. We will change color of this vertex, and repeat our search, while it is possible. After every move number of bad edges will be decrease by 1 or 2, so our cycle will end in not more then M operations. So solutions always exists and we need to change some vertex not more then M times, so we will take queue of bad vertexes and simply make all operations of changes.

273D - Dima and Figure
Good picture is connected figure that saticfy next condition: most left coordinates in every row of figure vere we have some cells will be almost-ternary, we have the same situation with right side, but here we have another sign. So it is not hard to write dp[i][j1][j2][m1][m2] numbr of figures printed of field size i*m, where last row contain all cells from j1 to j2, the most left coordinate will be m1, the most right coordinate will be m2. But it is not enough. We have to rewrite it in way that m1 will mean — was there some rows j and j+1 that most left coordinate if row j is bigger then most left coordinate in j+1. So now it is not hard to write solution with coplexity O(n*m*m*m*m). But we should optimize transfer to O(1), is can be done using precalculations of sums on some rectangels.

273E - Dima and Game
will be added soon.

Lets discuss problems here.

262A - Roma and Lucky Numbers

This problem just need to simulate everithing that was given in statment.

262B - Roma and Changing Signs

We will "reverse" numbers from the begining to the end while numebrers are negative and we did't spend all k operations.
In the end there can leave some operetions, and we will "reverse" only one numeber, with minimal value k(that remains) times.

261A - Maxim and Discounts

Ofcourse the most optimal way is to use discount with minimal q_i. We will sort our numbers and will go from the end to begin of the array. We will by use our discount as soon as it will be possible. It's not hard to see that we will buy all the items with numbers I (zero-numeration from the end of the sorted array) such, that I%(q+2)<q.

261B - Maxim and Restaurant
If all people can come, we will return answer as n.
If it is impossible, there will be finded some person that will be the last to come. We will brtueforce this value. Then we will detrminate dp[i,j,s] in how many ways j persons from the first i with total length s can be in the resturant. It is easy to calculate.
Then we will add to the answer values dp[n][i][s]*i!*(n-1-i)! for all i,s such that s+p[h]>P. Where P — total length of the table, p[h] — length of the fixed person.

261C - Maxim and Matrix
For fixed m, the sum in the last row will be 2^(bit_count(m+1)-1). So now if T is not power of 2, answer is 0. Else we can find number of bits that we need. And know we have stndart problem. How many numbers form 2 to n+1 have exactly P bits in binary presentation of the number. It is well known problem can be done using binomial cooficients. We will count number of numebers smaller then out number with fixed prefix.

261D - Maxim and Increasing Subsequence

This problem can be done using dp[i,j] where we can end our increasing sequence with length i and last number j. Its not hard to understand that number of states will be n*b. To make a tranfer we need to know array first[j] — first position of the number j in the sequence b, next[i][j] — first position of the number j in the sequence b after position i.

Now its easy to calculate all values.

261E - Maxim and Calculator

I will add tutorial later. But I will give you a hint: number of numbers with maximal prime divisor<=100 is near 3000000 numbers.

Hello everyone!

Codeforces Round #160 will take place on Sunday, January 13th at 19:30 MSK. This is my third Codeforces round and I hope not the last.

I'd like to thank Seyaua, sdya and Gerald for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

Problems’ point values will be standard in both divisions.

I strongly recommend you to read ALL the problems.

Gl & hf ! :)

Contest is over, I hope it was interesting for you :)

Congratulations to div1 winners:
1). PavelKunyavskiy
2). Dmitry_Egorov
3). Nerevar
4). Egor
4). gawry

and div2 winners:
1). Pad
2). nirvanafreak
3). pablobce

You can view tutorial here.

255A - Greg's Workout

It is not hard problem. We must calculate sums of numbers for each group and print group with maximum count.

255B - Code Parsing

Not hard to see that after few operations of first type string will become: x..xy..y. After fer operations of second type, there will be only letters of one type, count of this letters will be: |count(x) — count(y)|

256A - Almost Arithmetical Progression

Заметим, что ответ это длина последовательности: a, b, a, b, ... где a и b — некоторые целые числа. Зафиксируем одно число (допустим a), будем перебирать число b, и считать какой мы получим ответ, если это будет последнее число в последовательности. Заметим, что для фиксированных a, b — ответ считается жадно. Так же будем действовать и тут. Будем искать последнее вхождение числа b до зафиксированного, что между ними есть число a, и будем брать ответ как длина до найденного числа +2 (икасть будем с помощью метода двух указателей). Так же нужно рассмотреть случай, когда это будет 1е или 2е вхождение в последовательность.
Так же существует решение с помощью динамического программирования.
Асимптотика обоих решений O(n^2).
Буду очень рад, если кто то напишет решение с лучшей асимптотикой.

256B - Mr. Bender and Square

Solution — binary search for answer. Next we have to calculate the area of a truncated square set at 45 degrees. This can be done as follows: Calculate its total area. Subtract area that cuts off the top line. Similarly, for the lower, left and right line. Add parts that are cutted by corners. You can write a function that finds the length of the truncation desired area, for that would not write a lot of code.

256C - Furlo and Rublo and Game

Note that after the first move any pile turns into a pile no larger than 1000000. We assume Grundy function for numbers less than 1 million. Grundy function is very small, you can start on the partial sums for each type of function that would quickly tell what function is in the interval, and which are not present. Knowing the answer is not difficult to find small response for all piles.

256D - Liars and Serge

If person say number x, and at all x was said by x persons, then we cannot tell anything about fixed person.

Now we understand which sequence are good for us. We will calculate their count wuth dynamic programming dp[n][m][k], n — which persons answers we set to the sequence right now, m — how mant persons gived theis answers, k — how many persons from them are liers.
Transfer:
dp[n][m][k]*cnk[N-m][n] -> dp[n+1][m+n][k]
dp[n][m][k]*cnk[N-m][p] -> dp[n+1][m+p][k+p] p = 1 .. N, p != n.
We assume, that N — total number of the persons. This solution get TLE, becouse complexity if O(N^4). We need to use precalc. It will not be so big, as N is power of 2.

256E - Lucky Arrays

Solution is — interval tree. We will save dynamic programming f[i,j] in each vertex, this dp means: in how many ways we can change all 0 to some numbers on interval, such that it will be valid and first element will be i and last will be j.

With normal implementation its easy to pass system tests.