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.