Unoffcial Editorials OCT COOKOFF

general
1

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

2

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

3

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


[1]


  [1]: https://www.codechef.com/viewsolution/15924804
4

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

5

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.

6

Haha , It is ingrained in my muscle memory .

7

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.
8

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.

1 Like
9

Fourth and fifth problems plis? ;_;

10

You must be kidding right xD

11

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

12

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

13

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?

14

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

15

found the error.
it is integer overflow.