You are not logged in. Please login at www.codechef.com to post your questions!

×

# CHKDST - Editorial

 0 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[i]%mod;a[i]=(a[i-1]+upd)%mod;} upd=0; for(int i=n;i>=0;i--){ upd=b[i]%mod;b[i]=(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 This question is marked "community wiki". asked 30 Mar '16, 21:57 11●1 accept rate: 0% 0★admin ♦♦ 19.7k●350●498●541
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,482
×2,557
×1,236
×836
×814
×6
×1

question asked: 30 Mar '16, 21:57

question was seen: 476 times

last updated: 01 Apr '16, 16:41