USACO 2020 February Contest, Platinum Problem 2. Equilateral Triangles

USACO 2020 February Contest, Platinum Problem 2. Equilateral Triangles

Farmer John's pasture can be represented by a N×NN×N square grid (1N300)(1≤N≤300) consisting of positions (i,j)(i,j) for all 1i,jN1≤i,j≤N. For each square of the grid, the corresponding character in the input is equal to '*' if there exists a single cow at that position and '.' if there does not exist a cow at that position.

FJ believes that the beauty of his pasture is directly proportional to the number of triples of cows such that their positions are equidistant from each other. In other words, they form an equilateral triangle. Unfortunately, it was only quite recently that FJ realized that since all of his cows are located at integer coordinates, no beautiful triples can possibly exist if Euclidean distance is used! Thus, FJ has decided to switch to use "Manhattan" distance instead. Formally, the Manhattan distance between two positions (x0,y0)(x0,y0) and (x1,y1)(x1,y1) is equal to |x0x1|+|y0y1||x0−x1|+|y0−y1|.

Given the grid representing the positions of the cows, compute the number of equilateral triples.

 

SCORING:

There will be fourteen test cases aside from the sample, one for each of N{50,75,100,125,150,175,200,225,250,275,300,300,300,300}.N∈{50,75,100,125,150,175,200,225,250,275,300,300,300,300}.

 

INPUT FORMAT (file triangles.in):

The first line contains a single integer N.N.For each 1iN,1≤i≤N, line i+1i+1 of the input contains a string of length NN consisting solely of the characters '*' and '.'. The jjth character describes whether there exists a cow at position (i,j)(i,j) or not.

 

OUTPUT FORMAT (file triangles.out):

Output a single integer containing the answer. It can be shown that it fits into a signed 32-bit integer.

 

SAMPLE INPUT:

3
*..
.*.
*..

SAMPLE OUTPUT:

1

There are three cows, and they form an equilateral triple because the Manhattan distance between each pair of cows is equal to two.

 

Problem credits: Benjamin Qi

 

USACO 2020 February Contest, Platinum Problem 2. Equilateral Triangles 题解(翰林国际教育提供,仅供参考)

题解请注册登录查看

[/hide]

(Analysis by Benjamin Qi)

Note: Whenever I refer to a valid triangle below I mean one that is equilateral.

Here are some approaches with different time complexities.

O(N6)O(N6) (~1 test case): Go through all triples of squares and check whether they form a valid triangle.

O(N5)O(N5) (~3 test cases): Fix the lower-left-most square aa of the triangle. For each remaining square pp, place pp into a bucket labeled dist(a,p)dist(a,p). To check whether aa forms a valid triangle with two squares bb and cc in bucket ii just verify that dist(b,c)=i.dist(b,c)=i.

O(N4)O(N4) (~9 test cases). Consider the smallest rectangle with sides parallel to the coordinates axes that contains the triangle. At least one and at most two of the vertices of the triangle are also corners of this bounding rectangle.

Let the vertices of the triangle be a=(a0,a1),b=(b0,b1),c=(c0,c1).a=(a0,a1),b=(b0,b1),c=(c0,c1). First, consider a corner of the triangle which is also a corner of the rectangle. Without loss of generality, suppose that the corner is (a0,a1)(a0,a1) and a0min(b0,c0),a1min(b1,c1).a0≤min(b0,c0),a1≤min(b1,c1). Also suppose that dist(a,b)=dist(b,c)=dist(c,a)=rdist(a,b)=dist(b,c)=dist(c,a)=r (rr even). Then both bb and cc lie on the diagonal consisting of all (x,y)(x,y) satisfying x+y=a0+a1+rx+y=a0+a1+r. Furthermore, bc=±(r2,r2).b−c=±(r2,−r2). For a fixed aa and rr, we can count the number of pairs (b,c)(b,c) in O(N)O(N).

Regarding each of the three other possible orientations of the triangle (ex. a0max(b0,c0),a1max(b1,c1)a0≥max(b0,c0),a1≥max(b1,c1)), just keep rotating the original square by 90 degrees and running the solution. Make sure not to overcount the case where two vertices of the triangle are corners of the bounding rectangle!

O(N3):O(N3): Let's try to make the above solution faster. Again focus on the case a0min(b0,c0),a1min(b1,c1).a0≤min(b0,c0),a1≤min(b1,c1). For a fixed rr note that the pairs (b,c)(b,c) which could possibly make a triangle with a=(a0,a1)a=(a0,a1) are almost exactly the same as those which could make a triangle with a=(a0+1,a11)a′=(a0+1,a1−1), so we can transition between the two in O(1)O(1) time.

 

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

void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
 
int N;
bool G[300][300],GG[300][300];
long long ans;
 
void rot() { // rotate 90 degrees
	for (int i = 0; i < N; ++i) 
		for (int j = 0; j < N; ++j) 
			GG[N-1-j][i] = G[i][j];
	for (int i = 0; i < N; ++i) 
		for (int j = 0; j < N; ++j) 
			G[i][j] = GG[i][j];
}
void solve() { // corner in diagonal with sum a, other two vertices in diagonal with sum b
	for (int a = 0; a < 2*N-1; ++a) 
		for (int b = a+2; b < 2*N-1; b += 2) {
			int dif = (b-a)/2, st = max(0,a-(N-1)), en = min(a,N-1);
			int cur = 0;
			for (int i = st; i <= en; ++i) { 
				if (i == st) // consider (i,a-i) -> stuff in row b
					for (int j = max(i,b-(N-1)); j < min(i+dif,N-dif); ++j) 
						cur += G[j][b-j] && G[j+dif][b-j-dif];
				if (G[i][a-i]) ans += cur;
				if (i+2*dif < N && b-(i+dif) < N) 
					cur += G[i+dif][b-i-dif] && G[i+2*dif][b-i-2*dif];
				if (i+dif < N && b-i < N) 
					cur -= G[i][b-i] && G[i+dif][b-i-dif];
			}
		}
}
int main() {
	setIO("triangles"); 
	cin >> N;
	for (int i = 0; i < N; ++i) 
		for (int j = 0; j < N; ++j) {
			char c; cin >> c;
			G[i][j] = c == '*';
		}
	for (int i = 0; i < 4; ++i) solve(), rot(); 
	cout << ans << "\n";
}

As suggested by Dorijan Lendvaj, it is also possible to solve the problem in O(N4)O(N4) with bitset. Again, consider the case where a0min(b0,c0),a1min(b1,c1).a0≤min(b0,c0),a1≤min(b1,c1). Let (x,y)=(b0a0,b1a1)(x,y)=(b0−a0,b1−a1) and assume that b0<c0b0<c0xyx≤y, and x+yx+y is divisible by two. This means that

(c0,c1)=(a0,a1)+(x,y)+((x+y)/2,(x+y)/2).(c0,c1)=(a0,a1)+(x,y)+((x+y)/2,−(x+y)/2).

If we fix xxyy, and a0a0, then the number of a1a1 such that (a0,a1)(a0,a1)(b0,b1)(b0,b1), and (c0,c1)(c0,c1) all contain cows is equal to the number of bits set in the bitwise AND of three bitsets. This solution runs about as quickly as the one above.

 

#include "bits/stdc++.h"
 
using namespace std;
 
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
 
int N;
bool G[300][300],GG[300][300];
long long res = 0;

void rot() {
	for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) GG[N-1-j][i] = G[i][j];
	for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) G[i][j] = GG[i][j];
}

void solve() {
	bitset<300> mask[300];
	for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) 
		mask[i][j] = G[i][j];
	for (int i = 0; i < N; ++i)
		for (int x = 1; x < N; ++x) 
			for (int y = x; y < N; y += 2) {
				int x2 = x+(x+y)/2; if (i+x2 >= N) break;
				int y2 = (y-x)/2;
				res += (mask[i]&(mask[i+x]>>y)&(mask[i+x2]>>y2)).count();
			}
}

int main() {
	setIO("triangles"); 
	cin >> N;
	for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
		char c; cin >> c;
		G[i][j] = c == '*';
	}
	for (int i = 0; i < 4; ++i) { solve(); rot(); }
	cout << res << "\n";
}

[/hide]

翰林国际教育资讯二维码