...

Do we actually need to go off the axis?

How to avoid visiting an axis more than once?

1713A - Traveling Salesman Problem

To collect the furthest boxes on $$$Ox+$$$, we need to go in the following order: $$$(0, 0), (x_{max}, 0), (0, 0)$$$. Surprisingly, every other boxes on the $$$Ox+$$$ axis can be collected on the way. So the minimum number of moves required is $$$2 \cdot (|x_{max}|)$$$. The same strategy can also be applied on $$$Ox-$$$, $$$Oy+$$$ and $$$Oy-$$$. Just be careful when there is at least one axis that does not contain any boxes.

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()

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

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

Consider $$$a$$$ has $$$3$$$ elements. What if $$$a_1 \geq a_2 \leq a_3$$$?

1713A - Traveling Salesman Problem

Consider $$$a$$$ has 3 elements, there are two cases:

• $$$a_1 \geq a_2 \leq a_3: f(a) = a_1 + a_3 - a_2$$$, a.k.a the sum of two larger elements, substracting to the smallest one.

• Otherwise: $$$f(a) = max(a_i)$$$.

It can be showed that $$$f(a)$$$ on the second case is always smaller than the first one. Now we have the conclusion: When some elements $$$a_i$$$ is a local minimum, we will need more operations than usual.

Now we just have to find if there is any local minimum or not. Be careful of the case that several local minimums standing next to each other.

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

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

const int N = 1e5 + 5;

int n, a[N];

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

		bool ok = true;
		int p = max_element(a, a + n) - a;

		for (int i = 1; i <= p; i++) {
			if (a[i-1] > a[i]) {
				ok = false;
			}
		}

		for (int i = p+1; i < n; i++) {
			if (a[i-1] < a[i]) {
				ok = false;
			}
		}

		cout << (ok ? "YES\n" : "NO\n");
	}	
}

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]$$$.

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$$$.

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';
	}
}

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();
}

This is not a greedy 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 possibilities it can happen?

1713A - 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 to perform $$$1$$$ operation with $$$k = x$$$ or $$$k = y$$$. Notice that if we use both of the operations, these two cell won't be swapped.

So with have our constructive algorithm. Suppose we have traversed to the cell $$$(x, y)$$$. If $$$x \ge y$$$, ignore it. If $$$x < y$$$ then we try to make the current cell equal to $$$min(A_{x, y}, A_{y, x})$$$ by deciding to swap or not to swap the cells. If either $$$k = x$$$ or $$$k = y$$$ is performed, then $$$(x, y)$$$ will be swapped with $$$(y, x)$$$. Otherwise, if $$$k = x$$$ and $$$k = y$$$ are both performed or not performed, then the positions of $$$(x, y)$$$ and $$$(y, x)$$$ will not change.

But how can we determine if our algorithm can be done smoothly or not? Well, let's do a simple DSU. Let's call $$$2$$$ nodes $$$u$$$ and $$$v$$$ are in the same component if $$$2$$$ operations $$$k = u$$$ and $$$k = v$$$ should be both performed or not performed.

#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++) {
            for (int j = 1; j <= n; j++) {
                int x = getPar(i) > 0;
                int y = getPar(j) > 0;
                if (x + y != 1) {
                    cout << a[i][j] << ' ';
                } else {
                    cout << a[j][i] << ' ';
                }
            }
            cout << '\n';
        }
    }
}

• 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

Set $$$b'_{j - 1} = b_{j, n}$$$. First, we can see that $$$a_i$$$ contribute $$$\binom{(n - i) + (j - 1)}{j - 1}$$$ times to $$$b'_j$$$, which can calculate similar to Pascal's Triangle. It's easy to see that the value that $$$a_i$$$ contribute to $$$b'_j$$$ 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$$$ 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$$$ or $$$ \sim(n - i)\ AND\ (j - 1) = (j - 1)$$$ (with $$$\sim a$$$ is inverse mask of $$$a$$$).

Let define $$$m = 2^k$$$ with smallest $$$m$$$ satisfy $$$m \ge n$$$. So condition $$$\sim (n - i)\ AND\ (j - 1) = \sim (n - i)$$$ can be rephrase into $$$((m - 1) - (n - i))\ AND\ (j - 1) = (j - 1)$$$. Set $$$a'_{(m - 1) - (n - i)} = a_i$$$, 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 $$$[n, m)$$$.

...

~~~~~

~~~~~