Cow $i$ beats cow $j$ on average when $h_is_j+p_ih_j+s_ip_j>h_js_i+p_jh_i+s_jp_i$. The problem asks us to compute the number of "good" triples $(i, j, k)$ such that cow $i$ beats cow $j$, cow $j$ beats cow $k$, and cow $k$ beats cow $i$. We define a "bad" triple as any triple that is not good.
Subtask 1 ($N\leq 10$)
It suffices to brute force all $N\choose 3$ triples of cows.
Subtask 2 ($N\leq 7500$, the sum of $N$ over all tests does not exceed $10^4$)
First, consider the case where there are no ties (i.e., for every pair of cows, one beats the other). Let's use complementary counting and count the number of bad triples. Consider a single triple $(i, j, k)$. In a good triple, each cow wins exactly once against the others in the triple. In a bad triple, this balance is broken; one cow must beat the other two (2 wins), one cow wins once, and one cow wins zero times.
If we let $\text{win}_i$ represent the number of cows among the other $N-1$ cows that cow $i$ beats, the number of pairs $(j, k)$ that form a bad triple with $i$ (where $i$ is the 2-win cow) is $\text{win}_i\choose 2$. The answer to the problem is ${N\choose 3} - \sum_{i=1}^N{\text{win}_i\choose 2}$.
For the full subtask solution, we need to handle ties. Note that if $x_i=0$ and $y_i=0$, that cow draws with all other cows, so we can ignore such points. When cows $i$ and $j$ tie, we have
This means that tying is transitive: if cow $i$ ties with cows $j$ and $k$, then cow $j$ ties with cow $k$. We can first merge cows that tie into components and then use knapsack-like DP to find the total count of valid non-tying triples. Afterward, we subtract $\sum_{i=1}^N{\text{win}_i\choose 2}$ from this count, just as in the no-tie case. Finally, note that triples $(i, j, k)$ where cow $i$ beats cows $j$ and $k$, but cows $j$ and $k$ tie with each other, were not included in the initial "no-tie" triple count but were subtracted in the second step. We must add all such triples back to the answer.
The time complexity is $O(N^2)$ to check the winner between each pair of cows.
Ben's code:
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> e;
void init(int N) {
e.assign(N, -1);
}
int get(int x) {
return e[x] < 0 ? x : e[x] = get(e[x]);
}
int size(int x) {
return -e[get(x)];
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y], e[y] = x;
return true;
}
};
bool beat(const array<int, 3>& a, const array<int, 3>& b) {
long long sum = 0;
for (int i = 0; i < 3; ++i) {
sum += (long long)a[i] * b[(i + 1) % 3];
sum -= (long long)b[i] * a[(i + 1) % 3];
}
return sum > 0;
}
long long c2(long long c) {
return c * (c - 1) / 2;
}
void solve() {
int N;
cin >> N;
vector<array<int, 3>> points;
for (int i = 0; i < N; ++i) {
array<int, 3> a;
cin >> a[0] >> a[1] >> a[2];
if (a[0] == a[1] && a[0] == a[2]) continue;
points.push_back(a);
}
N = points.size();
vector<vector<bool>> beats(N, vector<bool>(N));
for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j)
beats[i][j] = beat(points[i], points[j]);
DSU D;
D.init(N);
for (int i = 0; i < N; ++i) for (int j = i + 1; j < N; ++j)
if (!beats[i][j] && !beats[j][i]) D.unite(i, j);
array<long long, 4> ways_k = {1, 0, 0, 0};
for (int i = 0; i < N; ++i) if (D.get(i) == i)
for (int j = 2; j >= 0; --j) ways_k[j + 1] += ways_k[j] * D.size(i);
long long ans = ways_k[3];
for (int i = 0; i < N; ++i) {
vector<int> with_repr(N, 0);
int c = 0;
for (int j = 0; j < N; ++j) {
if (beats[i][j]) {
++c;
ans += with_repr[D.get(j)];
++with_repr[D.get(j)];
}
}
ans -= c2(c);
}
cout << ans << "\n";
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int TC;
cin >> TC;
while (TC--) solve();
return 0;
}
Subtask 3 ($N\leq 2\cdot 10^5$)
As stated above, cow $i$ beats cow $j$ on average when $h_is_j+p_ih_j+s_ip_j>h_js_i+p_jh_i+s_jp_i$. Equivalently, this can be rewritten as $h_i(s_j-p_j)+p_i(h_j-s_j)+s_i(p_j-h_j) > 0$. Note that increasing $h_j$, $p_j$, and $s_j$ by a fixed constant does not change the inequality. Similarly, we can show the same property for $h_i$, $p_i$, and $s_i$. Using this observation, the tuple $(h_i, p_i, s_i)$ can be reduced to $(h_i-s_i, p_i-s_i, 0)$. This reduction allows us to work in 2 dimensions.
Let $x_i=h_i-s_i$ and $y_i=p_i-s_i$. Now, cow $i$ beats cow $j$ on average when $x_iy_j-y_ix_j > 0$. Geometrically, this is equivalent to the cross product: $x_iy_j-y_ix_j > 0$ occurs when vector $\langle x_j, y_j \rangle$ is counter-clockwise relative to vector $\langle x_i, y_i \rangle$. That is, if $\theta_i$ is the angle of vector $\langle x_i, y_i \rangle$, then the condition is equivalent to $\theta_i < \theta_j < \theta_i + 180^{\circ}$.
We can sort the remaining vectors by angle. Now, a bad triple occurs when the three vectors lie within a $180^{\circ}$-degree range, and a good triple happens otherwise (i.e., the origin is strictly inside the triangle formed by the vectors). To get the final answer, it suffices to perform either computation.
To count the number of bad triples, we can optimize the Subtask 2 solution. We can compute all $\text{win}_i$ in linear time using a two-pointers approach to count the number of $j$ such that $\theta_i < \theta_j < \theta_i + 180^{\circ}$.
To count the number of good triples directly, let's consider a single cow $i$. The vector $\langle x_i, y_i \rangle$ splits the 2D plane into two half-planes. A good triple consists of $i$ and two other cows $j$ and $k$ such that the vectors span more than $180^{\circ}$ degrees. If we compute $\text{pos_over_half}_i$, representing the index of the number of $p$ such that $\theta_p < \theta_i + 180^{\circ}$, then for a fixed pair $(i, j)$ where $i$ beats $j$, the number of valid $k$'s is $\text{pos_over_half}_j - \text{pos_over_half}_i$. To compute the sum over all $j$, we can apply a layer of prefix sums.
Both implementations need to handle edge cases where cows tie. The time complexity is $O(N\log N)$ due to sorting.
Ben's code (complementary counting):
#include <bits/stdc++.h>
using namespace std;
struct Point {
long long x, y;
};
long long cross(Point a, Point b) {
return a.x * b.y - a.y * b.x;
}
int half(Point p) {
return p.y > 0 || (p.y == 0 && p.x > 0) ? 1 : -1;
}
bool angleCmp(Point a, Point b) {
int h1 = half(a), h2 = half(b);
return h1 == h2 ? cross(a, b) > 0 : h1 < h2;
}
long long c3(long long n) {
return n * (n - 1) * (n - 2) / 6;
}
long long c2(long long n) {
return n * (n - 1) / 2;
}
void solve() {
int N;
cin >> N;
vector<Point> points;
for (int i = 0; i < N; ++i) {
int r, p, s;
cin >> r >> p >> s;
p -= s, r -= s;
if (p || r) points.push_back({(long long)p, (long long)r});
}
sort(points.begin(), points.end(), angleCmp);
vector<pair<Point, long long>> points2;
for (const auto& t : points) {
if (!points2.empty() && !angleCmp(points2.back().first, t) && !angleCmp(t, points2.back().first)) {
points2.back().second++;
} else {
points2.push_back({t, 1});
}
}
long long ans = c3(points.size());
int r = -1;
long long sum = 0;
int M = points2.size();
for (int l = 0; l < M; ++l) {
if (r < l) {
r = l;
} else {
sum -= points2[l].second;
}
while (cross(points2[l].first, points2[(r + 1) % M].first) > 0) {
++r;
sum += points2[r % M].second;
}
ans -= (c3(sum + points2[l].second) - c3(sum));
if ((r + 1) % M != l && cross(points2[l].first, points2[(r + 1) % M].first) == 0) {
ans -= c2(points2[l].second) * points2[(r + 1) % M].second;
ans -= points2[l].second * sum * points2[(r + 1) % M].second;
}
}
cout << ans << "\n";
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int TC;
cin >> TC;
while (TC--) solve();
return 0;
}
My code (direct counting):
#include <bits/stdc++.h>
using namespace std;
struct point {
int x, y;
bool half() { return y < 0 || (y == 0 && x < 0); }
};
long long cross(point a, point b) {
return 1ll * a.x * b.y - 1ll * a.y * b.x;
}
bool equals(point a, point b) {
return a.half() == b.half() && !cross(a, b);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<point> v;
for (int i = 0; i < n; i++) {
int x, y, z;
cin >> x >> y >> z;
x -= z, y -= z;
if (x || y) v.push_back({x, y});
}
n = v.size();
sort(v.begin(), v.end(), [&](point a, point b) {
if (a.half() != b.half()) return a.half() < b.half();
return cross(a, b) > 0;
});
vector<int> nxt_dif(n * 2);
for (int i = n * 2 - 1; i >= 0; i--)
nxt_dif[i] = i < n * 2 - 1 && equals(v[i % n], v[(i + 1) % n])
? nxt_dif[i + 1]
: i + 1;
vector<int> pos_over_half(n * 2);
for (int i = 0, j = 0; i < n * 2; i++) {
j = min(i + n, max(j, nxt_dif[i]));
while (j < i + n && cross(v[i % n], v[j % n]) >= 0) j++;
pos_over_half[i] = j;
}
vector<int> pos_bad(n * 2);
for (int i = 0, j = 0; i < n * 2; i++) {
j = min(i + n, max(j, nxt_dif[i]));
while (cross(v[i % n], v[j % n]) > 0) j++;
pos_bad[i] = j;
}
vector<long long> sum_pos_bad(n * 2 + 1);
for (int i = 0; i < n * 2; i++)
sum_pos_bad[i + 1] = sum_pos_bad[i] + pos_bad[i];
long long ans = 0;
for (int i = 0, j = 0; i < n; i++) {
j = max(j, nxt_dif[i]);
while (j < pos_bad[i] && pos_bad[j] < pos_over_half[i]) j++;
if (j < pos_bad[i]) {
ans += sum_pos_bad[pos_bad[i]] - sum_pos_bad[j];
ans -= 1ll * pos_over_half[i] * (pos_bad[i] - j);
}
}
assert(ans % 3 == 0);
ans /= 3;
cout << ans << '\n';
}
}