1713A - Traveling Salesman Problem
Idea: thanhchauns2
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()
Idea: DeMen100ns
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 the numbers from $$$(h - k)$$$ to $$$k$$$ in the following order:
The first number is the position, the second number is the number in that position. Using this method we can recursively reduce $$$k$$$ to $$$h - k - 1$$$, 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';
}
}
Idea: thanhchauns2
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();
}
Idea: DeMen100ns
- Is there any case that the answer doesn't exist?
- If exist, are there multiple?
No for both questions.
- How many times does $$$alpha_i$$$ contribute to $$$beta_{j, n}$$$?
$$$\rightarrow$$$ Calculate value that $$$alpha_i$$$ contribute to $$$beta_{j, n}$$$.
$$$alpha_i$$$ when $$$\binom{(n - i) + (k - 1)}{k - 1}$$$ is odd, $$$0$$$ otherwise.
Consider the inverse problem: Given array $$$alpha$$$. Construct $$$b_{j, n}$$$ for all $$$j$$$. How can you solve this problem?
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) = ~(n - i)$$$ (with $$$~a$$$ is inverse mask of $$$a$$$). So you can easily apply fast zeta transform (DP SOS) to solve this.
Let define $$$m = 2^k$$$ with smallest $$$m$$$ satisfy $$$m \ge n$$$.
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, let's calculate number of times of $$$alpha_i$$$ contribute to $$$beta_{j, n}$$$.
...First, we have $$$\binom{(n - i) + (k - 1)}{k - 1}$$$ is numbẻtimes of $$$alpha_i$$$ contribute to $$$beta_{j, n}$$$
~~~~~
~~~~~