Before the round starts
1713A - Traveling Salesman Problem
Hint 1
Hint 2
Tutorial
Solution
Feedback
Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback
Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution
Feedback
Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback
Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
#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}$$$?
Hint 1.1
$$$\rightarrow$$$ Calculate value that $$$a_i$$$ contribute to $$$b_{j, n}$$$.
Hint 1.2
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
Tutorial and solution for this problem will be updated later.