CHKDST - Editorial

array
chkdst
editorial
flfi2016
implementation
medium
medium-hard

#1

PROBLEM LINK :

contest

practice

Author : Vibhor Gupta

Tester : Vibhor Gupta

Editorialist : Vibhor Gupta

DIFFICULTY :

Medium-Hard

PREREQUISITES :

Arrays, Euclid’s Distance

PROBLEM :

Rahul has been given a new task.

He has been given N points on the x-axis, X1,X2,…,XN.

Now he is being asked Q queries. Each query gives him his position on the x-axis X, and asks him the sum of distances from his position and the N points.

As the sum can be quite large, he has been told to print the answer modulo 7630367.

He has written a program to calculate every query, but it seems to be giving him vague answers.

Flawed Code :

#include

#define ll long long

using namespace std;

int main(){

int n,x,q;

cin>>n>>q;

int a[n+1],b[n+1],mod=7630367;

for(int i=0;i!=n;i++){

cin>>x;

a[x]++;b[x]++;}

ll upd=0;

for(int i=0;i!=n+1;i++){

upd=a*%mod;a*=(a[i-1]+upd)%mod;}

upd=0;

for(int i=n;i>=0;i–){

upd=b*%mod;b*=(b[i+1]+upd)%mod;}

while(q–){cin>>x;printf("%lld",(a[x]+b[x])%mod);}}

EXPLANATION :

This question used a small trick to calculate the distances for each point from either sides.
The corrected code can be view at, Corrected Solution