The contests starts at 12.00 MSK.

There are some links where you can get some information about the conduct of the contest.

• official site, see results and video coverage here
• alternative standings
• Petr’s Mitrichev blog

Have fun watching the finals!

The official part of our visit takes a lot of time, which makes this entry greately resemble a short report about past events.

On the second day of staying in the Polish capital we went for a walk in the city centre. It was cold, windy and a little rainy, so those of us who hadn’t taken any warm clothes to Poland, had to buy hats, scarves and jumpers with Polish national symbols in souvenir shops. We were very impressed by the Old Town (Stare Miasto) that was destroyed in the World War II but then rebuilt. Actually, that’s what comes to my mind when I imagine a historical centre of a European city: narrow sett-paved streats, clock towers with high spines, tiled roofs…

This entry begins a small account of the journey Saratov State University delegation has left for the World Finals of the ACM ICPC 2012. The destination is Warsaw, where the World Finals take place this year. The delegation members are:

• Maxim Ivanov (e-maxx), Artem Rakhov (RAD), Nickolay Kuznetsov (NALP) — the Saratov SU 2 team;
• Michail Mirzayanov, the coach, with his wife Katherine and his daughter Tanya;
• Antonina Fedorova and Tatiana Semenova, our administrators;
• and finally, me (Nerevar), as the second coach.

That is the team’s second and last journey to the finals (last year they brought silver medals from Orlando). And for me this is the first journey to the Finals not as a participant (I participated in 2009 and 2010, and was a success too).

Несмотря на то, что участники уже опубликовали собственный разбор, предлагаем вам авторский разбор контеста.

The X regional school team programming contest will be held in Saratov on Tuesday, 18 of October. The jury has prepared a set of interesting problems. We came to conclusion that it will be unfair if these tasks are available only for the onsite school teams. That's why we decided to organize a contest with these tasks on Codeforces.

The statements will be available as PDF via links:

• russian text
• english text

It will be file input-output in these problems. Read statements carefully.

Let me say the customary phrase "The series of school online Olympiads have ended!"

The organization of all the Olympiads was supported by Yandex and ABBYY companies. Overall 6 competitions took place, three team Olympiads and three individual ones. It is now high time we looked at the results and found the Olympiad winners. The two nominations (team contests and individual contests) were ratified individually – in each of them the results of the participants’ best two of three performances. Here are the links to the total results in each nomination:

• team contests’ results
• individual contests’ results

Overall about 750 participants from all over the world had been registered during the series. Of course, the majority of them were Russian participants. As we can see, about 180 teams took part in the team contests and more than 400 school students took part in the individual contests.

Task B. T-shirts from sponsor.

Enumerate sizes of t-shirts by integers from 0 to 4. For each size we store the number of t-shirts of this size left. To process each participant, we need to determine the number of his preferable size. Then we iterate over all possible sizes and choose the most suitable one (with the nearest number) among the sizes with non-zero number of t-shirts left.

Task D. Parking.

Lets keep a set of cars which are currently parked. In this problem it is not essential how to keep this set. For each car, store its length and position. To process a request of type 2, we need to find the car which should leave the parking and remove it from the set. To do this, we should enumerate the cars and get the car number by the number of request. Now consider a request of type 1. As the drives tries to park his car as close to the beginning of the parking slot as possible, we can reduce the set of reasonable positions for parking: include into this set the beginning of the parking and all positions that are exactly b meters after the front of some car. For every position in this set we should determine if it is possible to park car in it. Then we choose the closest to the beginning position among admissible ones.

Task E. Comb.

Denote the input matrix by a. Compute the partial sums in each row first: . All these sums can be easily computed in O(nm). Then solve the task using dynamic programming. By d_i, j denote the maximum sum of numbers that we can take from first i rows, taking exactly j numbers in row i and not violating the "comb" condition. Starting values are obvious d_1, j = s_1, j. Transitions for i > 1 looks like this:

1) If i is even, .

2) If i is odd,  .

Straightforward computing of values d_i, j by these formulas has complexity O(nm²), which is not suitable. Use the following fact: if we compute values d_i, j in order of decreasing j in case of even i and in order of increasing j in case of odd i, the maximum values of  d_{i - 1, k} from the previous row can be computed in O(1), using value for previous j, i.e. without making a cycle for computation. This solution has complexity O(nm) and passes all tests.

Greetings to everybody.

I would like to invite you to take part in the next Codeforces competition, which will be held on 5th of December at 11:00 MSK. This competition will be a part of WCS olympiads (click here for details) and usual Codeforces round at the same time.

This competition, as all previous WCS contests, is sponsored by Yandex and ABBYY.

The official rules of the competition are ACM-ICPC rules. The duration of the competition is 3 hours.

Those who don't participate in selection to WCS will be displayed as "out of competition" in the result table. But everybody will get rating for this competition according to the merged result table.

This time the authors of the problems are Natalia Bondarenko and I. Thanks to Edvard Davtyan for his help in preparing the contest and to Maria Belova for translating problem statements.

Don't forget to register in order to take part in the competition. Good luck at the contest!

• Russian version
• English version

UPD: The results of the contest. Congratulations to tourist, the winner of WCS contest, and to Petr, the winner of beta round #43.

UPD: Links to problem tutorials: A,C,F,G and B,D,E.

Problem I. Toys.

In this problem we need to output all partitions of the given set into subsets in the order which is very similar to the Gray code. Lets denote each partition by a restricted growth string. For a restricted growth string a₁a₂a_n holds that a₁ = 0 and a_j + 1 ≤ 1 + max(a₁, ..., a_j) for 1 ≤ j < n. Every partition can be encoded with such string using the following idea: a_i = a_j if and only if elements i and j belong to the same subset in the partition. For example, string representation of the partition {1,3},{2},{4} is 0102.

Now we will learn how to generate all restricted growth strings by making a change in exactly one position in the current string to get the next string. It is obvious that in terms of partitions it is what we are asked for in the problem. Rather easy way to build such list of strings was invented by Gideon Ehrlich. Imagine that we have the required list s₁, s₂, ..., s_k for the length n - 1, We will obtain a list for the length n from it. Lets s_i = a₁a₂... a_n - 1, and m = 1 + max(a₁, ..., a_n - 1). Then, if i is odd, we will obtain strings of the length n by appending digits 0, m, m - 1, ..., 1 to s_i, otherwise we will append digits in order 1, ..., m - 1, m, 0. Thus, starting from the list 0 for n = 1 we will consequently get lists 00, 01 for n = 2 and 000, 001, 011, 012, 010 for n = 3. Ehrlich scheme is decribed in Knuth's "The art of programming", volume 4, fascicle 3, pages 83-84.

Problem G. Shooting Gallery.

Lets solve slightly different problem: for every target we will determine the shoot that hits it. Sort the targets in increasing order of their z-coordinate and process them in that order. Each target is processed as follows. Consider all shoots that potentially can hit it. It is obvious that all such shoots belong to the rectangle, corresponding to the target. From these shoots, the earliest shoot will hit the target. We should find this shoot and remove it from the set of shoots, and then turn to the next target. It's easy to see that the following condition will be held: before we process a target, all shoots that were going to hit it but faced other targer, were already removed from the set of shoots.

Now we need to implement the algorithm efficiently. We will store the shoots in some data structure. This structure should be able to answer two types of queries:

In my solution I used two-dimensional index tree to manage these queries. I won't describe what the two-dimensional index tree is. I just want to make several remarks. First, the removing operation is not as easy to implement in a two-dimensional index tree as it mays seem. But we are lucky that we have no additions, just deletions! Time complexity of the model solution is O((N + M)log²N.

Problem F. BerPaint.

Imagine that all segments were drawn. We will refer to these segments as to initial segments. Lets divide the rectangle of drawing into the set of regions and segments such that there are no points of the initial segments strictly inside any region, and new segments separate the regions. Note that new set of segments can contain not only the parts of the initial segments, but also some dummy segments. Initially the color of all regions is white, while the color of each segment can be black of white (dummy segments are white). Please note that in such a partition the border of the region is not consider to belong to it. Lets build a graph where each vertice corresponds either to a region or to a segment, and add edges according to the following rules:

It is clear that every region that can be filled corresponds to some connected component of this graph. That gives us a solution. We will store a color for each vertice. When processing a filling operation, we search for all such vertices that the objects that correspond to these vertices contain the chosen point. For region, the point should lie strictly inside the region. For the dummy segment, the point should lie on it but should not coincide with it end-points. And for the non-dummy segment, the point should just lie on it. From each of the found vertices, we make a DFS or BFS which finds all vertices that are reachable from the statring vertice and have the same color, and paints them with new color. After all operations, we need to find sum of areas for such colors, that there are at least one vertice with this color.

The main difficulty in the problem is to divide the rectangle into regions and segments. In my solution it is done using vertical decomposition. First, divide the rectangle into vertical stripes such that inner area of any stripe doesn't contain neiher end-points of the initial segments nor points of their intersections. Then each of these stripes is divided into trapezoid by initial segments, intersecting the stripe. Then add necessary dummy segments to separate the regions and build the graph. I think that there may be some easier ways to construct such graph.

Greetings to everybody.

Today is an unusual day on Codeforces: two contests a day with quite small gap between them. The reason is that today the IX Regional team school programming contest is held in Saratov, and it was decided to use the tasks from it for Codeforces rounds.

That's why there are many authors of today's tasks. I would like to thank the whole jury of the school contest for their excellent job. The following people are on the jury: Artem Rakhov, Nickolay Kuznetsov, Natalia Bondarenko, Gerald Agapov, Polina Bondarenko, Ivan Fefer, Edvard Davtyan, Igor Kudryashov, Pavel Kholkin and me. I believe that you know all these people as Codeforces problemsetters.

Let me draw your attention to the fact that today all problems have file IO. But generators for the hacks should output to stdout as usual.

Special thanks to Maria Belova and Julia Satushina for translating problem statements into English.

Good luck at the contests!

UPD: Results of the 35th round. We congratulate the winner, Naginchik, on his impressive debut!

UPD: Results of the 36th round.

Links to problem tutorials: A, B, C, D, E.

Dear girls and women! Happy Women's day! On behalf of the Codeforces team I would like to wish you all the best!

May love and care surround you! May you always catch the admiring gazes of men! Stay beautiful and clever and keep making us happy!