363A - Соробан

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 - Забор

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 - Исправление опечаток

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 - Прокат велосипедов

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 - Два круга

At first, for each valid center cell (i, j) calculate circleSum[i][j] — sum of values inside the circle with center at (i, j). This can be done with the code like that:

 for (int i0 = r; i0 + r < n; i0++) {
            for (int j0 = r; j0 + r < m; j0++) {
                int sum = 0;
                int lj = j0, rj = j0;
                for (int i = i0 - r; i <= i0 + r; i++) {
                    while (dist2(i0, j0, i, lj) > r * r) lj++;
                    while (dist2(i0, j0, i, lj - 1) <= r * r) lj--;
                    while (dist2(i0, j0, i, rj) > r * r) rj--;
                    while (dist2(i0, j0, i, rj + 1) <= r * r) rj++;
                    sum += rowSum[i][rj + 1] - rowSum[i][lj];
                }
                circleSum[i0][j0] = sum;
            }
        }

This code iterates over all rows from top to bottom and keeps lj and rj — the leftmost and the rightmost columns in current row i that are inside the circle with center at (i0, j0). The function dist2 returns squared distance between two cells, rowSum[i][j] is equal to sum of first j cells in row i. In total, values lj and rj will be changed O(n + m) times, so the complexity of this part is O(nm(n + m)).

In the second part of the solution, for each row i we calculate several values:

• leftMax[i][j] — maximum of circleSum[i][k] for k ≤ i
• cntLeftMax[i][j] — the number of corresponding maximum values
• rightMax[i][j] — maximum of circleSum[i][k] for k ≥ i
• cntRightMax[i][j] — the number of corresponding maximum values

All these values can be calculated in O(nm) time.

The third part of the solution is the most tricky one. Let's say that the cell (i, j) is boundary cell for the circle centered at (i₀, j₀) if it belongs to this circle and is the leftmost or the rightmost such point in row i. It is easy to see that two circles A and B intersect if and only if there exists a boundary cell of the circle A that belongs to the circle B. As long as we have O(n + m) boundary cells for each circle, checking whether two given circles intersect can be done in linear time. Now, for each pair (di, dj), which means the relative position of one center to the other, we can determine if such two circles intersect. There are O(nm) pairs (di, dj), so the total complexity of this part is O(nm(n + m)).

And, finally, in the fourth part we are going to calculate the answer. Let's iterate over all triples of values (i₀, j₀, i), where (i₀, j₀) is a valid center cell and i is a row number. Consider the set of cells (i, j) in the row i such that the circle centered at (i, j) intersects with the circle at (i₀, j₀). It is clear that this set is consists of some (possibly zero) consequtive cells in a row. Let's assume that these cells are (i, lj), (i, lj + 1), ..., (i, rj), values lj and rj can be found in the third part of the solution. We are interested in cell that are not in this set: (i, j) with j < lj or j > rj. To find the maximum sum in such circles in O(1), we use arrays computed in the second part. Overall complexity of the solution is O(nm(n + m)).