ADANTS - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Alei Reyes
Tester: Suchan Park
Editorialist: William Lin

DIFFICULTY:

Challenge

PROBLEM:

There are N points. In one operation, you can choose a convex polygon P from those points. Let M be the number of points of P. The sum of M over all operations should be \le 5\cdot 10^5. For each i from 1 to M-1, consider the segment from P_i to P_{i+1}. Move P_i to the nearest lattice point on the segment. Whenever two points coincide, they merge together and always move as one point afterwards. Find the minimum number of operations to merge all points.

Observations:

  • The coordinates are relatively small (at most 1024) compared to N (around 2^{17}).
  • This means each row / column should have an average of at least 100 points.

Simplest Valid Solution:

Since each row should have at least one point, for some point (x1, y1), there should exist some point (x2, y2) with x2=x1+1. Since the points are in adjacent rows, there can’t be any lattice points on the segment connecting them, so the two points can be merged in just one operation.

The full algorithm is to start from the bottom row and merge each point in one row with a point in the next row. After that, all points with be on the last row and we can finish by merging them from left to right (the coordinates are small so this doesn’t waste too many operations).

Code 
#include <bits/stdc++.h>
using namespace std;

#define ar array

int n;
vector<ar<int, 2>> v[1030];
vector<vector<int>> ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	//input
	cin >> n;
	for(int i=0, x, y; i<n; ++i) {
		cin >> x >> y;
		v[x].push_back({y, i});
	}

	int x=0;
	while(1) {
		if(v[x+1].empty())
			break;
		//merge all points on row i with a point on row i+1
		for(ar<int, 2> a : v[x])
			ans.push_back({a[1], v[x+1][0][1]});
		++x;
	}

	//all points on the last row, merge them
	sort(v[x].begin(), v[x].end());
	for(int i=0; i+1<v[x].size(); ++i) {
		//the first i points have been merged
		//now merge point i+1
		while(v[x][i][0]<v[x][i+1][0]) {
			ans.push_back({v[x][i][1], v[x][i+1][1]});
			//in one operation, point i becomes 1 closer
			++v[x][i][0];
		}
	}

	//output
	cout << ans.size() << "\n";
	for(vector<int> a : ans) {
		cout << a.size();
		for(int ai : a)
			cout << " " << ai+1;
		cout << "\n";
	}
}

Bigger polygons:

The previous solution is inefficient because we only merge two points for each operation. If we can somehow choose bigger polygons, we can merge more points for each operation, which will decrease the number of operations.

We can basically use the same solution as before, but we will try to add as many points in the next few rows to our polygon while making sure it is still convex.

Code 
#include <bits/stdc++.h>
using namespace std;

#define ar array

int n;
vector<ar<int, 2>> v[1030];
vector<vector<ar<int, 2>>> ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	//input
	cin >> n;
	for(int i=0, x, y; i<n; ++i) {
		cin >> x >> y;
		v[x].push_back({y, i});
	}

	int x=0;
	while(1) {
		if(v[x+1].empty())
			break;
		//merge all points on row i with a point on row i+1
		for(ar<int, 2> a : v[x]) {
			vector<ar<int, 2>> c={a, v[x+1][0]};
			int x2=x+1;
			while(v[x2].size()>1&&!v[x2+1].empty()) {
				//find some point on row x2+1
				bool ok=0;
				for(ar<int, 2> b : v[x2+1]) {
					//check cross product to check convexity
					if(c.back()[0]-c[c.size()-2][0]>b[0]-c.back()[0]) {
						c.push_back(b);
						ok=1;
						break;
					}
				}
				if(ok) {
					//point at row x2 is merged to x2+1
					v[x2].erase(find(v[x2].begin(), v[x2].end(), c[c.size()-2]));
				} else
					break;
				++x2;
			}
			ans.push_back(c);
		}
		++x;
	}

	//all points on the last row, merge them
	sort(v[x].begin(), v[x].end());
	for(int i=0; i+1<v[x].size(); ++i) {
		//the first i points have been merged
		//now merge point i+1
		while(v[x][i][0]<v[x][i+1][0]) {
			ans.push_back({v[x][i], v[x][i+1]});
			//in one operation, point i becomes 1 closer
			++v[x][i][0];
		}
	}

	//output
	cout << ans.size() << "\n";
	for(vector<ar<int, 2>> a : ans) {
		cout << a.size();
		for(ar<int, 2> ai : a)
			cout << " " << ai[1]+1;
		cout << "\n";
	}
}

Better polygon finder:

Finding next lattice point on a segment

Let the first point be (x1, y1) and the second point be (x2, y2). The vector from the first point to the second point is (vx, vy)=(x2-x1, y2-y1). If g=\gcd(vx, vy), the next lattice point on the segment will be (x1+\frac{vx}{g}, y1+\frac{vy}{g}).

It follows that if g=1 then there are no intermediate lattice points on the segment.

While there are still points left, we will take a random subset of at most 30 points (if we take too many then we will exceed the time limit). We will calculate the convex hull of the subset, but if we form a segment with an intermediate lattice point, then we will ignore the point. The goal of this is to make sure all points on the polygon of the convex hull can be merged into one point.

At some point when there are very few points left, it could be very hard to find any polygon. When that happens, merge two points at once until all remaining points have been merged.

Code 
#include <bits/stdc++.h>
using namespace std;

#define ar array

int n;
vector<ar<int, 3>> v;
vector<vector<ar<int, 3>>> ans;
vector<bool> del;

//distance squared
int ds(ar<int, 3> a, ar<int, 3> b) {
	return (a[0]-b[0])*(a[0]-b[0])+(a[1]-b[1])*(a[1]-b[1]);
}

//cross product
int cp(ar<int, 3> o, ar<int, 3> a, ar<int, 3> b) {
	return (a[0]-o[0])*(b[1]-o[1])-(a[1]-o[1])*(b[0]-o[0]);
}

//convex hull with graham's scan
vector<ar<int, 3>> ch(vector<ar<int, 3>> u) {
	sort(u.begin(), u.end());
	sort(u.begin()+1, u.end(), [&](const ar<int, 3> &i, const ar<int, 3> &j) {
		int cpv=cp(u[0], i, j);
		if(cpv>0)
			return false;
		if(cpv<0)
			return true;
		return ds(u[0], i)<ds(u[0], j);
	});
	vector<ar<int, 3>> ch;
	for(int i=0; i<u.size(); ++i) {
		while(ch.size()>1&&cp(ch[ch.size()-2], ch.back(), u[i])>=0)
			ch.pop_back();
		//make sure no intermediate lattice points
		if(ch.empty()||abs(__gcd(u[i][0]-ch.back()[0], u[i][1]-ch.back()[1]))==1)
			ch.push_back(u[i]);
	}
	if(ch.size()>2)
		while(ch.size()>1&&cp(ch[ch.size()-2], ch.back(), u[0])>=0)
			ch.pop_back();
	return ch;
}

//find the next point on a segment
ar<int, 3> next_on_segment(ar<int, 3> a, ar<int, 3> b) {
	ar<int, 2> v{b[0]-a[0], b[1]-a[1]};
	int g=abs(__gcd(v[0], v[1]));
	return {a[0]+v[0]/g, a[1]+v[1]/g, a[2]};
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	//input
	cin >> n;
	for(int i=0, x, y; i<n; ++i) {
		cin >> x >> y;
		v.push_back({x, y, i});
	}

	del=vector<bool>(n);
	int lastsize=n, halt=0;
	while(v.size()>1) {
		random_shuffle(v.begin(), v.end());
		for(int i=0; i<v.size(); i+=2000) {
			//take subset
			vector<ar<int, 3>> sub(v.begin()+i, v.begin()+i+min(2000, (int)v.size()-i));
			//find convex hull
			vector<ar<int, 3>> c=ch(sub);
			if(c.size()<2)
				continue;
			//delete points except for last
			for(int i=0; i+1<c.size(); ++i)
				del[c[i][2]]=1;
			ans.push_back(c);
		}
		//update v
		vector<ar<int, 3>> v2;
		for(ar<int, 3> a : v)
			if(!del[a[2]])
				v2.push_back(a);
		v=v2;
		if(lastsize>v.size()) {
			lastsize=v.size();
			halt=0;
		} else
			++halt;
		if(halt>9)
			break;
	}

	//merge two points at once
	//sort to avoid accidentally merging with other points
	sort(v.begin(), v.end());
	for(int i=0; i+1<v.size(); ++i) {
		//points 0 to i have been merged
		//now merge point i+1
		while(v[i][0]!=v[i+1][0]||v[i][1]!=v[i+1][1]) {
			v[i]=next_on_segment(v[i], v[i+1]);
			ans.push_back({v[i], v[i+1]});
		}
	}

	//output
	cout << ans.size() << "\n";
	for(vector<ar<int, 3>> a : ans) {
		cout << a.size();
		for(ar<int, 3> ai : a)
			cout << " " << ai[2]+1;
		cout << "\n";
	}
}

There’s a heuristic we can add. If the subset has points spread around the grid, then the convex hull will likely only contain the points near the outer part of the grid. We can group the points into subsets by their distance from the center of the grid.

Code

#include <bits/stdc++.h>
using namespace std;

#define ar array

int n;
vector<ar<int, 3>> v;
vector<vector<ar<int, 3>>> ans;
vector del;

//distance squared
int ds(ar<int, 3> a, ar<int, 3> b) {
return (a[0]-b[0])(a[0]-b[0])+(a[1]-b[1])(a[1]-b[1]);
}

//cross product
int cp(ar<int, 3> o, ar<int, 3> a, ar<int, 3> b) {
return (a[0]-o[0])(b[1]-o[1])-(a[1]-o[1])(b[0]-o[0]);
}

//convex hull with graham’s scan
vector<ar<int, 3>> ch(vector<ar<int, 3>> u) {
sort(u.begin(), u.end());
sort(u.begin()+1, u.end(), [&](const ar<int, 3> &i, const ar<int, 3> &j) {
int cpv=cp(u[0], i, j);
if(cpv>0)
return false;
if(cpv<0)
return true;
return ds(u[0], i)<ds(u[0], j);
});
vector<ar<int, 3>> ch;
for(int i=0; i<u.size(); ++i) {
while(ch.size()>1&&cp(ch[ch.size()-2], ch.back(), u[i])>=0)
ch.pop_back();
//make sure no intermediate lattice points
if(ch.empty()||abs(__gcd(u[i][0]-ch.back()[0], u[i][1]-ch.back()[1]))==1)
ch.push_back(u[i]);
}
if(ch.size()>2)
while(ch.size()>1&&cp(ch[ch.size()-2], ch.back(), u[0])>=0)
ch.pop_back();
return ch;
}

//find the next point on a segment
ar<int, 3> next_on_segment(ar<int, 3> a, ar<int, 3> b) {
ar<int, 2> v{b[0]-a[0], b[1]-a[1]};
int g=abs(__gcd(v[0], v[1]));
return {a[0]+v[0]/g, a[1]+v[1]/g, a[2]};
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);

//input
cin >> n;
for(int i=0, x, y; i<n; ++i) {
	cin >> x >> y;
	v.push_back({x, y, i});
}

del=vector<bool>(n);
int lastsize=n, halt=0;
while(v.size()>1) {
	if(halt<1) {
		sort(v.begin(), v.end(), [](const ar<int, 3> &i, const ar<int, 3> &j) {
			return (i[0]-512)*(i[0]-512)+(i[1]-512)*(i[1]-512)<(j[0]-512)*(j[0]-512)+(j[1]-512)*(j[1]-512);
		});
	} else
		random_shuffle(v.begin(), v.end());
	for(int i=0; i<v.size(); i+=2000) {
		//take subset
		vector<ar<int, 3>> sub(v.begin()+i, v.begin()+i+min(2000, (int)v.size()-i));
		//find convex hull
		vector<ar<int, 3>> c=ch(sub);
		if(c.size()<2)
			continue;
		//delete points except for last
		for(int i=0; i+1<c.size(); ++i)
			del[c[i][2]]=1;
		ans.push_back(c);
	}
	//update v
	vector<ar<int, 3>> v2;
	for(ar<int, 3> a : v)
		if(!del[a[2]])
			v2.push_back(a);
	v=v2;
	if(lastsize>v.size()) {
		lastsize=v.size();
		halt=0;
	} else
		++halt;
	if(halt>9)
		break;
}

//merge two points at once
//sort to avoid accidentally merging with other points
sort(v.begin(), v.end());
for(int i=0; i+1<v.size(); ++i) {
	//points 0 to i have been merged
	//now merge point i+1
	int j=i+1;
	//try to find next row
	while(j<v.size()&&v[j][0]==v[i][0])
		++j;
	if(j>=v.size())
		j=i+1;
	while(v[i][0]!=v[j][0]||v[i][1]!=v[j][1]) {
		v[i]=next_on_segment(v[i], v[j]);
		ans.push_back({v[i], v[j]});
	}
}

//output
cout << ans.size() << "\n";
for(vector<ar<int, 3>> a : ans) {
	cout << a.size();
	for(ar<int, 3> ai : a)
		cout << " " << ai[2]+1;
	cout << "\n";
}

}

Other solutions?

Note that in the solutions presented above, the segments from the polygons never contain lattice points which are not endpoints. This makes the code a lot easier as we don’t need to take care of the case when vertices on the polygon merge with points on the segments of the polygon. However, this also limits how efficient our solution can be, so if you take the time to write the code to account for polygons with segments with intermediate lattice points, the score should improve.

5 Likes