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

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

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

• How many times does $$$alpha_i$$$ contribute to $$$beta_{j, n}$$$?

$$$\rightarrow$$$ Calculate value that $$$alpha_i$$$ contribute to $$$beta_{j, n}$$$.

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

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

1713F - Lost Array

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

Let's solve the inverse problem: Given array $$$alpha$$$. Construct $$$b_{j, n}$$$ for all $$$j$$$.

By Lucas Theorem, $$$\binom{(n - i) + (k - 1)}{k - 1}$$$ is odd when $$$(n - i) AND (k - 1) = 0$$$ or $$$~(n - i) AND (k - 1) = (k - 1)$$$ (with $$$~a$$$ is inverse mask of $$$a$$$).

Let define $$$m = 2^k$$$ with smallest $$$m$$$ satisfy $$$m \ge n$$$. So condition $$$~(n - i) AND (k - 1) = ~(n - i)$$$ can be rephrase into $$$((m - 1) - (n - 1)) AND (k - 1) = (k - 1)$$$. So you can easily apply fast zeta transform (DP SOS) to solve this.

~~~~~

~~~~~