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

×

CHKDST - Editorial

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

vibhor3gupta's gravatar image

4★vibhor3gupta
111
accept rate: 0%

edited 01 Apr '16, 16:41

admin's gravatar image

0★admin ♦♦
19.7k350498541

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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