PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Alei Reyes
Tester: Radoslav Dimitrov
Editorialist: William Lin
DIFFICULTY:
PROBLEM:
There are 10^5 points on a 720720 by 720720 grid. You can split the grid into at most 1024 congruent rectangular pieces with integer side lengths. Then you can perform at most 1024 operations, each of one of two types:
- Shift a row to the right.
- Shift a column upwards.
Minimize the area of the final convex hull.
Simplest Valid Solution (787th Div-2, 260th Div-1):
The simplest valid solution was extremely simple for this problem. We can perform 0 operations and split the grid into 1 row and 1 column. You can also submit the code as a TEXT file!
Code
1 1 0
Random Shifts
There are only 3 test cases, so if you submit a bunch of random answers, some will score higher than others.
Checking your answer
For some other solutions, you need to be able to check how good a given solution is. For that, we can use any standard convex hull algorithm. Once we find the convex hull, we can use the Shoelace formula to find the area.
Observations
- There are 10^5 points total, which means that each rectangle has around 100 points on average. In other words, each rectangle should have several points.
- We can find the convex hull of each rectangle first to remove unnecessary points and improve runtime.
- Since each rectangle has at least one point, to find the convex hull of a given arrangement, we only need to consider rectangles on the border of the grid.
- For the rows in the middle of the grid (similarly for columns as well), only the leftmost and rightmost point in the row will matter the most, so we can approximate a given shift of the row by taking the difference of x coordinate of the rightmost point and the leftmost point.
1008 columns (12th Div-2, 27th Div-1)
Let’s split the grid into 1008 columns. Since shifting columns doesn’t do anything, we can only shift the rows. There are only 1008 possible shifts, so we can test all of them.
Note that using convex hull directly might be a bit slow, so to approximate the convex hull, we should only use all points in the first and last column and the top and bottom 3 points in the middle columns.
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
//number of rows, height of rectangle
const int M=1008, H2=720720/M;
int w, h, r;
vector<ar<ll, 2>> v[M];
//cross product
ll cp(ar<ll, 2> o, ar<ll, 2> a, ar<ll, 2> b) {
return (a[0]-o[0])*(b[1]-o[1])-(a[1]-o[1])*(b[0]-o[0]);
}
//convex hull with andrew's monotone chain
ll ch(vector<ar<ll, 2>> u) {
sort(u.begin(), u.end());
vector<ar<ll, 2>> ch, ch2;
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();
ch.push_back(u[i]);
}
ch.pop_back();
for(int i=u.size()-1; ~i; --i) {
while(ch2.size()>1&&cp(ch2[ch2.size()-2], ch2.back(), u[i])>0)
ch2.pop_back();
ch2.push_back(u[i]);
}
ch2.pop_back();
ch.insert(ch.end(), ch2.begin(), ch2.end());
//shoelace formula
ll area=0;
int s=ch.size();
for(int i=0; i<s; ++i)
area+=ch[(i+1)%s][0]*ch[i][1]-ch[i][0]*ch[(i+1)%s][1];
return area;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//input
cin >> w >> h >> r;
for(int i=0, x, y; i<r; ++i) {
cin >> x >> y;
//store relative y coord
v[y/H2].push_back({x, y%H2});
}
//sort points within rows
for(int i=0; i<M; ++i)
sort(v[i].begin(), v[i].end());
//test each shift
ar<ll, 2> ans{(ll)1e18};
for(int i=0; i<M; ++i) {
//bottom row will be i
//create points to calculate area
vector<ar<ll, 2>> u;
for(int j=i; j<i+M; ++j) {
//take left l, right r
int l, r;
if(j==i||j==i+M-1) {
//first or last row
l=v[j%M].size();
r=0;
} else {
//middle row
l=r=3;
}
vector<ar<ll, 2>> w;
for(int k=0; k<l; ++k)
w.push_back(v[j%M][k]);
for(int k=0; k<r; ++k)
w.push_back(v[j%M][v[j%M].size()-1-k]);
//convert from relative y coord to abs and add to u
for(ar<ll, 2> a : w)
u.push_back({a[0], a[1]+j*H2});
}
ans=min(ans, ar<ll, 2>{ch(u), M-i});
}
//output
cout << "1 " << M << " " << ans[1] << "\n";
for(int i=0; i<ans[1]; ++i)
cout << "2 1\n";
}
Best 4 Corners
This is from @carre’s comment here.
The intuition is that the most empty space comes from the 4 corners of the grid, so we should try to find rectangles that fit there well. To find the best rectangle for the bottom-left corner of the grid, for example, we should, for each rectangle, add points to all corners of the rectangle except for the bottom-left corner. Then, we choose the rectangle with the convex hull of the smallest area.
After we have found the 4 rectangles that we want, we need to put them in the corners of the grid.
Best Bottom Sides
This is a variation of the previous solution. We find the N rectangles with the most space on the bottom and move them to the bottom side of the grid.
Randomization
Pretty much all top solutions have some form of randomization. Just test a random shift and if it makes the answer better, use it. Do this until the 5s time limit is almost exceeded.
