I am happy to present you author's ideas of solutions. Editorial of the first five problem is authored by — HolkinPV and gridnevvvit, editorial for the last two problems is written by me.

479A - Expression

In this task you have to consider several cases and choose the best one:

int ans = a + b + c;
ans = max(ans, (a + b) * c);
	ans = max(ans, a * (b + c));
	ans = max(ans, a * b * c);

	cout << ans << endl;

479B - Towers

The task is solved greedily. In each iteration, move the cube from the tallest tower to the shortest one. To do this, each time find the position of minimum and maximum in the array of heights (in linear time).

479C - Exams, 480A - Exams

The solution is again greedy. Sort the exams by increasing a_i, breaking ties by increasing b_i. Let’s consider exams in this order and try to take the exams as early as possible. Take the first exams in this order on the early day (b₁). Move to the second exam. If we can take it on the day b₂ (i.e. b₁ ≤ b₂), do it. Otherwise, take the second exam on the day a₂. Continue the process, keeping the day of the latest exam.

std::sort(a, a + n);  // а is the array of pairs, where first element is the date in schedule, and second is the early date of passing
int best = -1;
for(int i = 0; i < n; i++) {
if (best <= a[i].second) {
		best = a[i].second;
	} else {
	 	best = a[i].first;
	}
}	

479D - Long Jumps, 480B - Long Jumps

It is easy to see that the answer is always 0, 1 or 2. If we can already measure both x and y, output 0. Then try to measure both x and y by adding one more mark. If it was not successful, print two marks: one at x, other at y.

So, how to check if the answer is 1? Consider all existing marks. Let some mark be at r. Try to add the new mark in each of the following positions: r - x, r + x, r - y, r + y. If it become possible to measure both x and y, you have found the answer. It is easy to check this: if, for example, we are trying to add the mark at r + x, we just check if there is a mark at r + x + y or r + x - y (by a binary search, since the marks are sorted). Make sure that the adde marks are in [0, L].

479E - Riding in a Lift, 480C - Riding in a Lift

The task is solved by a dynamic programming. State is a pair (i, j), where i is the number of trips made, and j is the current floor. Initial state is (0, a), final states are (k, v), where v is any floor (except b).

It is easy to see the transitions: to calculate dp(i, j), let’s see what can be the previous floor. It turns out that all possible previous floors form a contiguous segment (with a hole at position j, because we can’t visit the same floor twice in a row). So, dp(i, j) is almost equal to the sum of values dp(i - 1, t), where t belongs to some segment [l, r] (the values of l and r can be easily derived from the conditions from the problem statement). Using pretty standard technique called “partial sums” we can compute dp(i, j) in O(1), so overall complexity is O(NK).

Jury solution: 8322623

480D - Parcels

Let’s make two observations.

First, consider the parcels as time segments [in_i, out_i]. It is true that if at some moment of time both parcel i and parcel j are on the platform, and i is higher than j, then .

Second, let’s imagine that there are some parcels on the platform. It turns out that it is enough to know just a single number to be able to decide whether we can put another parcel on top of them. Let’s denote this value as “residual strength”. For a parcel (or a platform itself) the residual strength is it’s strength minus the total weight of parcels on top of it. For a set of parcels, the residual strength is the minimum of individual residual strengths. So, we can put another parcel on top if it’s weight does not exceed the residual strength.

These observations lead us to a dynamic programming solution. Let the top parcel at the given moment has number i, and the residual strength is rs. Make this pair (i, rs) the state of DP, because it is exactly the original problem, where the platform strength is rs and there are only parcels j with . In d(i, rs) we will store the answer to this instance of the original problem.

Which transitions are there? We can choose a set of parcels i(1), i(2), ... i(k) such that

• out_i(j) ≤ in_i(j + 1), i.e. segments do not intersect (but can touch) and are sorted;
• the weight of each of these parcels does not exceed rs.

This choice corresponds to the following sequence of actions: first put parcel i(1) on the top of i. This gets us to the state i(1), min(rs - w_i(1), s_i(1)), so we add up the answer for this state and the cost of i(1). Then we take away all parcels, including i(1), and put the parcel i(2) on top of i, and so on.

As the number of states in DP is O(NS), all transitions should take linear time. It can be achieved by making an inner helper DP. This give a solution in O(N²S). Note that for simplicity the platform can be considered as a parcel too.

480E - Parking Lot

Let’s denote the car arrivals as events.

Consider the following solution (it will help to understand the author’s idea): let’s consider all empty square in the table. There a too many of them, but imagine that we can afford to loop through all of them. If we fix a square, we can find out when it is no longer empty: find the first event that belongs to this square. Let this event has number x, and the size of the square is k. Now we can update the answers for all events with numbers less than x with a value of k.

The model solution use the idea of Divide and Conquer. Let’s make a recursive routine that takes a rectangular sub-table, bounded with r₁, r₂, c₁, c₂ (r₁ ≤ r₂, c₁ ≤ c₂), and a list of events that happen inside this sub-table. The purpose of the routine is to consider how maximal empty squares in this sub-table change in time, and to update the answers for some of the events.

Let’s assume that c₂ - c₁ ≤ r₂ - r₁ (the opposite case is symmetric). Take the middle row r = (r₁ + r₂) / 2. Virtually split all the squares inside the sub-table into those which lie above r, those which lie below r, and those which intersect r. For the first two parts, make two recursive calls, splitting the list of events as well. Now focus on the squares that intersect the row r.

Using initial table, for each cell (r, c) we can precompute the distance to the nearest taken cell in all four directions (or the distance to the border, if there is no such cell): up(r, c), down(r, c), left(r, c) и right(r, c). Using this values, build two histograms for the row r: the first is an array of values up(r, c), where c₁ ≤ c ≤ c₂; the second is an array of values down(r, c), where c₁ ≤ c ≤ c₂. I say histograms here, because these arrays actually can be viewed as heights of empty columns, pointing from the row r upwards and downwards. Lets call the first histogram “upper”, the second one — “lower”. Now consider all events inside the sub-table in the order they happen. Each event changes a single value in a histogram. If after some event x the maximum empty square found in the histograms has size k, and the next event has number y, we can update answers for all events with numbers x, x + 1, ..., y - 1 with the value of k.

It remains to learn to find a maximum square in two histograms. It can be done by a two-pointer approach. Set both pointers to the beginning. Move the second pointer until there is such square in histograms: there is a square with side length k if (minimum on the interval in the upper histogram) + (minimum on the interval in the upper histogram) — 1 >= k. When the second pointer can not be moved any more, update the answer and move the first pointer. To find the minimum in O(1), author’s solution creates a queue with minimum in O(1) support. That is, the maximum square can be found in linear time.

Let’s try to estimate the running time. Each call of the routine (omitting inner calls) costs O(len·q), where len is the shortest side of the sub-table, and q is the number of events in it. If we draw a recursion tree, we will see that each second call len decreases twice. The total cost of all operations in a single level of a recursion tree is O(NK), where K is the total number of events. As long as we have O(logN), overall complexity is O(NKlogN).

Greetings to the Codeforces community!

Yet another Div1+Div2 round will take place this Sunday, 19th of October at 13:00 MSK.

The round is based on the problems of the regional stage of All-Russia team school competition, which will take place at the same time in Saratov. We are aware about the overlapping with Opencup, but we have no option to shift the round, because we are bounded to the local event.

The problems were prepared by HolkinPV, gridnevvvit, danilka.pro, Avalanche, IlyaLos, Fefer_Ivan and me.

Scoring: 500-1000-1500-2000-2500 (both divisions).

UPD: Editorial is published.

Greetings to the Codeforces community!

Today in Saratov there is a second day of the local school competition, so we again introduce you a round based on school problemset. Round is for participants from Division II. Members of the first division can participate out of competition, as usual.

Round starts on 8-th of December at 09:00 UTC

Problems were prepared by employees and students of Saratov State U, including MikeMirzayanov, Fefer_Ivan, NALP, HolkinPV and me.

Scoring: 500-1000-1500-2000-2500.

UPD: Congratulations to the winners:

1. asalwaysdontbeahero
2. VKRNVO5
3. chnluyi
4. pkwv
5. Xe4NIK

UPD: tutorial.

370A - Rook, Bishop and King

There are two approaches to this task. The first is use BFS to find the shortest path three times. The second is to notice that:

• A rook can reach the destination in one or two moves. If the starting and the destination fields are in the same row or column, one move is enough.
• A bishop can reach only fields that are colored the same as the starting cell, and can do this in at most two moves: if the starting and the destination fields are on the same diagonal, one move is enough. To find this out, check that r₁ - c₁ = r₂ - c₂ OR r₁ + c₁ = r₂ + c₂.
• A king should make max(|r₁ - r₂|, |c₁ - c₂|) moves.

    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    if (r1 == r2 || c1 == c2) cout << 1; else cout << 2;
    cout << " ";
    if ((r1 + c1) % 2 != (r2 + c2) % 2) cout << 0; else {
        if (r1 + c1 == r2 + c2 || r1 - c1 == r2 - c2) cout << 1; else cout << 2;
    }
    cout << " ";
    cout << max(abs(r1 - r2), abs(c1 - c2)) << endl;

370B - Berland Bingo

It is good idea to think about cards as set of numbers. It is easy to see that card a can’t be finished before b if b is subset of a. So all you need is to find such cards (sets) which do not have other card (other set) as subset.

Since there are at most 1000 cards, you may iterate through all pairs and check that one card contains other in naive way like:

bool contains(vector<int> a, vector<int> b) // b in a?
{
    forn(i, b.size())
    {
        bool in = false;
        forn(j, a.size())
            if (a[j] == b[i])
                in = true;
        if (!in)
            return false;
    }

    return true;
}

370C - Mittens

Let’s show that if the most frequent color appears not more than times, than all children can get mittens of distinct colors. One way to construct such solution is to sort all left mittens in the order of decreasing frequency of their colors: for the input 1 2 1 2 3 1 3 3 1 we get 1 1 1 1 3 3 3 2 2. To obtain the sequence of right mittens, rotate the sequence of left mittens to the left by the maximum color frequency (in the example it is 4, so we get the sequence 3 3 3 2 2 1 1 1 1). Then just match the sequences (1 — 3, 1 — 3, 1 — 3, 1 — 2, 3 — 2, 3 — 1, 3 — 1, 2 — 1, 2 — 1). It can be easily shown that all pairs consist of distinct colors.

OK, but what to do if there is a dominating color that appears more than half times? Use exactly the same algorithm! It will maximize the number of pairs of distinct colors.

370D - Broken Monitor

There are a lot of correct approaches to solve the problem. But there are much more incorrect :)

One way to solve the problem is following. It is easy to see that in possible answer there are two opposite sides each containing w. In opposite case frame can be shrinked. So the size of frame is dx or dy, where dx = maxx - minx + 1 and dy = maxy - miny + 1 (minx, maxx, miny, maxy are coordinates of left/right/top/bottom ws). Obviously, you should choose max(dx, dy) as a size.

Now we know the size of the required frame. How to find it’s leftmost-topmost corner?

The set of possible xs is: minx, maxx - size + 1 and 0. Indeed, you may move frame to the left until it will abuts to w by left size/right size of abuts to the left side of monitor.

Similarly, the set of possible ys as y-coordinate of leftmost-topmost corner: miny, maxy - size + 1, 0.

Now the solution looks like:

find minx, maxx, miny, maxy
dx = maxx-minx+1, dy=maxy-miny+1
size = max(dx, dy)
foreach x in {minx, maxx-size+1, 0}
    foreach y in {miny, maxy-size+1, 0}
        if frame_correct(x, y, size)
            print answer
            exit algorithm

All you need is to write frame_correct. You may iterate through frame and check that all cells inside monitor and calculate the number of ws on it. If all the cells are inside and calculated number equals to total number of w, then return true.

This solution works in O(nm).

370E - Summer Reading

For each book number that is in the sequence, find the leftmost and the rightmost position of this number. In other words, for each such book number we find a segment of positions that should consist of this number. If for some pair of numbers there segments intersect, it is impossible to construct the answer. The same thing happens if some segment has length more than 5. It is reasonable to separately handle the case when all given numbers are zeroes. In this case, fill in the numbers greedily, spending 2 days on each book (probably, except the last one).

So, we have some blocks of numbers and gaps between them. Lets do the following DP: each state of DP is described by two values (i, j): i means the number of block (lets enumerate them consecutively), j means how far to the right will this block eventually extend (if there is a gap after this block, it is possible that we fill some prefix of this gap with the same book number that is in the block). It is clear that j - i will not exceed 5, so we actually can describe the state by values (i, j - i), which may sound more convenient. So, the number of states is linear. Lets say that D(i, j) is true if it it possible to correctly fill all the gaps that come before the i-th block, under condition that the i-th block extends to the position j, and D(i, j) is false otherwise. To calculate the value of D(i, j), lets try to extend the i-th block to the left in all (not so many) possible ways (to replace some number of consecutive zeroes that are in the gap just before the i-th block). Then, try to fix where the previous block can actually end (fix the state D(i - 1, k), where D(i - 1, k) is true, of course). To make a transition in DP, we should check whether it possible or not to fill the rest of the gap between the (i - 1)-th block and the i-th block. Lets say that (i - 1)-th block consists of number x, the i-th block consists of number y, and there are f still unfilled positions in the gap. Than the gap can be correctly filled if and only if 2·(y - x - 1) ≤ f ≤ 5·(y - x - 1).

If you understand this DP, it won’t be difficult for you to find out how to construct the answer from it.

363A - Soroban

Not so much to say about this problem. You need to extract the digits of the given number (read it as string or repeteadly divide by 10 and take the remainders). Then carefully do the mapping of digits to its' representation.

363B - Fence

Another easy problem. We need to calculate the sum of every consequtive segment of k planks. One way to do this is to calculate partial prefix sums: . Then the sum of heights of the planks i, i + 1, ..., i + k - 1 is s_{i + k - 1} - s_i - 1. The other approach is to calculate the sum of the first k planks: h₁ + h₂ + ... + h_k. By subtracting h₁ and adding h_k + 1 we get sum of k planks starting from the second plank. Then, by subtracting h₂ and adding h_k + 2 we get sum of k planks starting from the third plank, and so on.

363C - Fixing Typos

The general idea of the solution is the following: while there are three consequtive equal characters, remove any one of them. After that we can only have typos of the second type. So, if we have one couple of equal characters immediately after another couple of equal characters (xxyy), we need to decide which character to remove, x or y? Let's find the leftmost typo of the second type in the string. It is easy to see that we can always remove the character from the second couple.

All these can be done in a single pass. Go through the characters of the given string and build the resulting string ans. Let's denote the current character as ch. If ch is equal to the last two characters of ans, skip ch. If ch is equal to the last character of ans and ans[length(ans) - 2] = ans[length(ans) - 3] (assume that ans is 1-indexed), skip ch. Otherwise, append ch to ans.

363D - Renting Bikes

Let's do a binary search over the number of boys that can rent a bike. So let's say that we want to check whether it possible for k boys to rent bikes. If some k boys can rent a bike, then the k "richest" boys (with the most amount of personal money) also can do that. It is easy to see that if they can rent bikes, they can rent k cheapest bikes (if we first sort the bikes in increasing order of price, it will be just the first k bikes).

So, take k richest boys and try to match them with k cheapest bikes, spending as much common budget as possible. The following algorithm works (try to understand and prove it before asking questions): take the boy with least number of money (of course, among the considered k richest) and try to give him the cheapest bike. If the boy has ehough personal money to rent this bike, use his money to do this. Otherwise, use all his money and take some money from the common budget. Continue this process with the second cheapest bike and the second "poorest among the richest" boys. This process can end in two ways: we will either run out of budget and fail to rent k bikes, or we will successfully rent these bikes.

363E - Two Circles

Correct solution will be published later.

Greetings to the Codeforces community!

I'm glad to announce that we again decided to introduce a round based on one of the programming olympiads for schoolchidren in Saratov. This time it is a round for participants from Division II. Round will start at unusual time for Codeforces: 12:00 MSK.

The problems were prepared by MikeMirzayanov and me, while Fefer_Ivan and Gerald helped us with writing alternative solutions.

Members of the first division can participate out of competition, as usual.

Scoring distribution is standard: 500-1000-1500-2000-2500.

UPD: tutorial can be found here.

UPD 2: The model solution for problem E (unfortunately, there were only one model solution) was incorrect. But, the answers for all pretests were correct. After the round we fixed the solution. All submits for problem E were rejudged.

UPD 3: Results are final, ratings are updated.

357A - Group of Students

In this problem you need to iterate over all possible values of passing rate from 1 to 100 and for each value calculate the sizes of two groups.

357B - Flag Day

Let's process the dances in the given order and determine the colors of dancers' clothes. If there are no dancer from some previous dance, we can give the dances different colors arbitrarily. And if there is such dancer, we already know the color of his clothes. So, we arbitrarily distribute the other two colors between the remaning two dancers.

356A - Knight Tournament

Let's the current fight (l, r, x) consists of K knights fighting. Then all we have to do is to find all these knights in time O(K) or O(KlogN). There are several ways to do that, let's consider some of them.

The first way is to store the numbers of all alive knights in std::set (C++) or TreeSet (Java). Then in C++ we can use lower_bound method to find the first knight in the fight that is alive, and to iterate over this set, each time moving to the next alive knight. In Java we should use subSet method.

    set<int> alive;
    for (int i = 0; i < n; i++)
        alive.insert(i);
        
    for (int i = 0; i < m; i++) {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        l--, r--, x--;        
        set<int>::iterator it = alive.lower_bound(l);
        vector<int> toErase;        
        while(it != alive.end()){
            int cur = *it;            
            if(cur > r)
                break;                
            if(cur != x){    
                toErase.pb(cur); answer[cur] = x;
            }
            it++;
        }

        for (size_t j = 0; j < toErase.size(); j++)
            alive.erase(toErase[j]);
    }

The second way is to define array next with the following meaning:

• if knight v is alive, then next[v] = v;
• if knight v is out of tournament, next[v] points to some knight u (next[v] = u), such that there are no alive knights between v and u;

To find the first alive knight starting from the knight v we need to follow this links until we find the first knight w with next[w] = w. In order not to pass the same links too many times, we will use the trick known as path compression (it is used in Disjoint Set Union). Note that you should handle the case when the current knight is the last knight and is out of tournament.

    int getNext(int v){
        if(next[v] == v)
            return v;
        return next[v] = getNext(next[v]);
    }

    ...

     int cur = getNext(l);
     while(cur <= r){
        if(cur == x){
            cur = cur + 1;
        }else{
            answer[cur] = x;
            next[cur] = cur + 1;
        }

        cur = getNext(cur);
    }

356B - Xenia and Hamming

Let's denote the length of the first string as lenX, the length of the second string as lenY. Let L = LCM(lenX, lenY). It's obvious that L is a period of the long strings a and b, so we can find the distance of its' prefixes of length L and multiply the answer by . Let's fix the position i in the string x and think about all characters from the second string it will be compared with. It it easy to conclude that it will be compared with such y_j that i ≡ j (mod g), where g = GCD(lenX, lenY). For each possible remainder of division by g and for each character c we can calculate count(r, c) — the number of characters c that appear in y in such positions j that j mod g = r. When calculating the Hamming distance, the character x_i will be compared with exactly count(i mod g, x_i) characters from y that are equal to it, all other comparisons will add one to the distance.

private void solve() {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong(), m = in.nextLong();
        String x = in.next(), y = in.next();
        int lenX = x.length(), lenY = y.length();
        int g = gcd(lenX, lenY);
        long L = lenX * (long)lenY / g;
        long answer = L;
        int[][] count = new int[g][26];
        for (int j = 0; j < lenY; j++) {
            count[j % g][y.charAt(j) - 'a']++;
        }
        for (int i = 0; i < lenX; i++) {
            answer -= count[i % g][x.charAt(i) - 'a'];
        }
        System.out.println(answer * (n * lenX / L));
    }

356C - Compartments

In the problem you should come up with some right greedy algorithm. One of correct approaches acts as follows:

1. Firstly, it joins all "twos" and "ones" (to get "threes"). Several "ones" should be moved.
2. Then you should consider two cases depend on amounts of "ones" and "twos". If initially you have more "ones", you should try to join remaining after the first point "ones" into groups of three. If initially you have more "twos", you should try to join remaining after the first point "twos" into groups of three. You can get two "threes" from three "twos".
3. After the first point and the second point some "ones" or "twos" can remain. You shouldn't come up with common solution. Else you should just to consider all possible cases.

To solve the problem you should follow your common sense (is it greedy?). Writing naive solution (bfs search) for stress purposes is not so bad for proving correctness of your solution.

356D - Bags and Coins

It's easy to see that bags and their relations "lies directly in" should form directed forest. Each vertex should be given value c_i — the number of coins in the corresponding bag. Let's denote the sum of values c_j in the subtree of vertex i as f_i. The following conditions should be met:

• f_i = a_i
• then sum of f_i of roots equals s.

It's clear that one of the bags with largest a_i must be the root of some tree. It's quite easy to see that the solution exists if and only if there exists a subset a_i1, a_i2, ..., a_ik such that a_i1 + a_i2 + ... + a_ik = s and this subset contains at least one bag with the largest a_i. It's obvious that it is necessary condition, the sufficiency is also easy to see: let's suppose we have such subset. Then all bags from the subset, except one of the largest, will be roots of the signle-vertex trees (i.e. c_i = a_i for them). All bags that are not in the subset we will consequentially put into the largest bag, forming the "russian doll" (this tree will be directed chain).

So, we reduced the task to the well-known subset-sum problem: from the items a₁, a₂, ... a_n find the subset with the given sum s. This problem is NP-Complete, and with these constraints is solved in a following way: let T(i, j) = 1 if it is possible to obtain sum j using some of the first i items, and T(i, j) = 0 otherwise. Then . The i-th row of this table depends only on the previous row, so we don't have to store the whole table in memory. Also we should use the fact that the values of the table are zeroes and ones, and we can use bit compression and store each row in an array of int's of size . To get the i-th row, we should calculate the bitwise OR of the previous row and the previous row shifted to the left by a_i positions. That is, we can find out whether it possible to obtain the sum s in approximately operations. To find the actual way to obtain s, we need to use the following trick: for every possible sum j we will remember the value first(j) — the number of such item that after considering this item it became possible to obtain j. This allows us to restore the solution.

356E - Xenia and String Problem

During the contest most of participants write the solutions that are very similar to the author's one. One of the author's solution uses hashes (but there exist solution without it), you can see short description of the solution below:

1. For each position i calculate with hashes the maximal value of L_i, such that substring s[(i - L_i + 1)..(i + L_i - 1)] is Gray string. Also, calculate the maximal value P_i, that substring s[(i - P_i + 1)..(i + P_i - 1)] differs from some Gray string in at most one position. You can see that P_i ≥ L_i. If P_i > L_i, also remember position and letter in the position, that differs Gray string and the substring.

2. You can see, that if we don't need to change letters, then the answer for the problem is , where f(L) = 1² + 3² + 7² + ... + L². So, calculate an answer without changes.

3. Next, iterate through all positions and letters in it. What is the new answer for the problem? Look at all Gray strings that occurs in our string and touches our fixed position. After we change this position the string will not be Gray string anymore (so we should subtract the squired length of the string from our answer). Look at all Gray strings that differs in exactly fixed position from some substring of the string. If we change the letter in the position to the fixed letter, all such strings will be added to the answer (and we should add their squired lengths).

4. Summary, with P_i and L_i we need to calculate for each position and letter, how the answer differs if we change the letter in the position to the fixed one. For that reason we should use offline update (+=) on the segment. After the values will be calculated we can update our answer with all possible values.

Hi all.

Today there is a school regional team competition in programming in Saratov. We've decided to make a round using tasks from this competition. The problems were prepared by Gerald (Gerald Agapov), Fefer_Ivan (Ivan Fefer), HolkinPV (Pavel Kholkin), Igor_Kudryashov (Igor Kudryashov), IlyaLos (Ilya Los) and Nerevar (Dmitry Matov). The problems' statements were translated into english by Mary Belova (Delinur).

The round starts today, on 15th of October, at 16:00 MSK. Parcipants from both divisions are welcome to take part in it.

The scoring is standard: 500-1000-1500-2000-2500.

Congratulations to the winners!

Division I:

1. tourist
2. mmaxio
3. Dmitry_Egorov
4. iwiwi
5. bmerry

Division II:

1. Apsara
2. ZJUDBLab
3. noxe
4. intsashka
5. Kanari

UPD: The tutorial is published.

254A - Cards with Numbers

For each x from 1 to 5000 store a list L(x) of such indexes i that a_i = x. Then just check that all lists have even size and output the elements of each list in pairs.

254B - Jury Size

One of the possible solutions is: for each Olympiad find the period of the preparation. This can be done by iterating the days back from the day of the Olympiad. For each day d of the preparation add p_i to the number of distinct jury members that have to work on problems on day d. Then the answer is maximum calculated sum over all days. Be careful with the year 2012.

254C - Anagram

Lets denote the number of character x in s by C_s(x). Similarly C_t(x) is defined. Then the minimum number of changes required to get anagram of t from s is equal to . Now we need to obtain lexicographically minimum solution. Lets iterate through the positions in s from the left to the right. For a fixed position, look through all characters from 'a' to 'z' and for each character decide whether the optimal answer can contain this character in that position. If it can, put this character in that position and continue with the next position. To check if the given character is suitable quickly, we maintain the values C_s(x) and C_t(x) while iterating through positions.

254D - Rats

Choose arbitrary rat (for say, the leftmost of the upmost). It's cell should be cleared. Make a BFS that never goes further than d from this cell (we will call such a BFS by d-BFS). It will visit approximately 2d² cells in the worst case. So, we have to blow the first grenade in one of the visited cells. Lets check every visited cell as a candidate. Make a d-BFS from the candidate cell. Some cells with the rats will not be visited. That means that they should be cleared by the second grenade. Choose arbitrary cell with a rat that was not cleared by the first grenade. Make a d-BFS from it. All cells visited by this BFS are candidates to blow the second grenade. Lets check every such cell. Checking a cell again means making a d-BFS from it. If this BFS visits all cells that were not cleared by the first grenade, that we have found a solution. As every d-BFS visits at most 2d², the overall number of steps is approximately 8d⁶.

254E - Dormitory

The problem can be solved by dynamic programming: denote as D(n, r) the maximum rating that we can achieve in the first n days with the condition that we have r kilos of food remaining from the day n - 1. It is obvious that if we decide to feed k friends on some day, the better way is to feed k friends with the lowest f_j (of course we consider only friends that live with Vasya on that day). So we need to sort all available students in the order of increasing f_j and try to feed 0, 1, 2, \ldots first students in this order. We have 400² states and 400 transitions from each state.

Sorry for the short tutorial: we are too busy preparing and conducting school competition.

253A - Boys and Girls

Lets assume that we have more boys than girls (the other case is solved similarly). Then we can construct one of the optimal solutions in the following way: we add pairs consisting of a boy and a girl (BG, in that order) to the end of the line until we don't have girls any more. Then add remaining boys to the end of the line. For instance, with 7 boys and 4 girls we will come to the solution BGBGBGBGBBB.

253B - Physics Practical

For each x from 1 to 5000 calculate count(x) — the number of measurements equal to x. The iterate over all possible minimal values m (from 1 to 5000). For a fixed m we can easily figure out which numbers we have to erase: we should erase every number k that k < m or k > 2·m. To find out the number of such values in the given sequence, we should sum up values count(k) for all such k.

253C - Text Editor

One of the solutions to the problem is breadth-first-search (BFS). Vertices of the graph correspond to all possible pairs (r, c), denoting the row and the position of the cursor. Each vertex has at most four arcs leaving it (these arcs correspond to pressing the buttons). So we need to find the shortest path from one vertex to the other. There are at most 10⁷ vertices and at most 4·10⁷ arcs. This problem can also be solved with some greedy observations.

253D - Table with Letters - 2

Lets iterate over all pairs of rows i, j (i < j), that bounds the sub-table from the top and from the bottom. Then for each character ch make a list of such column numbers k that T[i, k] = T[j, k] = ch. Consider such list for some fixed character ch. All we need to count is the number of pairs l, r (l < r) in this list such that the sub-table with corners at (i, l) and (j, r) contains not more than k characters "a". This can be done using two standard techniques: two-pointer method and calculating partial sums.

253E - Printer

First lets learn how to simulate the process with all priorities known. We will keep the priority queue of tasks. The task enters the queue when the printer receives this task, and leaves the queue when the printer finishes it. Then every change in the queue happens when one of the two possible events occurs: the printer receives some task or finishes printing some task. Between the consecutive events printer just prints pages from the tasks with the highest priority. So, if we maintain a set of events, the simulation can be done in O(NlogN).

To solve the problem, make an obvious observation: the higher priority the task has, the sooner the printer finishes it. Then the required missing priority can be found using binary search. Also we can search the missing priority among O(N) values. The overall complexity is O(Nlog²(N)).

This problem also has O(NlogN) solution, which will be described later.

Hello everybody.

On the 8th and on the 9th of December there will be local two-stage school competition in Saratov. We decided that it will be interesting to allow everybody to solve problems from it. So I am glad to announce that this weekend there will be two Div2 rounds.

The first round — Codeforces Round #154 (Div. 2) — will start at 14:00 MSK on the 8th of December.

The second round — Codeforces Round #155 (Div. 2) — will start at 14:00 MSK on the 9th of December.

Rounds will be held under usual CF rules, with one condition:

Problems will require file I/O: you have to read data from input.txt and write data to output.txt.

Score distribution will be announced just before the beginning of each round.

Participants from Div1 can take part in rounds out of competition.

UPD Here are links to solutions with file I/O in some languages:

• C++: 2366378
• Pascal: 2454867
• Java: 2366738
• Python: 2387503
• D: 2436251
• Scala: 2385341
• Haskell: 2378010
• C: 2519130
• Ruby: 2375494
• PHP: 2381582
• C# 2716641

UPD2 Score distribution in round 155 will be standard: 500-1000-1500-2000-2500.

UPD3 Tutorial is available for round 154.

UPD4 Unfortunately, in the first half of the contest, it was found that the task C checker does not check the lexicographically minimality of the answer. We offer our apologies for this error. So we adjusted checker. We conducted an investigation and found that the change has affected 53 members from the second division. We believe that a completely fair to make this competition for such participants unrated. This inaccuracy had absolutely no effect to all other.

UPD5 Tutorial is available for round 155.

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.