21 Days Training // Day 18

T0. good

If we directly enumerate m, n, p, i , the complexity of the algorithm will be O(n^4) .

Notice that we only need to find A_m+A_n+A_p=A_i .
So we can enumerate all m, n, p and record all A_m+A_n+A_p , then enumerate i .
If you use map or set to search, the complexity is O(n^3\log n) .

Optimize further, we can enumerate all m, n and record all A_m+A_n , then enumerate p, i .
If you use map or set to search, the complexity is O(n^2\log n) .

The maximum operation number will be about 6.2 \times 10^8 times, with hte risk of TLE.

In fact, it can get 40. If we use unordered_map, it can get 50.

Notice that for 70% cases, |A_i| \le 10^6 , |A_i+A_j| \le 2 \times 10^6 ,
so we can use a bucket to replace map .

Here are the test result (unit : sec.) :

Manual Test	map	unordered_map	bucket
1	2.65	0.8	0.05
2	0.67	0.77	0.05
3	14.57	4.99	0.26
4	31.4	13.01	RE

Test Generation Rule :

1. For test 1, 2, 3, N=5000 ; for test 4, N=4999 .
2. For test 1, A_i=i .
3. For test 2, A_i=2 \times ((i+1) \mod 2) – 1 (i.e. 1 and -1 appear alternatively) .
4. For test 3, 4, the content is in the pack below.
5. For test 3, |A_i| \le 10^6 (subtask 3, 70% cases, real case 5)
6. For test 4, |A_i| \le 10^9 (subtask 4, 100% cases, real case 8).

Test cases 3, 4

From the table, we can see that for most conditions, map has the worst performance, unordered_map better, and the bucket best.
However, the bucket can only be used when |A_i| \le 10^6 , or it will RE.

In fact, if we change the way of using the bucket, we can get 100. (hash)

Code 1 : unordered_map (50 pts.) :

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

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    freopen("good.in", "r", stdin);
    freopen("good.out", "w", stdout);
    int N;cin >> N;
    long long A[N];
    long long tmp;
    for (int i=0;i<N;i++) cin >> A[i];
    unordered_map<long long, long long> sum2;
    for (int i=0;i<N;i++) {
        for (int j=0;j<=i;j++) {
            if (sum2.find(A[i]+A[j])==sum2.end()) sum2[A[i]+A[j]] = i;
        }
    }
    long long ans=0;
    for (int i=0;i<N;i++) {
        for (int j=0;j<i;j++) {
            if (sum2.find(A[i]-A[j])!=sum2.end()&&sum2[A[i]-A[j]]<i) {
                ans++; break;
            }
        }
    }
    cout << ans;
    return 0;
}

Code 2 : bucket (70 pts.) :

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

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    freopen("good.in", "r", stdin);
    freopen("good.out", "w", stdout);
    int N;cin >> N;
    long long A[N];
    long long tmp;
    for (int i=0;i<N;i++) cin >> A[i];
    int exs[4000100];
    for (int i=0;i<4000100;i++) exs[i] = INT_MAX;
    for (int i=0;i<N;i++) {
        for (int j=0;j<=i;j++) {
            if (exs[A[i]+A[j]+2000000]==INT_MAX) exs[A[i]+A[j]+2000000]=i;
        }
    }
    long long ans=0;
    for (int i=0;i<N;i++) {
        for (int j=0;j<i;j++) {
            if (exs[A[i]-A[j]+2000000]<i) {
                ans++; break;
            }
        }
    }
    cout << ans;
    return 0;
}