Contest Duration: - (local time) (100 minutes) Back to Home

## C - Min Max Pair Editorial by en_translator

The conditions given in the Problem Statement is equivalent to that one of the following two holds:

• $$a_i = i$$ and $$a_j = j$$
• $$a_i = j$$ and $$a_j = i$$

The number of pairs satisfying the former is $$\frac{n(n - 1)}{2}$$, where $$n$$ is the number of $$k$$’s such that $$a_k = k$$.

The number of pairs satisfying the latter can be counted by inspecting each $$i$$, because once $$i$$ is fixed $$j$$ is uniquely determined since $$a_i \neq i$$.

Therefore, the problem has been solved in a total of $$O (N)$$ time.

Sample code (C++)

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

int main() {
int n;
cin >> n;
vector<int> a(n);
int same = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
a[i] -= 1;
if (a[i] == i) {
same += 1;
}
}
long long ans = (long long)same * (same - 1) / 2;
for (int i = 0; i < n; ++i) {
if (a[i] > i and a[a[i]] == i) {
ans += 1;
}
}
cout << ans << '\n';
return 0;
}


Sample code (Python)

n = int(input())
a = list(map(int, input().split()))

for i in range(n):
a[i] -= 1

same = 0
for (i, x) in enumerate(a):
if i == x:
same += 1

ans = same * (same - 1) // 2
for (i, j) in enumerate(a):
if i < j and a[j] == i:
ans += 1

print(ans)


posted:
last update: