Problemset was prepared by Yandex employees.

Problem А. ZeroOne

Firstly, let's convert input strings into two binary strings. Because the numbers can be approximately $$$2^{333}$$$ we shouldn't convert them into the numeric type and should compare their string representations

#include <iostream>
#include <algorithm>

int main() {
    std::string s[2];
    std::cin >> s[0] >> s[1];


    std::string r[2];

    for(int i = 0; i < 2; ++i) {
        while (!s[i].empty()) {
            if (s[i].substr(s[i].size() - 3, 3) == "one") {
                s[i].pop_back();
                s[i].pop_back();
                s[i].pop_back();
                r[i] += "1";
            } else {
                s[i].pop_back();
                s[i].pop_back();
                s[i].pop_back();
                s[i].pop_back();
                r[i] += "0";
            }
        }
    }

    for(auto & s : r) {
        std::reverse(s.begin(), s.end());
    }
    
    if (r[0].size() > r[1].size()) {
        std::cout << ">";
    } else if (r[1].size() > r[0].size()) {
        std::cout << "<";
    } else if (r[0] > r[1]) {
        std::cout << ">";
    } else if (r[0] == r[1]) {
        std::cout << "=";
    } else {
        std::cout << "<";
    }

    return 0;
}

Problem B. Tiles 2x2

To solve to problem we can introduce equivalence classes of tiles $$$2 \times 2$$$. If the number of tiles of each class in the set is not less than the required number for the picture, the result will be positive.

To determine the equivalence class one can choose the main representative of the class. In the case of the matrix $$$2\times 2$$$ the minimum tuple of all four rotations of the matrix is suitable.

import collections


def normalize(a, b): # write cells in clockwise order
	return min(a[0] + a[1] + b[1] + b[0], 
		a[1] + b[1] + b[0] + a[0], 
		b[1] + b[0] + a[0] + a[1],
		b[0] + a[0] + a[1] + b[1])


def main():
	k = int(input())
	tile_set = collections.defaultdict(int)
	for _ in range(k):
		a = input()
		b = input()
		tile = normalize(a, b)
		tile_set[tile] += 1
	n, m = map(int, input().split())
	for _ in range(n // 2):
		a = input()
		b = input()
		for j in range(0, m, 2):
			tile = normalize(a[j:j+2], b[j:j+2])
			tile_set[tile] -= 1

	print('Yes' if min(tile_set.values()) >= 0 else 'No')


if __name__ == '__main__':
	main()

Problem C. Balls and Boxes

Let $$$sumA = \sum_{i = 1}^k a_i$$$. To check whether a certain number of boxes $$$x, 1\le x\le sumA,$$$ satisfies all conditions the following must be fulfilled:

• x is a divisor of $$$sumA$$$
• $$$a_i - x \cdot b_i \ge 0$$$ for each color $$$i$$$

So, we can iterate over the divisors of the number $$$sumA$$$, check the fulfillment of the second condition, and choose the maximum $$$x$$$ that the condition is met.

The tricky part of the problem is to print the result. One should be attentive with the case $$$b_i=0$$$.

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int k;
    std::cin >> k;


    int sum = 0;
    std::vector<int> a(k);
    for(int i = 0; i < k; ++i) {
        std::cin >> a[i];
        sum += a[i];
    }

    std::vector<int> possible;

    for(int i = 1; i <= sum; ++i) {
        if (sum % i == 0) {
            possible.push_back(i);
        }
    }

    std::reverse(possible.begin(), possible.end());

    std::vector<int> every_need;

    int sumb = 0;
    std::vector<int> b(k);
    for(int i = 0; i < k; ++i) {
        std::cin >> b[i];
        sumb += b[i];
        for(int j = 0; j < b[i]; ++j) {
            every_need.push_back(i + 1);
        }
    }

    int ans = -1;

    for(auto i : possible) {
        bool ok = true;

        for(int j = 0; j < k; ++j) {
            if (b[j] != 0) {
                if (a[j] / b[j] < i) {
                    ok = false;
                    break;
                }
            }
        }

        if (ok) {
            ans = i;
            break;
        }
    }


    if (ans == -1) {
        std::cout << -1;
        return 0;
    }

    std::vector<int> free;
    for(int i = 0; i < k; ++i) {
        a[i] -= b[i] * ans;
        for(int j = 0; j < a[i]; ++j) {
            free.push_back(i + 1);
        }
    }

    int in_every = sum / ans;
    std::cout << ans << ' ' << in_every << std::endl;

    for(int i = 0; i < ans; ++i) {
        for(auto j : every_need) {
            std::cout << j << ' ';
        }

        for(int j = 0; j < in_every - sumb; ++j) {
            std::cout << free.back() << ' ';
            free.pop_back();
        }
        std::cout << std::endl;
    }
    
    return 0;
}

Problem D. Matrix

For convenience, we will use the following notation $$$n=2^{n'}$$$, $$$m=2^{m'}$$$.

1. Let's consider the case $$$n=m,\,n>1$$$. After the first step the matrix has the following form:

After the second step the matrix has the following form:

Thus, after the second step and until the very end, the entire matrix is filled with the same numbers.

Summarizing this information, the total of different numbers will be written out is $$$n^{2}+\frac{n}{2}+\log_2{\frac{n^2}{2}}$$$ ($$$1$$$, $$$2$$$, ..., $$$n^2$$$, $$$n^2+2$$$, $$$n^2+4$$$, ..., $$$n^2+n$$$, $$$2(n^2+1)$$$, $$$2^2(n^2+1)$$$, ..., $$$\frac{n^2(2n^2+1)}{2}$$$.

1. Let's consider the case $$$n<m$$$. After the first step the matrix has the following form:

After the $$$i_{th}$$$ of following ($$$m'-n'-1$$$) steps the matrix has the following form:

Note that in these matrices any number over $$$nm$$$ occurs only once (an entire row of one of the matrices). At the next step and until the very end, the entire matrix is filled with the same numbers.

Unlike the first case, we can consider each of the $$$n$$$ rows of the matrix separately ($$$n < 2^{15}$$$).

1. Let's consider the case $$$n>m$$$. After the first step the matrix has the following form:

After the $$$i_{th}$$$ of following ($$$n'-m'$$$) steps the matrix has the following form:

It should be noted that the maximum element of the matrix at step $$$i$$$ is less than the minimum element of the matrix at step $$$i+1$$$.

Summarizing this information, there are $$$nm+\frac{m}{2}+m\log_2{\frac{n}{m}}+\log_2{\frac{m^2}{2}}$$$ different numbers will be written out .

import sys
import math


def log2(n):
	return 0 if n <= 1 else int(math.log(n, 2))


def main():
	n, m = map(int, input().split())
	_n = n * m
	result = _n
	if n == m:
		result += n // 2
		result += log2(n ** 2 // 2)
	elif n < m:
		for i in range(n):
			x = 1 + (2 * i + 1) * m
			for j in range(log2(m // n)):
				if x > _n:
					result += 1
				x *= 2
		result += log2(n ** 2)
	else:
		result += m // 2
		result += m * log2(n // m)
		result += log2(m ** 2 // 2)

	print(result)


if __name__ == '__main__':
	main()

Problem E. Matrix sort

Let us consider the set of zeros in the sorted matrix. The number of operations is the number of ones in the original matrix inside this set. The set of zeros forms a Young tableau which is the set of cells, such that in each row and column zeroes form a prefix. So we need to construct Young tableau of the given size which contains the least amount of ones in the original matrix.

We are going to solve the problem with dynamic programming. For each cell of the matrix we consider the rectangle with one corner in this cell and the opposite corner in the right upper corner of the matrix. For each possible size of Young tableau inside this rectangle we calculate the least number of ones it can contain. There are $$$O(nm)$$$ cells in the matrix and $$$O(nm)$$$ sizes of Young tableau so we need to solve $$$O((nm)^2)$$$ subproblems.

Let us show how to solve each subproblem. Let us consider the cell in the left lower corner of the rectangle where we consider our Young tableaus. It is either belongs to the Young tableau(meaning that it will contain zero in the end) or not.

If it belongs to the Young tableau, then all cells above it belong to the Young tableau too. In this case we reduced our problem to the rectangle with left lower corner one cell to the right from our cell and Young tableau size is reduced by the size of the column. In order to calculate how many ones we got inside the column, we precalculate for each cell of the matrix the number of ones non-strictly above it in the same column. This precalculation can be made in $$$O(nm)$$$, if we go from top to bottom.

In the second case, the left lower corner does not belong to the Young tableau. In this case we reduced our problem to the rectangle with left lower corner one cell above from our cell and Young tableau size as well as the answer remained unchanged.

All what is left, is to take the minimum of these two cases. Each case requires $$$O(1)$$$ time, so all cases require $$$O((nm)^2)$$$ time. The states of the dynamic programming can be calculated from top to bottom and from right to left. Moreover, we can only store current and the next row or column. So we only need $$$O(\min(n^2m, nm^2))$$$ memory.

Problem F. Path Reverse

$$$O(n^2)$$$ solution

To solve this problem in $$$O(n^2)$$$, it's enough to iterate over all pairs $$$(p, q)$$$ and for each of them find the answer in $$$O(1)$$$.

In this solution, we must be able to find the distance between every pair of vertices in $$$O(1)$$$. We can precalculate them: just run dfs or bfs from each vertex and get $$$d_{ij}$$$ — the distance between vertices $$$i$$$ and $$$j$$$.

When $$$p$$$ and $$$q$$$ are fixed, each vertex $$$x$$$ belongs to one of the four following kinds:

• $$$x$$$ lies on the path between $$$p$$$ and $$$q$$$, inclusively. This can be checked with this condition: $$$d_{px} + d_{xq} = d_{pq}$$$.
• $$$x$$$ lies in the part of tree behind vertex $$$p$$$, or $$$d_{xp} + d_{pq} = d_{xq}$$$.
• $$$x$$$ lies in the part of tree behind vertex $$$q$$$, or $$$d_{pq} + d_{qx} = d_{px}$$$.
• $$$x$$$ lies on a branch connected to the path $$$p-q$$$. This happens if all three of the conditions above are false.

How can vertices $$$1$$$ and $$$n$$$ be located relative to $$$p$$$ and $$$q$$$? There are 16 cases in general: $$$1$$$/$$$n$$$ (independent) can have one of four relations above (4 choices). The distance between $$$1$$$ and $$$n$$$ changes only in these cases (actually in 8 cases out of 16):

• $$$1$$$ is behind $$$p$$$, $$$n$$$ is on path $$$p-q$$$ or lies on a branch.
• $$$1$$$ is behind $$$q$$$, $$$n$$$ is on path $$$p-q$$$ or lies on a branch.
• $$$n$$$ is behind $$$p$$$, $$$1$$$ is on path $$$p-q$$$ or lies on a branch.
• $$$n$$$ is behind $$$q$$$, $$$1$$$ is on path $$$p-q$$$ or lies on a branch.

As they are identical, consider only the first one. So, $$$1$$$ is behind $$$p$$$, and $$$n$$$ lies on a path $$$p-q$$$ or on a branch. Before the reverse operation the distance was $$$d_{1p} + d_{pn}$$$, and after the swap it becomes $$$d_{1p} + d_{qn}$$$. Problem solved, 2 points are ours.

Solution for a line case

Here our tree is a line, but we must do it in $$$O(n)$$$. The distance changes only when one of $$$p$$$ and $$$q$$$ lies outside path $$$1-n$$$ and the other one lies inside.

First of all, calculate the distance between $$$1$$$ and $$$n$$$ and multiply it by $$$\frac{n(n-1)}{2}$$$. We will find how answer changes after reverse operations, not calculate it from scratch every time.

Let's say $$$1$$$ is to the left of $$$n$$$, and denote the number of vertices strictly to the left of $$$1$$$ as $$$a$$$, and strictly between $$$1$$$ and $$$n$$$ as $$$b$$$.

.... (a slots) .... [1] .... (b slots) .... [N] ....

Let $$$d$$$ be the delta the answer increases by after the reverse. If $$$p$$$ is in one of the $$$a$$$ slots to the left of $$$1$$$, how many slots for $$$q$$$ on path $$$1-n$$$ can produce this delta $$$d$$$? Let's show the pictures for $$$d=1$$$ and $$$d=2$$$:

$$$d = 1$$$:

    .... (a slots) .... [1] .... (b slots) .... [N] ....

[ ] [ ] [ ] [ ] [ ] [p] [q] [ ] [ ] [ ] [ ] [ ] [N] [ ] [ ]
[ ] [ ] [ ] [ ] [p] [ ] [1] [q] [ ] [ ] [ ] [ ] [N] [ ] [ ]
[ ] [ ] [ ] [p] [ ] [ ] [1] [ ] [q] [ ] [ ] [ ] [N] [ ] [ ]
...

$$$d = 2$$$:

    .... (a slots) .... [1] .... (b slots) .... [N] ....

[ ] [ ] [ ] [ ] [p] [ ] [q] [ ] [ ] [ ] [ ] [N] [ ] [ ] [ ]
[ ] [ ] [ ] [p] [ ] [ ] [1] [q] [ ] [ ] [ ] [N] [ ] [ ] [ ]
[ ] [ ] [p] [ ] [ ] [ ] [1] [ ] [q] [ ] [ ] [N] [ ] [ ] [ ]
...

Hope you got the pictures. For fixed $$$d$$$, the answer is $$$\min(a - d + 1, b + 1)$$$ (one of the segments with slots ends sooner, that's why there is minimum in the formula). So we add $$$d \cdot \min(a - d + 1, b + 1)$$$ to the total answer.

Deltas can be negative (the distance between $$$1$$$ and $$$n$$$ can decrease). This are the pictures for negative deltas:

$$$d = 1$$$:

    .... (a slots) .... [1] .... (b slots) .... [N] ....

[ ] [ ] [ ] [ ] [ ] [ ] [q] [p] [ ] [ ] [ ] [N] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [q] [1] [ ] [p] [ ] [ ] [N] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [q] [ ] [1] [ ] [ ] [p] [ ] [N] [ ] [ ] [ ]
...

$$$d = 2$$$:

    .... (a slots) .... [1] .... (b slots) .... [N] ....

[ ] [ ] [ ] [ ] [ ] [ ] [q] [ ] [p] [ ] [ ] [N] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [q] [1] [ ] [ ] [p] [ ] [N] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [q] [ ] [1] [ ] [ ] [ ] [p] [N] [ ] [ ] [ ]
...

Here, the formula for a certain $$$d$$$ is $$$\min(b - d + 1, a + 1)$$$.

Positive $$$d$$$ can change from $$$1$$$ to $$$a$$$, and negative $$$d$$$ can change from $$$1$$$ to $$$b$$$ (by absolute value). For each of these $$$d$$$ we find the answer's delta in $$$O(1)$$$.

Challenge: actually, knowing $$$a$$$ and $$$b$$$, it's possible not to iterate over $$$d$$$ (which would be $$$O(n)$$$), but calculate everything in $$$O(1)$$$. Can you discover the formula?

Solution for a general case

In $$$O(n^2)$$$ solution, we divided all vertices into four classes depending on their location relative to $$$p$$$ and $$$q$$$. Here we will need the similar thing but relatively to $$$1$$$ and $$$n$$$.

Let's say $$$d_{1x}$$$ is the distance from $$$x$$$ to $$$1$$$, and $$$d_{nx}$$$ — from $$$x$$$ to $$$n$$$. Also let's say $$$m$$$ is the distance between $$$1$$$ and $$$n$$$. Then, vertices can be:

• behind $$$1$$$ or equal to $$$1$$$: $$$d_{1x} + m = d_{nx}$$$,
• behind $$$n$$$ or equal to $$$n$$$: $$$d_{1x} = m + d_{nx}$$$,
• strictly inside the path $$$1-n$$$: $$$d_{1x} + d_{nx} = m$$$, but $$$x \ne 1$$$ and $$$x \ne n$$$,
• on a branch, if all three conditions above are false.

Answer changes in two general cases:

• $$$p$$$ is strictly between $$$1$$$ and $$$n$$$ or equal to one of them, and $$$q$$$ is behind $$$1$$$ or $$$n$$$,
• $$$p$$$ is strictly between $$$1$$$ and $$$n$$$, and $$$q$$$ lies on a branch, and the root of the branch $$$z$$$ is strictly between $$$1$$$ and $$$n$$$, and $$$p \ne z$$$.

First case:

Let's iterate over $$$q$$$. Now we have fixed $$$q$$$. How can the answer change?

... [Q] ..... (a slots) ... [1] ... (b slots, P is somewhere on [1, N)) ... [N] ...

... [Q] [ ] [ ] [ ] [ ] [ ] [p] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [N] ...
... [Q] [ ] [ ] [ ] [ ] [ ] [1] [p] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [N] ...
... [Q] [ ] [ ] [ ] [ ] [ ] [1] [ ] [p] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [N] ...
... [Q] [ ] [ ] [ ] [ ] [ ] [1] [ ] [ ] [p] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [N] ...
...
... [Q] [ ] [ ] [ ] [ ] [ ] [1] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [p] [N] ...

For the first row ($$$p=1$$$), the delta is $$$a$$$ (which is equal to $$$d_{1q})$$$, for the second row — $$$a-1$$$, and so on. Finally, when $$$n$$$ and $$$p$$$ are neighbors, it's $$$a-b$$$ (it may be negative if $$$a < b$$$, it's fine). So the result is the sum of consecutive numbers between $$$a$$$ and $$$a - b$$$ and can be found in $$$O(1)$$$.

If you solve this case correctly and completely ignore the second case, you will get 2 points, as this solves the line subtask.

Second case:

Let's again iterate over $$$q$$$. Knowing $$$d_{1q}$$$ and $$$d_{nq}$$$, we can find the branch root $$$z$$$ (as we can calculate the length of the branch, which is $$$\frac{d_{1q} + d_{nq} - m}{2}$$$, where $$$m$$$ is distance between $$$1$$$ and $$$n$$$, $$$m = d_{1n}$$$) and its $$$d_{1z}$$$ and $$$d_{nz}$$$. Here we again have two identical cases (choice between $$$1$$$ and $$$n$$$), let's show one of them.

                                                    ...
                                                    [N]
                                                    [ ]
                                                    ...
                                                    [ ]
... [1] ... (a slots, P is somewhere on (1, Z)) ... [Z] ... (b slots) ..... [Q] ...

... [1] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [p] [Z] [ ] [ ] [ ] [ ] [ ] [Q] ...
... [1] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [p] [ ] [Z] [ ] [ ] [ ] [ ] [ ] [Q] ...
... [1] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [p] [ ] [ ] [Z] [ ] [ ] [ ] [ ] [ ] [Q] ...
...
... [1] [p] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [Z] [ ] [ ] [ ] [ ] [ ] [Q] ...

Here, $$$a = d_{1z} - 1$$$, $$$b$$$ is the branch length minus 1. As shown at the picture, answer changes when $$$p$$$ runs from $$$1$$$ to $$$z$$$, not including $$$1$$$ and $$$z$$$. It is again a sum of consecutive numbers: $$$b + (b-1) + \ldots + (b-a+1)$$$ and again can be calculated in $$$O(1)$$$.

So for each of two general cases, we iterate over all $$$q$$$ and for each $$$q$$$ find the answer is $$$O(1)$$$, which gives the total complexity $$$O(n)$$$.

int64_t arithmSum(int64_t first, int64_t last) {
    if (first > last) {
        swap(first, last);
    }
    const int64_t len = last - first + 1;
    return (first + last) * len / 2;
}

// vertices in the solution are 0-indexed
vector<int> d1; // d1[x] is the distance between x and 0
vector<int> dn; // dn[x] is the distance between x and (n - 1)

const int m = d1[n - 1];
const int64_t initialAns = int64_t(m) * n * (n - 1) / 2;

auto isOnPath = [&](const int x) -> bool {
    if (x == 0 || x == n - 1) return false;
    return d1[x] + dn[x] == m;
};
auto isOutside1 = [&](const int x) -> bool {
    return d1[x] == dn[x] - m;
};
auto isOutsideN = [&](const int x) -> bool {
    return dn[x] == d1[x] - m;
};
auto isOnBranch = [&](const int x) -> bool {
    if (isOnPath(x)) return false;
    if (isOutside1(x)) return false;
    if (isOutsideN(x)) return false;
    return true;
};

// case 1
auto f1 = [](const int64_t a, const int64_t b) -> int64_t {
    // a + (a-1) + ... + (a-b)
    return arithmSum(a, a - b);
};
int64_t add1 = 0;
for (int q = 0; q < n; q++) {
    if (isOutside1(q)) add1 += f1(d1[q], m - 1);
    if (isOutsideN(q)) add1 += f1(dn[q], m - 1);
}

// case 2
auto f2 = [](const int64_t a, const int64_t b) -> int64_t {
    // b + (b-1) + ... + (b-a+1)
    if (a == 0) return 0;
    return arithmSum(b, b - a + 1);
};
int64_t add2 = 0;
for (int q = 0; q < n; q++) {
    if (isOnBranch(q)) {
        const int branchLength = (d1[q] + dn[q] - m) / 2;
        const int lenFrom1ToZ = d1[q] - branchLength;
        const int lenFromNToZ = dn[q] - branchLength;
        add2 += f2(lenFrom1ToZ - 1, branchLength - 1);
        add2 += f2(lenFromNToZ - 1, branchLength - 1);
    }
}

const int64_t ans = initialAns + add1 + add2;