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

C - Ringo's Favorite Numbers 2 Editorial by en_translator

$$A_i - A_j$$ is a multiple of $$200$$” if and only if “the remainder of $$A_i$$ divided by $$200$$ and that of $$A_j$$ are the same”.

So, the desired answer is equal to the number of pairs $$(i,j)$$ $$(1 \le i < j \le N)$$ (that is, the number of choices of two elements with the different position) such that remainder of $$A_i$$ divided by $$200$$ and that of $$A_j$$ are the same.

First, let us find how many elements are there in $$A_i$$ whose remainder by $$200$$ is $$k$$. In this problem, counting with a naive loop is sufficient, but a packet-sort like inspection is faster.
Assume that the sequence $$A_i$$ contains $$X$$ elements whose remainders by $$200$$ are $$k$$. Then, the number of combinations of two distinct elements from the sequence $$A$$ is $$\frac{X \times (X-1)}{2}$$. This is also true for $$X=0,1$$.
The problem can be solved by summing them up for every integer from $$0$$ through $$199$$, inclusive.

The total complexity is $$O(N)$$.

Sample code in C:

#include<stdio.h>

int main(){
int n,a;
long long b={0};
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
b[a[i]%200]++;
}
long long res=0;
for(int k=0;k<200;k++){
res+=(b[k]*(b[k]-1))/2;
}
printf("%lld\n",res);
return 0;
}

$$A_i - A_j$$ is a multiple of $$200$$” if and only if “the remainder of $$A_i$$ divided by $$200$$ and that of $$A_j$$ are the same”.

We will explain the reason.
If the remainders of some two elements $$A_i$$ and $$A_j$$ by $$200$$ are equal, the difference between these two elements are only due to their quotients divided by $$200$$. Moreover, their difference is always a multiple of $$200$$.
Conversely, if the remainders of some two elements $$A_i$$ and $$A_j$$ by $$200$$ are not equal, then $$A_i-A_j$$ is a multiple of $$200$$. This is because, no matter how many times we add or subtract $$200$$ to/from $$A_j$$, the remainder by $$200$$ does not change, so it will never be equal to $$A_i$$.

Appendix 2: About the number of combinations

Assume that the sequence $$A_i$$ contains $$X$$ elements whose remainders by $$200$$ are $$k$$. Then, the number of combinations of two distinct elements from the sequence $$A$$ is $$\frac{X \times (X-1)}{2}$$.

We will explain the reason.
Now, let us consider how many choices are there of two objects out of $$X$$ pairwise distinguishable objects.
We first choose the first object. There are $$X$$ choices. Here, no matter which object was chosen, there are $$X-1$$ choice of the second object.
After all, the number of combinations is $$X \times (X-1)$$. In this problem, you are asked to just choose two objects, and their order (there are two of them) is not distinguished. Therefore, the desired number of choices is $$\frac{X \times (X-1)}{2}$$.

posted:
last update: