Ordered Additive Triples
National Olympiad — National round (2021 season)
Submission name: triplets.cpp
Problem summary
Given N distinct positive integers, count ordered triples of distinct elements (x,y,z) satisfying x+y=z. Both (x,y,z) and (y,x,z) count.
Input
N followed by N distinct positive values.
Output
The number of ordered qualifying triples.
Constraints
2 < N < 20,000; values ≤ 50,000.
Worked example
An independently prepared example for this explanation.
Input
5 7 3 4 5 8
Output
4
Solution analysis
- Use a membership array for the input values. Enumerate each unordered pair of different input positions once and check whether their sum is present.
- Because all values are positive, a sum x+y is larger than either summand, so the third element is automatically different from both. Add 2 for each successful unordered pair to account for the two summand orders.
- The sample contains 3+4=7 and 3+5=8. Each contributes two ordered triples, giving 4. The potential equality 4+4=8 contributes nothing because only one 4 exists and elements must be distinct.
Why it works
Every valid triple has a unique unordered pair of summands, which the nested loops visit once. Membership detects its third element exactly. Each such pair yields exactly the two allowed orders, and positivity guarantees three distinct elements.
Watch out. Do not allow the same input element twice. Count both summand orders, but do not multiply by six: the sum occupies the third position.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> values(n);
vector<bool> present(50001, false);
for (int& value : values) {
cin >> value;
present[value] = true;
}
long long answer = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int sum = values[i] + values[j];
if (sum <= 50000 && present[sum]) {
// Swapping the summands produces a second ordered triple.
answer += 2;
}
}
}
cout << answer << '\n';
}