Do we actually need to go off the axis?

How to avoid visiting an axis more than once?

1713A - Traveling Salesman Problem

We just need to walk along the axis to collect the boxes, moreover we only need to care about the furthest box on each axis, because other boxes can be collected while gathering it.

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.

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

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, is there multiple?

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

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

Lucas theorem

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

~~~~~

~~~~~