RAISINS - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Alei Reyes
Tester: Radoslav Dimitrov
Editorialist: William Lin

DIFFICULTY:

Challenge

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.

9 Likes

Thank you very much for this editorial. It was most wanted :slightly_smiling_face:
What about the shortest solution. Like printing output using TEXT. that was a bug, right?

1 Like

What do you mean, what bug?

No it wasn’t a bug ,read the editorial carefully he has mentioned it

2 Likes

What about 0 point for this problem? In practise problem it also look like this.
Capture

1 Like

The admin mentioned that they were changing tests.

My guess is that they removed all tests at some point, so when that happened there were no tests and the sum of any solution will be 0.

2 Likes

Thanks for uploading the Editorial to this problem as well @tmwilliamlin :slight_smile:

1 Like

Is 1008 1008 0 a valid answer as both width and height would be divisible by 1008?