400A — Inna and Choose Options

Not difficult task. Let's iterate param a. If 12 % a != 0, continue. Calculate b = 12 / a. Let's iterate column (from 1 to b) and for each it's cell (i, j) check, if it contains X or not. Cell (i, j) — is ((i–1) * a + j) -th element of string.

400B — Inna and New Matrix of Candies

In the final version of statement we must choose all lines we haven't finish already. If it is a string where we have S...G — answer  - 1.

Otherwise, the answer is the number of distinct distances, as one step kills all distances of the minimal length.

400C — Inna and Huge Candy Matrix

Let's note that the number of 90 clockwise make sence only by modulo 4. Horizontal — by modulo 2, and 90 counterclockwise — by modulo 4, and 1 such rotation is 3 clockwise rotations.

90 clockwise: newi = j; newj = n–i + 1 don't forget to swap(n, m).

Horizontal: newj = m–j + 1

400D — Dima and Bacteria

If the distribution is correct, after deleting all ribs with cost more than 0 graph will transform to components of corrects size. Also, the nodes are numereted so we should turn dfs for the first node of each type and be sure that we receive exact all nodes of this type and no ohter.

Now simple floyd warshall, and put in each cell of adjacent matrix of components the minimal weight between all ribs from 1 component to another.

400E — Inna and Binary Logic

Let's solve this for each bit separately. Fix some bit. Let's put 1 if the number contains bit and 0 otherwise. Now we receive the sequence, for example 11100111101.

Now let's look on sequence of 1 without 0, for this sequence current bit will be added to the sum on the first stage (with all numbers single) on the second stage (with all neighbouring pairs) on the third stage and so on, the number of appiarence for sequence of neighbouring 1 is a formula which depends on the length of sequence only.

The last is to learn how to modificate. For each bit let's save the set of sequence of 1. When the bit is deleted, one sequence is sepereted on two, or decreases its length by 1. When the bit is added, new sequence of length 1 appears, or some sequence increases its lentgh by 1 or two sequence transform to 1 biger sequence.

Hi! Soon Codeforces Round #234 (Div. 2) will take place, i am the author, Dmytro Berezin :)

Thanks to Gerald Agapov (Gerald) for the help in round preparation, Maria Belova (Delinur) for tasks translations, Mike Mirzayanov (MikeMirzayanov) for perfect system, and Sergii Nagin (Sereja) for his agreement (to share his evening with me) to help in testing.

Distribution will be announced as soon as found :) Standard :)

Good luck!

374A — Inna and the pink pony

Lets find a solution for shifting a candy from the position (x₁, y₁) into position (x₂, y₂). On each step we shift (increase or decrease) x₁ by a and y₁ by b.

It is not difficult to understand that if |x₂ - x₁| is not divisible by a and |y₂ - y₁| is divisible by b answer doesn't exist.

We should also note that |x₂ - x₁| / a and |y₂ - y₁| / b Should be both even or odd as shifting is performed at a time for both values.

We should also look up for a corner case when step dropes us out from the board.

Now we can determine the way from (x₁, y₁) to (x₂, y₂) as max(|x₁ - x₂| / a, |y₁ - y₂| / b).

Lets calculate it for all corners and choose minimum or determine that the answer doesn't exist.

374B — Инна и девять

We can divide the task into subtasks because if two adjacent digits have sum none-9 the number transformation doesn't depends on other side relatively to the position between this two digits. It means we should divide our task into subtasks of kind: x or xyxyxyx...xyxy where x + y = 9. We should multiply all such answers because we are looking for the whole number of variants.

For x answer is 1. What should we do for xyxyxy? Let its length is s. Then if s is even we simply receive s / 2 nines. If s is odd one digit (any of them) will stay. Thus each sequence xyxyxyxyx...xyxyxy with odd length s increases the answer IN s times.

374C — Inna and Dima

Our task is tranformed to the task of finding cycle or maximal way, but lets solve it without any graphs.

Lets run dfs from each digit D, memorizing all already calculated tasks. If we come into the cell we have already been (in one of the previous D) than we should simply add the maximal way length to our current length. Way length is increased not in each cell but only when we come into A. If we come into the cell we have already been on current step (in our dfs running) this is the cycle and we should stop the algorithm. Don't forget to change the color of cell after droping from recursiong because you will receive "false cycle". Simply set the colour to current when come into the cell but decrease it before end of recursion for this cell.

374D — Inna and sequence

Lets note that not more than n numbers, thus it will be not more than n dropings. We will run this process using data structure Segment Tree (you can use another structures). Lets calculate the number of numbers in current segment. When the number is added we should simply go down from the root to the leaf and increase value for each segment on the way by 1. Deletetion — vice versa. If there is enough numbers in the left subtree we should go into the right one, othervise — into the left one. Don't forget to shift the a_i position by decreasing on i as all numbers are droped immidiately. And don't forget to break the cycle as soon as you reach first a_i such that there is no number to be droped out from it.

374E — Inna and babies

We will make the binary search to find the answer. For each time let's generate our segments and rotate them to transform them into horizontal and verticle. We can use transformation (x, y) to (x + y, x - y). Don't forget to make the union of all segments which were at the one diagonal and have an intersection. You should sort all segments of one type and iterate through them updating the size of the segment. Now we should only determine if there is at least one rectangle. For example we can iterate each verticle segment updating the set of all horizontal which begin not later than our verticle. For each verticle (the left one) we should iterate the right verticle and now calculate the set of horizontal which not only begin not later than the left verticle but also don't end earlier than the right one. Now we should only determine is ther is two or more horizontal segments from the set which satisfy also y-conditions for current vertical.

Hi! Soon Codeforces Round #220 (Div. 2) will take place, i am the author, Dmytro Berezin. This is my third round and Sereja still hopes, that this is the last :)

Everything changed since last round. Dima and Inna have thought about their behavior and asked Sereja to excuse them. They are good friends now. You should make the family happiness even stronger!

Thanks to Gerald Agapov (Gerald) for the help in round preparation, Maria Belova (Delinur) for tasks translations, Mike Mirzayanov (MikeMirzayanov) for perfect system, and Sergii Nagin (Sereja) for his agreement (not to post here another photo) to help in testing.

Points distribution will be. 500-1000-1500-2000-2500. Here we go :)

366A — Dima and Guards

The solution doesn't exist only if the mimimal way to bribe is grater than n. Otherwise we can increase the gift price to make price1 + price2 = n.

Let's find the miminal way to bribe. We should buy that gift for old lady which costs less. It means, if we have 2 guards with params a b c d, then minimum bribe price will be min(a, b) + min(c, d). Let's choose the guard with the minimal bribe price. If the minimal bribe price is greater than n, answer -1. Otherwise, the possible answer is, for example: Guard number, min(a, b), n–min(a, b).

366B — Dima and To-do List

Dima can make k–1 tasks, so Inna always tells him off for each k-th taks, beginning from the chosen place. So for the numbers with same modulo by k the answer will be the same. We should find the answer with minimal first task number so it is eniugh to calculate the sums of “tellings of” for tasks 0, 1... k–1. We can do it in such way: Determine the array int sum[k]. And put the number into appropriate bucket while reading:

sum[I mod k] +  = a[i]. Now we should simply find first i with minimal sum[i].

Complexity: O(N).

366C — Dima and Salad

Let's calculate dinamic: d[num][balance] where num – last looked fruit, balance — difference between sum of colories and sum of tastes. Let's multiply each b by k. The answer will be d[n][0].

d[num][balance] = maximal possible sum of tastes under conditions.

Step: from d[num][balance] we can relax answers:

d[num + 1][balance] = max(d[num + 1][balance], d[num][balance]) – if we don't choose a fruit

d[num + 1][balance + a[i] - b[i]·k] = max(d[num + 1][balance + a[i] - b[i]·k], d[num][balance] + a[i]) – if we choose a fruit.

Balance can be negative, so in programming languages which don't support negative indexation, indexes should be shifted by the biggest negative number for balance. If we determine the balance as sum(b·k) - sum(a) it will be the sum of all tastes.

366D — Dima and Trap Graph

The answer for some path is a range under which we can go all the way, and this range is the intersection of all the ranges on the path. We can conclude it because the number is valid for path if it is valid for all ranges in the path. We will iterate all ribs. Let the left board of range on a rib is the left board of our intersection. It means we can't use ribs whith left board greater than ours. Lets iterate all right boards, determining the answer as the range from fixed left board to the chosen right. This answer exists if we have any path from the first node to the last. Let's check if the graph is connected if we leave only ribs with left board not greater than our and right board not less than our. If the graph is connected — let's update the answer. Right board can be found by binary search so the complexity is O(M²·logM).

366E — Dima and Magic Guitar

There are many solutions for this task. I will describe my, you can deal with other by looking participants code. To find the answer we should calculate maxDis[k][k], where maxDis[i][j] – maximal complexity from note i to note j.

Now we should only iterate the song updating answer for each pair of adjacent notes. Let's think how we can calculate the matrix.

For each place (x₁, y₁) on the guitar let's iterate pairs (x₂, y₂) with y₂ ≤ y₁.

If (x₂ ≤ x₁) distance will be x₁–x₂ + y₁–y₂. So we should find minimal x₂ + y₂ in submatrix from (0, 0) to (x, y).

If (x₂ ≥ x₁) distance will be x₂–x₁ + y₁–y₂. So we should find maximal x₂–y₂ in submatrix from (n–1, 0) до (x, y).

We will calculate this values for each note. We need too much memory so we should memorize only one previous row for each note. For each place we will update dinamics for both variants according to already calculated and for our own note (which is in this cell) we will also compare (i + j) or (i–j) with current value in the cell.

Complexity O(N·M·K)

Good day! The event named Codeforces Round #214 (Div. 2) will take place soon. My name is Dmytro Berezin and i am the author. This is my second round and Sereja hopes that this is the last one :)

Private life — is such thing, which can't contains too much happiness, so you should help Dima and Inna again. In addition, Sereja is not a negative character! He is rather some kind of circumstances you should fight with... Sometimes.

I want to thank Gerald Agapov (Gerald) for his help in round preparation, Maria Belova (Delinur) for statements translations, and Sergii Nagin (Sereja) for the fact he kindly (leaves the room sometimes) agreed to help in testing.

Sergii sends greetings and strongly recomend to read ALL tasks.

Point distributions will be announced. Honestly. And the distribution is: 500-1000-1500-2000-2500

Thank you for your time, have a nice round!

Hi everybody!

When you've seen my nickname you probably thought: "Finally! At least this round is not made by Sereja! And you are right! I, Dmytro Berezin(Berezin) give this round... and my neighbour Sergii Nagin(Sereja)

The action will take place in Friday, 25th october, 19:30.

Thanks to Gerald Agapov(Gerald) and Maria Belova(Delinur) for help in preperation and translation of problems respectively.

Thanks to Yaroslav Tverdokhlib(KADR) for help in testing.

You have to help Dima equip his personal life :)

The point values for this cause is 500 1000 1500 2000 3000.

Sergii strongly recommends you to read all the tasks.

I highly recommend you also to try to solve them.

Thank you for your attention, and have a successful round!

Tutorial: http://codeforces.net/blog/entry/9334