See my answer here.
As @betlista mentioned, since in this problem the numbers are up to 1000 you can use array instead of map in my solution and get O(N + maxC)
solution.
But it may appear that there are many tests with small N
in one test file. Say 100000 tests with N up to 5. Then this new solution may get TLE too since we always should iterate over array of size 1000. If I would be the author of this problem I would definitely create such test file
One way to avoid this is to use O(N^2)
brute-force for very small N, say N smaller that 45. For array of size 45 we have approximately 1000 pairs so brute-force will have the same time as counting solution. But then we can create a test file where all N are near 45 and T=10000 or higher and this new solution can also get TLE.
To avoid TLE for any evil possible tests we need another hacky array mark[1000]
that is initialized by zeros before reading tests. When we handle t-th test (t=1,2,…,T) mark[Ci] == t
if and only if Ci
appears in array C[]
of the current test. So we shouldn’t initialize it by zeros again. We also shouldn’t initialize array cnt[1000]
. The value cnt[Ci]
will be actual only if mark[Ci] == t
. Otherwise it may contains some garbage from the previous tests. Finally to make efficient loop for calculating the answer we should save all different values that we met during reading in some array.
So during reading of our array if we read number Ci
for which mark[Ci] < t
then it means that we did not meet this number in the array before. So we should assign mark[Ci] = t
, assign cnt[Ci] = 0
and add it to the list of unique values. And as in the previous solution we of course should do cnt[Ci]++
for each read Ci
. So the C++ code for this part may look as follows:
int mark[1000] = {0};
int cnt[1000] = {0};
int lst[1000];
scanf("%d", &T);
for (int t = 0; t < T; ++t) {
int X, N;
scanf("%d, %d", &X, &N);
int len = 0;
for (int i = 0; i < N; ++i) {
int Ci;
scanf("%d", &Ci);
if (mark[Ci] < t) {
cnt[Ci] = 0;
mark[Ci] = t;
list[len++] = Ci;
}
cnt[Ci]++;
}
//now lst contains all different values among C[i]
// compute the answer. see below
}
Loop for computing the answer also requires some careful consideration. Now we have list lst[1000]
that contains len
elements that are all unique values among our array. We iterate by this list and for the current value val
if val == X-val
than add cnt[val] * (cnt[val]-1) / 2
as described in my previous post. Otherwise in order to not count the same pair twice val should be greater than X-val
and mark[X-val]
should be equal to t
. Otherwise cnt[X-val]
can be some garbage value from the previous tests. So the code looks as follows:
typedef long long LL;
LL ans = 0;
for (int i = 0; i < len; ++i) {
int val = lst[i];
if(val == X - val) {
ans += LL(cnt[val]) * (cnt[val] - 1) / 2;
} else if(X - val < val && mark[X - val] == t) {
ans += LL(cnt[val]) * cnt[X - val];
}
}
printf("%lld\n", ans);
Alternatively you could check condition X-val > val
but then it may appear that X-val >= 1000
so next look up at mark[X-val]
will be incorrect in this case. So you should either make mark
of size 2001
or to save memory check condition X-val < 1000. In any case the way described above is better.
This solution has complexity O(N + min(N,maxC)) = O(N)
.