Home » 国际竞赛 » Details

USACO 2020 February Contest, Platinum Problem 2. Equilateral Triangles

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午2:47

USACO 2020 February Contest, Platinum Problem 2. Equilateral Triangles

Farmer John's pasture can be represented by a $N \times N$ square grid $(1 \leq N \leq 300)$ consisting of positions $(i, j)$ for all $1 \leq i, j \leq 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 $(x_{0}, y_{0})$ and $(x_{1}, y_{1})$ is equal to $| x_{0} - x_{1} | + | y_{0} - y_{1} |$ .

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 \in {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 .$ For each $1 \leq i \leq N,$ line $i + 1$ of the input contains a string of length $N$ consisting solely of the characters '*' and '.'. The $j$ th character describes whether there exists a cow at position $(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:

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 (N^{6})$ (~1 test case): Go through all triples of squares and check whether they form a valid triangle.

$O (N^{5})$ (~3 test cases): Fix the lower-left-most square $a$ of the triangle. For each remaining square $p$ , place $p$ into a bucket labeled $d i s t (a, p)$ . To check whether $a$ forms a valid triangle with two squares $b$ and $c$ in bucket $i$ just verify that $d i s t (b, c) = i .$

$O (N^{4})$ (~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 = (a_{0}, a_{1}), b = (b_{0}, b_{1}), c = (c_{0}, c_{1}) .$ First, consider a corner of the triangle which is also a corner of the rectangle. Without loss of generality, suppose that the corner is $(a_{0}, a_{1})$ and $a_{0} \leq min (b_{0}, c_{0}), a_{1} \leq min (b_{1}, c_{1}) .$ Also suppose that $d i s t (a, b) = d i s t (b, c) = d i s t (c, a) = r$ ( $r$ even). Then both $b$ and $c$ lie on the diagonal consisting of all $(x, y)$ satisfying $x + y = a_{0} + a_{1} + r$ . Furthermore, $b - c = \pm (\frac{r}{2}, - \frac{r}{2}) .$ For a fixed $a$ and $r$ , we can count the number of pairs $(b, c)$ in $O (N)$ .

Regarding each of the three other possible orientations of the triangle (ex. $a_{0} \geq max (b_{0}, c_{0}), a_{1} \geq max (b_{1}, c_{1})$ ), 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 (N^{3}) :$ Let's try to make the above solution faster. Again focus on the case $a_{0} \leq min (b_{0}, c_{0}), a_{1} \leq min (b_{1}, c_{1}) .$ For a fixed $r$ note that the pairs $(b, c)$ which could possibly make a triangle with $a = (a_{0}, a_{1})$ are almost exactly the same as those which could make a triangle with $a^{'} = (a_{0} + 1, a_{1} - 1)$ , so we can transition between the two in $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 (N^{4})$ with bitset. Again, consider the case where $a_{0} \leq min (b_{0}, c_{0}), a_{1} \leq min (b_{1}, c_{1}) .$ Let $(x, y) = (b_{0} - a_{0}, b_{1} - a_{1})$ and assume that $b_{0} < c_{0}$ , $x \leq y$ , and $x + y$ is divisible by two. This means that

(c 0, c 1) = (a 0, a 1) + (x, y) + ((x + y) / 2, - (x + y) / 2) .

If we fix $x$ , $y$ , and $a_{0}$ , then the number of $a_{1}$ such that $(a_{0}, a_{1})$ , $(b_{0}, b_{1})$ , and $(c_{0}, c_{1})$ 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]