ABC 200 help required in Ringo's fav no. 2

help
1

The link to the problem is here :

Being a beginner, I am not able to understand why taking modulo with 200 and adding to an array(as is given in the editorial) gives the correct answer…I mean…What is the thinking process involved here?
link to editorial is :

2

Adding it to an array will tell you the number of previous indexed such that their modulo with current sum is x(suppose). If the modulo of current element is x then all these number will give 0 after taking modulo with 200.
Hence calculating it for all the number , we can easily find the total pairs in one iteration.

Based on your implementation , you can use map { O(nlogn) } or an array { O(n) } for storing modulos.

3

I still did not understand :thinking: :no_mouth:

4

O( N + K ) approach

Code 
ll countPair(vector<ll> arr,ll n,ll k)
{
    ll cnt = 0;
    for(ll i = 0; i < n; i++) arr[i] = (arr[i] + k) % k;
 
    ll hash[k] = { 0 };
 
    for(ll i = 0; i < n; i++) hash[arr[i]]++;
 
    for(ll i = 0; i < k; i++) cnt += (hash[i] * (hash[i] - 1)) / 2;
 
    return cnt;
}

I think this code is available on GFG as well. Still u can check the implementation here. It’s better to use maps for hashing. In a hurry I used array itself.

https://codeforces.com/contest/1520/problem/D

This question also used the logic of P & C. If anyone wants to practice can look into it.

5

ok…But can you pls explain this part :

(hash[i] * (hash[i] - 1)) / 2;

6

Here’s my approach for the problem.
My solution is based on the observation that if (i, j) and (j, k) are both valid pairs, then it also implies that (i, k) is a valid pair. i.e. if (A[i]-A[j]) and (A[j]-A[k]) are multiples of 200, then (A[i]-A[k]) is also a multiple of 200. So, we can form chains in the sequence where each element will form a valid pair with every other element in the chain, and will not form a valid pair with any element outside the chain. This can be implemented in O(n) time.
Here’s My Code -

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){

int n;
cin >> n;

vector<ll> A(n);
for(int i = 0; i < n; i++){
    cin >> A[i];
}

vector<bool> visited(n, false);
ll cnt = 0;
int i = 0;
while(i<n){
    if(visited[i]){
        i++;
        continue;
    }
    int c = 1;
    int j = i+1;
    while(j<n){
        if(abs(A[i]-A[j])%200==0){
            cnt += c;
            c++;
            visited[j] = true;
        }
        j++;
    }
    i++;
}
cout << cnt << endl;



return 0;

}

7

Thank you everyone…I understood it now! :grin:

8

basic P & C (Permutation and Combination)