PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Sorting
PROBLEM:
There are N wells, the i-th at (X_i, Y_i).
Every second, channels extend outward in the four cardinal directions from each well.
Two wells are considered connected if their channels meet.
Find the first time at which all the wells are connected, either directly or indirectly.
EXPLANATION:
Suppose we had just two wells, at (X_1, Y_1) and (X_2, Y_2). Then, they’d have to be directly connected to each other in the end.
To decide when this will happen, we need to analyze some cases:
- If X_1 = X_2, then this will happen at time \text{ceil}\left(\frac{|Y_1 - Y_2|} 2\right), since their channels will essentially grow towards each other, and meet at the midpoint.
- Similarly, if Y_1 = Y_2, the time required is \text{ceil}\left(\frac{|X_1 - X_2|} 2\right).
- Finally, if X_1\neq X_2 and Y_1 \neq Y_2, their channels will meet at time \max(|X_1 - X_2|, |Y_1 - Y_2|), since the horizontal channel of one must meet the vertical channel of another.
When there are more wells, we can still apply the logic above to each pair of wells to figure out when they’ll be directly connected to each other.
Let t_{i, j} be the time at which i and j become directly connected.
We now have the following straightforward algorithm:
- Sort all the t_{i, j} values in ascending order, and process them in this order.
- Start with all the wells being their own components.
- When looking at t_{i, j}, merge the components of i and j if they’re different, since i and j are now directly connected.
- After a merge, if all wells are in the same component, this t_{i, j} is our answer.
This can be tracked by, for example, checking if the number of merges done equals N-1.
Generating the t_{i, j} values takes quadratic time, and sorting them takes \mathcal{O}(N^2 \log N) time.
Thereafter, the merging can really be done in any way: you can use a data structure like a DSU to do it quickly, or even do it naively in linear time since merges can only happen N-1 times in total anyway.
Alternately, observe that the described process is exactly what we get when running Kruskal’s algorithm on the weighted graph whose weights are the t_{i, j} values; and the result is the MST of this graph.
We’re technically looking for the minimum bottleneck spanning tree (MBST) of the graph, but an MST is also an MBST so any MST algorithm will work: in particular, Prim’s algorithm can be implemented to run in \mathcal{O}(N^2) time by performing each step in linear time.
This saves a \log N factor from the solution, if really necessary.
TIME COMPLEXITY:
\mathcal{O}(N^2 \log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
struct ufds{
vector <int> root, sz;
int n;
void init(int nn){
n = nn;
root.resize(n + 1);
sz.resize(n + 1, 1);
for (int i = 1; i <= n; i++) root[i] = i;
}
int find(int x){
if (root[x] == x) return x;
return root[x] = find(root[x]);
}
bool unite(int x, int y){
x = find(x); y = find(y);
if (x == y) return false;
if (sz[y] > sz[x]) swap(x, y);
sz[x] += sz[y];
root[y] = x;
return true;
}
};
void Solve()
{
int n; cin >> n;
vector <int> x(n), y(n);
for (int i = 0; i < n; i++){
cin >> x[i] >> y[i];
}
vector <array<int, 3>> a;
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
int t;
if (x[i] == x[j] || y[i] == y[j]){
t = (abs(x[i] - x[j] + y[i] - y[j]) + 1) / 2;
} else {
t = max(abs(x[i] - x[j]), abs(y[i] - y[j]));
}
a.push_back({t, i, j});
}
}
sort(a.begin(), a.end());
ufds uf; uf.init(n);
int comps = n;
if (n == 1){
cout << 0 << "\n";
return;
}
for (auto pi : a){
int t = pi[0];
int x = pi[1];
int y = pi[2];
if (uf.unite(x + 1, y + 1)){
comps--;
}
if (comps == 1){
cout << t << "\n";
return;
}
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...)
#endif
#ifndef LOCAL
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
#else
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
string X; cin >> X;
return X;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res; cin >> res;
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res; cin >> res;
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
}
void readEoln() {
}
void readEof() {
}
};
#endif
struct DSU{
int N, cmp;
vector<int> par, sz;
DSU(int N_) : N(N_ + 1), cmp(N_), par(N_ + 1), sz(N_ + 1, 1) {
iota(par.begin(), par.end(), 0);
}
int find(int node) {
if(par[node] == node) {
return node;
}
return par[node] = find(par[node]);
}
bool join(int u, int v) {
u = find(u);
v = find(v);
if(u == v) {
return false;
}
if(sz[u] > sz[v]) {
swap(u, v);
}
sz[v] += sz[u];
par[u] = v;
--cmp;
return true;
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
input_checker inp;
int T = inp.readInt(1, (int)1e3), NN = 0; inp.readEoln();
while(T-- > 0) {
int N = inp.readInt(1, (int)2e3); inp.readEoln();
vector<pair<int, int>> A(N);
for(auto &[x, y]: A) {
x = inp.readInt(1, (int)1e9); inp.readSpace();
y = inp.readInt(1, (int)1e9); inp.readEoln();
}
vector<pair<int, int>> ed; ed.reserve(N * (N - 1) / 2);
for(int i = 0 ; i < N ; ++i) {
for(int j = i + 1 ; j < N ; ++j) {
ed.emplace_back(i, j);
}
}
auto get_dist = [&](int i, int j) {
if(A[i].second == A[j].second) {
return (abs(A[i].first - A[j].first) + 1) / 2;
}
if(A[i].first == A[j].first) {
return (abs(A[i].second - A[j].second) + 1) / 2;
}
return max(abs(A[i].first - A[j].first), abs(A[i].second - A[j].second));
};
sort(ed.begin(), ed.end(), [&](auto &x, auto &y) {
return get_dist(x.first, x.second) < get_dist(y.first, y.second);
});
DSU ds(N);
int ans = 0;
for(auto &[x, y]: ed) {
if(ds.join(x, y)) {
ans = max(ans, get_dist(x, y));
}
}
cout << ans << '\n';
}
assert(NN <= (int)5e5);
inp.readEof();
return 0;
}
Editorialist's code (Python3)
for _ in range(int(input())):
n = int(input())
wells = []
for i in range(n):
x, y = map(int, input().split())
wells.append((x, y))
times = []
for i in range(n):
for j in range(i+1, n):
x1, y1 = wells[i]
x2, y2 = wells[j]
if x1 == x2 or y1 == y2: times.append(((abs(x1 - x2) + abs(y1 - y2) + 1) // 2, i, j))
else: times.append((max(abs(x1 - x2), abs(y1 - y2)), i, j))
times.sort()
comp = list(range(n))
merges = 0
for t, i, j in times:
if comp[i] == comp[j]: continue
x, y = comp[i], comp[j]
merges += 1
for ii in range(n):
if comp[ii] == x: comp[ii] = y
if merges == n-1:
print(t)
break
else:
print(0)
