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

×

Unoffcial Editorials OCT COOKOFF

Chef and Employment test

**Note : * It is guaranteed that n+k is an odd number and also k < n.

So it is obvious that the median will be a number having index number between 0 and n-1.

And also the median of the whole array will be at index (n+k)/2 .

First of all sort the given array

We have to add numbers such that we have the maximum medium .

There can be two cases :

(1) Adding numbers greater than the number at index (n+k)/2 .

(2) Adding numbers less than the number at index (n+k)/2 .

If we add numbers less than the number at index (n+k)/2 , it will shift that number away from the median and the new median will be a lesser number .

So we should only add number greater than number at index (n+k)/2 .

So the answer by default becomes the number at index (n+k)/2 in the original array.

Chef and Weird Queries

A simple observation is that b can't be greater than 700 so all the values of A , having , number of B values that satisfy the equation can be at max 700 even if there are a lot of possible values . So if the number of B that satisfy the equation for a particular A are greater than 700 , we only consider 700 pairs for that A .

Building upon this ,

if y-700 <=0

this means that there are no such values which for a particular A , have number of B >700 . So we only simply count the number of B for every value of A

//Here i represents A

for(register long long int i=1;i*i<=y;i++)

{

    if((y-i*i)<=700)

    ans=ans+(y-i*i);

    else

    ans=ans+700;

}

else

upto the square root of y-700 , for all A , number of B are greater than 700 so we add them to our answer

a=(long long int)(sqrt(y-700));

ans=ans+(long long int)(700*a);

And then from (long long int)(sqrt(y-700))+1 until a^2 <=y , we individually add B for every value of A.

for(long long int i=(a)+1;i*i<=y;i++) {

if((y-i*i)<=700)

    ans=ans+(y-i*i);

}

Link : https://www.codechef.com/viewsolution/15931204

asked 23 Oct '17, 00:38

trashmaster's gravatar image

2★trashmaster
98619
accept rate: 12%

Makes me feel good when I see some1 using register keyword. :D

(23 Oct '17, 01:34) vijju123 ♦♦5★

Haha , It is ingrained in my muscle memory .

(23 Oct '17, 10:36) trashmaster2★

hi @we7d thanks for the help. Two of my submissions got WA because of this. I dont have karma points to upvote your comment. Still thanks again.

link

answered 23 Oct '17, 13:43

b123eginner's gravatar image

3★b123eginner
111
accept rate: 0%

Hi can you please tell my why code to question: "Chef and Employment" test gives wrong answer. Link to code: Code

link

answered 23 Oct '17, 02:04

b123eginner's gravatar image

3★b123eginner
111
accept rate: 0%

@b123eginner don't use scanf with sync_with_stdio(false)

link

answered 23 Oct '17, 02:33

we7d's gravatar image

2★we7d
222
accept rate: 0%

the first question is pretty mediocre , you do not need to such stuffs , just sort you array and print a[(n+k)/2] . since no matter how many elements you add , as k<=n you will end up with the median at (n+k)/2 always.

link

answered 23 Oct '17, 06:08

striverlearner's gravatar image

3★striverlearner
46910
accept rate: 0%

And if I ask you "Why?" or to give the proof? That guy has attempted to give a proof of why it works if you read carefully. And thats helpful for newbies. I wouldnt at all like it if the editorial simply says-

he first question is pretty mediocre , you do not need to such stuffs , just sort you array and print a[(n+k)/2] . since no matter how many elements you add , as k<=n you will end up with the median at (n+k)/2 always.

(23 Oct '17, 12:43) vijju123 ♦♦5★

its better to not look at people's comment in personal, its not a post dude! its better if you look at your personal things, i find noone at forum having a problem , so why are u interfering?

(23 Oct '17, 21:12) striverlearner3★

Fourth and fifth problems plis? ;_;

link

answered 23 Oct '17, 15:09

ista2000's gravatar image

4★ista2000 ♦
2.4k723
accept rate: 20%

You must be kidding right xD

(23 Oct '17, 15:26) trashmaster2★

i could just wish tourist wish and other top notch coders being more active here in the forum, but not the case :(

(23 Oct '17, 21:13) striverlearner3★

@b123egineer check your code on following case https://ideone.com/7YzCvx

link

answered 23 Oct '17, 18:14

alphastar's gravatar image

2★alphastar
295
accept rate: 0%

Please help. I am not able to find error in my solution of 3rd question (Chef and Counting Test). My code is here.

link

answered 23 Oct '17, 19:28

atuly's gravatar image

3★atuly
0
accept rate: 0%

found the error. it is integer overflow.

(24 Oct '17, 01:01) atuly3★
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:

×368

question asked: 23 Oct '17, 00:38

question was seen: 876 times

last updated: 24 Oct '17, 01:01