Great efforts have been put over last year. We want to say thanks to everybody who helped us to make this round as it is. Cannot wait to see you guys on the next one!

Do we actually need to go off the axis?

How to avoid visiting an axis more than once?

1713A - Traveling Salesman Problem

Suppose we only have boxes on the $$$Ox+$$$ axis, then the optimal strategy is going in the following way: $$$(0, 0), (x_{max}, 0), (0, 0)$$$. There is no way to do in less than $$$2 \cdot |x_{max}|$$$ moves.

What if we have boxes on two axis? Let's assume it is $$$Oy+$$$, suppose we have a strategy to go in the following way: $$$(0, 0), (x_{max}, 0),..., (0, y_{max}), (0, 0)$$$. In this case it is optimal to fill the three dots with $$$(0, 0)$$$, which is just solving each axis independently.

Therefore, the number of axis does not matters. For each axis that has at least one box, go from $$$(0, 0)$$$ to the farthest one, then come back to $$$(0, 0)$$$.

Time complexity: $$$O(n)$$$

def solve():
    n = int(input())
    minX, minY, maxX, maxY = 0, 0, 0, 0
    for i in range(n):
        x, y = list(map(int, input().split()))
        minX = min(x, minX)
        maxX = max(x, maxX)
        minY = min(y, minY)
        maxY = max(y, maxY)
    print(2 * (maxX + maxY - minX - minY))


test = int(input())
while test > 0:
    test -= 1
    solve()

• Didn't solve
• Good problem
• Average problem
• Bad problem

How to calculate $$$f(a)$$$?

What if $$$a$$$ is intially sorted?

Consider $$$a$$$ has $$$3$$$ elements. What if $$$a_1 > a_2$$$ and $$$a_2 < a_3$$$?

1713B - Optimal Reduction

Let's call $$$M = max(a_1, a_2, \dots, a_n)$$$.

The problem asks us to make all its elements become $$$0$$$ in some operations. And for each operation, we subtract each elements in an subarray by $$$1$$$. Thus, every largest elements of the array have to be decreased in at least $$$M$$$ operations. And also because of that, $$$min(f(p))$$$ over all permutations $$$p$$$ of $$$a$$$ is never less than $$$M$$$.

Every permutations $$$p$$$ of $$$a$$$ such that $$$f(p) = M$$$ have the same construction. That is, they can be divided into $$$2$$$ subarrays where the left subarray is sorted in non-decreasing order, and the right subarray is sorted in non-increasing order. In other words, the elements of the array should form a mountain.

So how to check whether $$$f(a) = M$$$ or not? Well, we can define $$$preLen$$$ equal to the length of the longest prefix which is sorted in non-decreasing order. Then define $$$sufLen$$$ equal to the length of the longest suffix which is sorted in non-increasing order. If $$$preLen + sufLen \ge n$$$, the answer is YES.

Time complexity: $$$O(n)$$$

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n, a[N];

int main() {
    int tc;
    for (cin >> tc; tc--; ) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];

        int preLen = 1;
        while (preLen < n && a[preLen] <= a[preLen + 1])
            preLen++;

        int sufLen = 1;
        while (sufLen < n && a[n-sufLen] >= a[n-sufLen + 1])
            sufLen++;

        if (preLen + sufLen >= n)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}

• Didn't solve
• Good problem
• Average problem
• Bad problem

Is there any case that the answer doesn't exist?

What if: $$$n \le 5$$$

Construct the suffix instead of the prefix.

With any positive integer $$$x$$$, there is at least one square number in $$$[x, 2x]$$$. Proof.

1713C - Build Permutation

First, let's prove that the answer always exists. Let's call the smallest square number that is not smaller than $$$k$$$ is $$$h$$$. Therefore $$$h \leq 2 \cdot k$$$, which means $$$h - k \leq k$$$. Proof.

So we can fill $$$p_i = h - i$$$ for $$$(h - k \leq i \leq k)$$$. Using this method we can recursively reduce $$$k$$$ to $$$h - k - 1$$$, then all the way down to $$$-1$$$.

We can prove that $$$h - k \geq 0$$$, as $$$h \geq k$$$.

Time complexity: $$$O(n)$$$

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n, ans[N];

void recurse(int r) {
	if (r < 0) return;
	int s = sqrt(2*r); s *= s;
	int l = s - r; recurse(l - 1);
	for (; l <= r; l++, r--) {
		ans[l] = r; ans[r] = l;
	}
}

int main() {
	int tc; cin >> tc;
	while (tc--) {
		cin >> n; recurse(n - 1);
		for (int i = 0; i < n; i++)
			cout << ans[i] << ' ';
		cout << '\n';
	}
}

• Didn't solve
• Good problem
• Average problem
• Bad problem

We made sure that almost every $$$2^{n - 1}$$$ solutions cannot pass.

Did you use the $$$0$$$ query?

$$$\frac{2^{n + 1}}{3} = 2^n \cdot \frac{2}{3}$$$, what is the conclusion?

1713D - Tournament Coundown

There is a way to erase $$$3$$$ participants in every $$$2$$$ queries. Since there are $$$2^n - 1$$$ participants to be removed, the number of queries will be $$$\left \lceil (2^n - 1) \cdot \frac{2}{3} \right \rceil = \left \lfloor \frac{2^{n + 1}}{3} \right \rfloor$$$. Suppose there are only $$$4$$$ participants. In the first query we will ask the judge to compare the $$$1^{st}$$$ and the $$$3^{rd}$$$ participants. There are three cases:

• The $$$1^{st}$$$ participant wins more game than the $$$3^{rd}$$$ one: the $$$2^{nd}$$$ and $$$3^{rd}$$$ cannot be the winner.

• The $$$3^{rd}$$$ participant wins more game than the $$$1^{st}$$$ one: the $$$1^{st}$$$ and $$$4^{th}$$$ cannot be the winner.

• The $$$1^{st}$$$ and $$$3^{rd}$$$ participants' numbers of winning games are equal: both the $$$1^{st}$$$ and $$$3^{rd}$$$ cannot be the winner.

Ask the remaining two participants, find the winner between them.

If there are more than $$$4$$$ participants, we can continuously divide the number by $$$4$$$ again and again, until there are at most $$$2$$$ participants left. Now we can get the winner in one final query.

#include <bits/stdc++.h>

using namespace std;

int ask(vector<int> &k)
{
	cout << "? " << k[0] << ' ' << k[2] << endl;
	int x;
	cin >> x;
	if (x == 1)
	{
		cout << "? " << k[0] << ' ' << k[3] << endl;
		cin >> x;
		if (x == 1) return k[0];
		return k[3];
	}
	else if (x == 2)
	{
		cout << "? " << k[1] << ' ' << k[2] << endl;
		cin >> x;
		if (x == 1) return k[1];
		return k[2];
	}
	else
	{
		cout << "? " << k[1] << ' ' << k[3] << endl;
		cin >> x;
		if (x == 1) return k[1];
		return k[3];
	}
}

void solve()
{
	int n;
	cin >> n;
	vector<int> a, b;
	for (int i = 1; i <= (1LL << n); i++)
	{
		a.push_back(i);
	}
	while (a.size() > 2)
	{
		while (!a.empty())
		{
			vector<int> k(4);
			k[0] = a.back();
			a.pop_back();
			k[1] = a.back();
			a.pop_back();
			k[2] = a.back();
			a.pop_back();
			k[3] = a.back();
			a.pop_back();
			int win = ask(k);
			b.push_back(win);
		}
		a = b;
		b.clear();
	}
	if (a.size() == 2)
	{
		cout << "? " << a[0] << ' ' << a[1] << endl;
		int x;
		cin >> x;
		if (x == 2) a[0] = a[1];
	}
	cout << "! " << a[0] << endl;
}

int main(int argc, char ** argv)
{
	int tests;
	cin >> tests;
	while(tests--) solve();
}

• Didn't solve
• Good problem
• Average problem
• Bad problem

Think of the most to the least significant cell of the matrix.

How many positions in the matrix can a cell travel to after performing the operations?

And for each position that that cell can travel to, how many ways are there we can make it?

1713E - Cross Swapping

Let's take a look at what the lexicographically smallest matrix is. Let's call $$$(x, y)$$$ a cell that is in the intersection of row $$$x$$$ and column $$$y$$$ of the matrix, and the integer written on that cell is $$$A_{x, y}$$$. A cell $$$(x_p, y_p)$$$ of this matrix is called more significant than the another cell $$$(x_q, y_q)$$$ if and only if $$$x_p < x_q$$$, or $$$x_p = x_q$$$ and $$$y_p < y_q$$$. The problem asks us to find the smallest matrix so the best suitable way to solve this problem is to traverse through the most to the least significant cell of the matrix, then determine if the current cell can be minimized or not.

Suppose the current cell we are looking at is $$$(x, y)$$$. If $$$x = y$$$ then its position will not change after performing the operations. But if $$$x \neq y$$$, there are exactly $$$2$$$ operations that swap $$$(x, y)$$$ with another cell, that is $$$k = x$$$ and $$$k = y$$$. Both of these operations swap $$$(x, y)$$$ with the same cell $$$(y, x)$$$. So the only way we can minimize the value of $$$(x, y)$$$ is to try swapping it with $$$(y, x)$$$ (if $$$x < y$$$ and $$$A_{x, y} > A_{y, x}$$$) in some way.

As a result we have our constructive algorithm. Remind that for each operation $$$k = i$$$ of the matrix ($$$1 \le i \le n$$$), there are $$$2$$$ states: it is being performed and not being performed. Suppose we have traversed to the cell $$$(x, y)$$$. If $$$x \ge y$$$, ignore it. If $$$x < y$$$ then we try to make $$$A_{x, y} = min(A_{x, y}, A_{y, x})$$$ by deciding to swap or not to swap the cells. If $$$A_{x, y} > A_{y, x}$$$, try to swap $$$(x, y)$$$ with $$$(y, x)$$$ by making $$$2$$$ operations $$$k = x$$$ and $$$k = y$$$ having different states. And if $$$A_{x, y} < A_{y, x}$$$ then we should keep their positions unchanged by making $$$2$$$ operations $$$k = x$$$ and $$$k = y$$$ having the same state. Note that if $$$A_{x, y} = A_{y, x}$$$, we do nothing.

Let's implement this algorithm using a simple DSU where the $$$ith$$$ node represents the operation $$$k = i$$$. We define the value $$$par[u]$$$ in such a way that, suppose $$$p$$$ is the root of the $$$u$$$ node's component, $$$par[u] = p$$$ if $$$2$$$ operations $$$k = u$$$ and $$$k = p$$$ should have the same state, or $$$par[u] = -p$$$ if $$$2$$$ operations $$$k = u$$$ and $$$k = p$$$ should have different states. Define another function $$$join(i, j)$$$ to union $$$2$$$ nodes $$$i$$$ and $$$j$$$ to the same component. Note that $$$u$$$ and $$$-u$$$ are always in the same component and $$$par[-u] = -par[u]$$$. Thus, for the current cell $$$(x, y)$$$, we want to swap it with $$$(y, x)$$$ by calling $$$join(x, -y)$$$, or keep its position unchanged by calling $$$join(x, y)$$$.

After constructing the graphs, the last thing to do is to determine which operations should be performed. One way to do so is for each root of the components of the DSU, we perform the operation which this root represents for. Then for other nodes just check $$$par[i] > 0$$$ for the $$$ith$$$ node and if it is true, the $$$k = i$$$ operation should be performed. When we have the list of the operations that need to be performed, we can bruteforcely perform each operation from the list one by one and the final matrix will be the lexicographically smallest matrix.

Time complexity: $$$O(n^2)$$$

#include <bits/stdc++.h>
using namespace std;

const int N = 2e3 + 5;

int n, a[N][N];

int par[N];
int getPar(int u) {
    if (u < 0) return -getPar(-u);
    if (u == par[u]) return u;
    return par[u] = getPar(par[u]);
}
void join(int u, int v) {
    u = getPar(u); v = getPar(v);
    if (abs(u) != abs(v)) {
        if (u > 0) par[u] = v;
        else par[-u] = -v;
    }
}

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int tc; cin >> tc;
    while (tc--) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                cin >> a[i][j];
            }
    
        iota(par + 1, par + n + 1, 1);
        // set par[i] == i for i in [1, n]

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                if (a[i][j] < a[j][i]) join(i, j);
                if (a[i][j] > a[j][i]) join(i, -j);
            }
    
        for (int i = 1; i <= n; i++) {
            if (getPar(i) < 0) continue;
            // we only perform the operation
            // if and only if getPar(i) > 0
            for (int j = 1; j <= n; j++)
                swap(a[i][j], a[j][i]);
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cout << a[i][j] << ' ';
            }
            cout << '\n';
        }
    }
}

• Didn't solve
• Good problem
• Average problem
• Bad problem

• Is there any case that the answer doesn't exist?
• If exist, are there multiple?

• How many times does $$$a_i$$$ contribute to $$$b_{j, n}$$$?

$$$\rightarrow$$$ Calculate value that $$$a_i$$$ contribute to $$$b_{j, n}$$$.

Consider the inverse problem: Given array $$$a$$$. Construct $$$b_{j, n}$$$ for all $$$j$$$. How can you solve this problem?

Consider easier problem: Let construct matrix $$$g$$$ of size $$$(2n + 1) \times (n + 1)$$$ same way as matrix $$$b$$$. Given $$$g_{i, n}$$$ $$$(1 \le i \le 2n)$$$, please reconstruct $$$a$$$. How can you solve this problem?

1713F - Lost Array

First, we can see that $$$a_i$$$ contribute $$$\binom{(n - i) + (j - 1)}{j - 1}$$$ times to $$$b_{j, n}$$$, which can calculate similar to Pascal's Triangle. It's easy to see that the value that $$$a_i$$$ contribute to $$$b_{j, n}$$$ equal to $$$a_i$$$ when $$$\binom{(n - i) + (j - 1)}{j - 1}$$$ is odd, $$$0$$$ otherwise.

Let's solve the inverse problem: Given array $$$a$$$. Construct $$$b_{j, n}$$$ for all $$$j$$$. $$$(1 \le j \le n)$$$

By Lucas Theorem, $$$\binom{(n - i) + (j - 1)}{j - 1}$$$ is odd when $$$(n - i)\ AND\ (j - 1) = 0$$$

$$$\rightarrow (n - i)$$$ is a submask of $$$\sim(j - 1)$$$ (with $$$\sim a$$$ is inverse mask of $$$a$$$).

Let define $$$m = 2^k$$$ with smallest $$$m$$$ satisfy $$$m \ge n$$$. Set $$$a'_i = a_i$$$ and $$$b'_j = b_{\sim(j - 1)} = b_{(m - 1) - (j - 1)}$$$ then $$$b'$$$ is the Zeta transform of $$$a'$$$.

So we could apply Mobius transform in $$$b'$$$ to get $$$a'$$$. Since the operation is xor, mobius transform is as same as zeta transform. But unlike the inverse problem, there are some differences. We don't know the value of $$$b'_i$$$ for $$$i$$$ in $$$[0, m - n)$$$.

Let $$$c$$$ be the sum over supermasks array of $$$b'$$$ (with $$$i$$$ is supermasks of $$$j$$$ when $$$i\ AND\ j = j)$$$, then set $$$c_k = 0$$$ for $$$k$$$ in $$$[m - n, m)$$$. After that, do another sum over supermasks on $$$c$$$ to get original value of $$$b'$$$. Now we can find $$$a'$$$ from $$$b'$$$ and $$$a$$$ from $$$a'$$$.

Complexity: $$$O(nlog_2(n))$$$

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 1 << 19;

int n;
int a[N], b[N], ta[N], tb[N];
int c[N];

int m, lm, all1;

signed main(){
    cin >> n;
    ForE(i, 1, n){
        cin >> b[i];
    }

    m = 1 << __lg(n);
    if (m < n){
        m *= 2;
    }
    lm = __lg(m);
    all1 = m - 1;
    memset(ta, -1, sizeof(ta));
    memset(tb, -1, sizeof(tb));
    ForE(i, 1, n){
        tb[all1 ^ (i - 1)] = b[i];
        ta[n - i] = -2;
    }

    For(i, 0, m){
        c[all1 ^ i] = max(tb[i], 0);
    }
    For(bit, 0, lm){
        For(msk, 0, m){
            if (msk >> bit & 1){
                c[msk] ^= c[msk ^ (1 << bit)];
            }
        }
    }
    For(i, 0, m){
        if (tb[i] == -1){
            c[all1 ^ i] = 0;
        }
    }
    For(bit, 0, lm){
        For(msk, 0, m){
            if (msk >> bit & 1){
                c[msk] ^= c[msk ^ (1 << bit)];
            }
        }
    }
    For(i, 0, m){
        if (tb[i] == -1){
            tb[i] = c[all1 ^ i];
        }
    }

    For(i, 0, m){
        ta[i] = tb[i];
    }
    For(bit, 0, lm){
        For(msk, 0, m){
            if (msk >> bit & 1){
                ta[msk] ^= ta[msk ^ (1 << bit)];
            }
        }
    }
    ForE(i, 1, n){
        a[i] = ta[n - i];
    }
    ForE(i, 1, n){
        cout << a[i] << ' ';
    } cout << endl;
}

• Didn't solve
• Good problem
• Average problem
• Bad problem