Chef Teams

Problem code: CTEAMS

All submissions for this problem are available.

The executive chef is trying to bring some competitive spirit into his kitchen. He wants to split the chefs into two teams based on their age - he'll form the young and the old team. To make it fair, he will split them evenly or give the young team one person advantage when there is an odd number of chefs. Ages of all employees are unique. The executive chef also rated all chefs according to their cooking skills. Rating of a team is equal to the sum of ratings of its members. The chefs have developed a habit of coming to work late. The executive chef wants to keep the teams as fair as possible at all times and is therefore forced to change the teams each time one of the chefs comes to work in the morning. He needs your help with this task.

Input

The first line contains the number of chefs N. The following N lines describe the chefs in order as they come to work. Each chef is described by two integers, his or her age Ai and rating Ri.

Output

Every time a new chef joins the kitchen, output the absolute difference between team ratings.

Constraints

  • 1 <= N <= 10^5
  • 1 <= Ai <= 10^9
  • 1 <= Ri <= 1000

Example

Input:
5
2 3
1 7
5 5
3 1
8 15

Output:
3
4
5
4
9
Author: thocevar
Date Added: 13-04-2011
Time Limit: 3 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

please describe the output

ar3_ar @ 1 Jun 2011 04:11 PM
please describe the output ...

can anybody xplain the

jravi96 @ 1 Jun 2011 04:39 PM
can anybody xplain the problem in simple words??

@ar3_ar split in to 2 teams

rijin @ 1 Jun 2011 04:52 PM
@ar3_ar split in to 2 teams ryt. then 1st (2,3) comes ; that time 2nd team is zero that time abs diff. of rating is 3-0=3 2nd 1,7 come and join other team abs diff for rating=7-3=4 3rd time 5,5 comes so sum of aages for the chef's <5 so 2,3 moves to 2nd group and 5,5 join 1st group then 7+3-5=5 like that all;

@ar3_ar split in to 2 teams

rijin @ 1 Jun 2011 05:04 PM
@ar3_ar split in to 2 teams ryt. then 1st (2,3) comes ; that time 2nd team is zero that time abs diff. of rating is 3-0=3 2nd 1,7 come and join other team abs diff for rating=7-3=4 3rd time 5,5 comes that time sum of aages for the chef's <5 so (2,3) moves to 2nd group and 5,5 join 1st group then 7+3-5=5 like that all;

@rijin pls xplain the output

jravi96 @ 1 Jun 2011 05:23 PM
@rijin pls xplain the output for the case (3,1) and (8,15)

@jravi96 case (3,1) young

default1130 @ 1 Jun 2011 05:48 PM
@jravi96 case (3,1) young team{1,2} sum1 =7+3=10 old team {5,3} sum2=5+1=6 ans 10-6=4 case (8,15) young team{1,2,3} sum1 =7+3+1=11 old team {5,8} sum2=5+15=20 ans 20-11=9

@default1130 -- thnx a lot

jravi96 @ 1 Jun 2011 05:56 PM
@default1130 -- thnx a lot

im getting runtime error but

Vishnutej @ 1 Jun 2011 06:29 PM
im getting runtime error but my code works fine in my system..plz help!!

i am getting time limit

kapilagarwal @ 1 Jun 2011 07:23 PM
i am getting time limit exceeded . someone could pls advice me how to reduce time limit my soln is http://www.codechef.com/viewsolution/559879

"Please do not discuss

tomaz_adm @ 1 Jun 2011 08:07 PM
"Please do not discuss strategy, suggestions or tips in the comments during a live contest."

One thing I am not clear on

ziyao_wei @ 1 Jun 2011 08:10 PM
One thing I am not clear on this: will there be any duplicate value for ages?

Reread the problem statement

tomaz_adm @ 1 Jun 2011 08:21 PM
Reread the problem statement ... "Ages of all employees are unique"

@Vishnutej i got runtime

rijin @ 1 Jun 2011 09:33 PM
@Vishnutej i got runtime errors mainly due to mistakes in boundary values and limits;

how Time limit exceeded

anksha @ 1 Jun 2011 09:52 PM
how Time limit exceeded removed for this prob

is there any soln in

aayush123 @ 1 Jun 2011 10:54 PM
is there any soln in O(n^2)???????????????????????????????????????????

can this prob solve in

aayush123 @ 1 Jun 2011 10:55 PM
can this prob solve in O(n)???????????????????/

parameter has incomplete

abhicoolest03 @ 1 Jun 2011 11:08 PM
parameter has incomplete type?? how to cure this??

the question is, in case of

alielkhateeb @ 2 Jun 2011 02:30 AM
the question is, in case of (8,15) for example: why did i remove the 3 to the other vector??? why didn't i just add the 8 to the least aged group or the least experienced? :D

now i understood :D ...

alielkhateeb @ 2 Jun 2011 03:46 AM
now i understood :D ... thanks and sorry for disturbance, but i got TLE :D

thanx a lot..

ar3_ar @ 2 Jun 2011 10:26 AM
thanx a lot..

please explain the output

ar3_ar @ 2 Jun 2011 10:42 AM
please explain the output .... why the chef's are moving from one team to another ... help please..

to balance the rating ....as

sagar5 @ 2 Jun 2011 10:58 AM
to balance the rating ....as well as not mixing the young and old team.....if one team's rating is high....it would be younger team....

I am stuck with "Time limit

tassi48 @ 2 Jun 2011 11:13 AM
I am stuck with "Time limit exceeding". What is the problem? can anyone explain??

Can you pls clarify what is

DineshGupta @ 2 Jun 2011 11:36 AM
Can you pls clarify what is young team and old team on the basis of ages? I mean suppose that there are n members then does the young team means summation of ages of young group members is smaller than the other group or first [n/2] young age members will be in younger team?

on which base (age or rating)

ar3_ar @ 2 Jun 2011 11:43 AM
on which base (age or rating) chef should be shift...

@ar3_ar : on the basis of

apoorvpurwar @ 2 Jun 2011 01:00 PM
@ar3_ar : on the basis of age.

in case(5,5) why we are

ar3_ar @ 2 Jun 2011 01:46 PM
in case(5,5) why we are placing (2,3) to another group... and why we are not simply placing just (5,5) to 1st group i.e to (2,3)...

@all gave me 1more in & out

rijin @ 2 Jun 2011 01:51 PM
@all gave me 1more in & out *puts ----> N=4, [1 2 50 100] = is {1,2 } {50,100} or {1 2 50} { 100}

N=4, ages=[1 2 50 100] = is

rijin @ 2 Jun 2011 02:02 PM
N=4, ages=[1 2 50 100] = is {1,2 } {50,100} or {1 2 50} { 100}

My code is giving correct

jay_mahadeokar @ 2 Jun 2011 02:28 PM
My code is giving correct result for the test case given, and all test cases which i tried. Any peculiar test case which might give wrong answer? Some additional examples would be really helpful

wats the output if the inputs

sachin004 @ 2 Jun 2011 02:30 PM
wats the output if the inputs are 5 2 3 4 5 5 5 3 2 8 15

5 {2-3}{3-4}{5-5}{3-2}{8-15}

sachin004 @ 2 Jun 2011 02:31 PM
5 {2-3}{3-4}{5-5}{3-2}{8-15}

sorry

sachin004 @ 2 Jun 2011 02:33 PM
sorry 5{2-3}{4-5}{5-5}{3-2}{8-15}

@sachin : 3 2 3 5 10

rijin @ 2 Jun 2011 02:48 PM
@sachin : 3 2 3 5 10

@sachin @rijin i thnk it sud

tassi48 @ 2 Jun 2011 02:57 PM
@sachin @rijin i thnk it sud be 3 2 7 5 10

Number of test cases is only

rijin @ 2 Jun 2011 02:58 PM
Number of test cases is only one?

@sachin "he young team one

rijin @ 2 Jun 2011 02:59 PM
@sachin "he young team one person advantage when there is an odd number of chefs"

@ rijin den why in d sample

tassi48 @ 2 Jun 2011 04:43 PM
@ rijin den why in d sample input he hasnt given d advantage when all d input are dere. means 5 sud be in young team if tat so.

@tassi : check the

rijin @ 2 Jun 2011 04:50 PM
@tassi : check the description of outputs given above!!!

I am continuously getting TLE

nntnag17 @ 2 Jun 2011 04:59 PM
I am continuously getting TLE for O(n^2). Those who have solved , what is the complexity of your algortihm.??

Anyone ans plz : Number of

rijin @ 2 Jun 2011 05:04 PM
Anyone ans plz : Number of test cases?

Please provide more test

harishp @ 2 Jun 2011 08:02 PM
Please provide more test cases..

Please note that discussing

tomaz_adm @ 2 Jun 2011 09:38 PM
Please note that discussing time complexities of your solutions is against the rules! There is a single test file. Sample test case is here to illustrate the input/output format and to clarify the problem. It is not supposed to help you test your solution. Therefore, additional test cases will not be provided.

a simple question: shall i

alielkhateeb @ 3 Jun 2011 05:24 AM
a simple question: shall i print the output every time a chef joins the kitchen directly or accept all inputs, calculate and then print the result array for example: is it => Input: 5 2 3 3 1 7 4 5 5 5 3 1 4 8 15 9 or is it => 5 2 3 1 7 5 5 3 1 8 15 3 4 5 4 9

i mean this: {5} {2 3} 3 {1

alielkhateeb @ 3 Jun 2011 05:27 AM
i mean this: {5} {2 3} 3 {1 7} 4 {5 5} 5 {3 1} 4 {8 15} 9 or this: {5} {2 3} {1 7} {5 5} {3 1} {8 15} 3 4 5 4 9

You can do it either way. The

tomaz_adm @ 3 Jun 2011 11:08 AM
You can do it either way. The judge evaluates your output when the program ends.

can anyone please tell how to

kshav @ 3 Jun 2011 11:24 AM
can anyone please tell how to use tic tock func. to check compile time?

is there need to take var. T

piyushurpade @ 3 Jun 2011 05:31 PM
is there need to take var. T for test cases please ans i got run time error for input explain above

or is this because of

piyushurpade @ 3 Jun 2011 05:40 PM
or is this because of declaration long long age[5000],

By constraints as

orion_88 @ 3 Jun 2011 07:16 PM
By constraints as 1<=Age<=10^9, does that mean test cases will not include entries like (-9,4), that is a test case that checks the behavior of the program when a value outside the boundary condition is inserted. This is my first time paticipating here and so bit confused.

Test cases in all problems

tomaz_adm @ 3 Jun 2011 09:21 PM
Test cases in all problems satisfy the constraints so you don't have to deal with any invalid data.

@admin and all: Plz explain

paarth @ 3 Jun 2011 11:56 PM
@admin and all: Plz explain ...for the given example...on what basis last input (8 15) chooses the young team and old team.... 1stly how a team is young or old..??....on the basis of age of all members of the team(sum) or the max age or the min age...?? 2ndly how to decide which team will it take ....young or old ...on basis of reducing the final age difference or on basis of the difference of the max. age of the teams and the new member age...?? plz do reply.....

@tomaz_adm plz do reply......

paarth @ 4 Jun 2011 12:49 AM
@tomaz_adm plz do reply......

The chefs are split by

tomaz_adm @ 4 Jun 2011 01:31 AM
The chefs are split by chosing some age limit (not necessarily integer) and assigning all younger chefs to the first team and all older chefs to the second. Age difference and ratings are irrelevant in the process of forming the teams. The only goal is to balance the number of members in each of the teams.

i have tried 3 diff algos anf

null_pointer @ 4 Jun 2011 01:40 AM
i have tried 3 diff algos anf getting TLE everytime ,i dont know whether this is due to java or whatever,i am going mad now..,can anybody help???

Getting a runtime Error

malaykeshav @ 4 Jun 2011 02:05 AM
Getting a runtime Error everytime :/ "SIGSEGV" The code is running fine on my PC. and i have used dynamically allocated memory using the "new" constructor (in various functions) making a linked list, instead of an array. what seems to be the problem?

@tomaz_adm: Is it necessary

orion_88 @ 4 Jun 2011 11:50 AM
@tomaz_adm: Is it necessary to output the results(the rating differences) altogether at the end of inputs?.Can alteration be done in the order as in I/P:2 3 O/P:3 1 7 4 5 5 5 3 1 4 8 15 9 Please reply.. @null_pointer: pretty much the same condition, but its better not to get mad. Lets kep at it man and get this problem solved.

Please check previous posts

tomaz_adm @ 4 Jun 2011 02:58 PM
Please check previous posts (by alielkhateeb) before asking the same question that has already been answered.

@tomaz_adm:apologies and I

orion_88 @ 4 Jun 2011 04:12 PM
@tomaz_adm:apologies and I appreciate your reply. Thanks :)

@admin Id 564179 Plzzz check

littleboy @ 4 Jun 2011 05:34 PM
@admin Id 564179 Plzzz check whats wrong there??? Does it need optimization or should i start from scratch with another approach???

@admin Id 564179 Plzzz check

littleboy @ 4 Jun 2011 05:34 PM
@admin Id 564179 Plzzz check whats wrong there??? Does it need optimization or should i start from scratch with another approach???

@admin...my code gives

theunforgiven @ 4 Jun 2011 11:45 PM
@admin...my code gives TLE.....i hv tried a lot to optimize it bt failed..pls give it a look..nd tell whts wrong in there??? http://www.codechef.com/viewsolution/564544

@orion_88 yeah man keep

null_pointer @ 5 Jun 2011 11:29 AM
@orion_88 yeah man keep trying ,i am thinking a diffrnt approach now..

@tomaz_admin: i m getting

agarwalchucky @ 5 Jun 2011 07:47 PM
@tomaz_admin: i m getting wrong answer bt for test case u have provided i m getting same answer....whatever test case i make i am getting the answer as it was supposed to be...can u tell where i can be wrong...

can anyone tell y wrong

agarwalchucky @ 5 Jun 2011 08:03 PM
can anyone tell y wrong answer for this problem is coming even i m getting same answer for given test case...

what does 0M mean , i got it

arpitiiita @ 5 Jun 2011 10:08 PM
what does 0M mean , i got it when i submit my code , is it zero memory or my code was not compiled.....

Come on Guys! Age of 10^9.

chamanchindi @ 6 Jun 2011 02:41 PM
Come on Guys! Age of 10^9. Does even human race age 10^9?

I guess cooks are not human

mkagenius @ 6 Jun 2011 04:21 PM
I guess cooks are not human :P .::LOL::.

The problem statement doesn't

tomaz_adm @ 6 Jun 2011 07:26 PM
The problem statement doesn't specify age unit - could be seconds and not years. :)

then 1s is not fair at all...

pikku @ 6 Jun 2011 07:42 PM
then 1s is not fair at all... lol :-P

@pikku That 1 had the unit of

ambujpandey @ 6 Jun 2011 08:10 PM
@pikku That 1 had the unit of 'scores'. 10^9 would be in seconds. :-)

Or rather milliseconds...

ambujpandey @ 6 Jun 2011 08:13 PM
Or rather milliseconds...

@rijin Can u illustrate what

angelin_nadar @ 6 Jun 2011 10:15 PM
@rijin Can u illustrate what are boundary values and limits? Iam too getting runtime error.

@admin My code is executing

tanzeel @ 7 Jun 2011 03:53 PM
@admin My code is executing within 2s in my computer for a testcase involving 10^5 chefs,I have also tried running the program using the method mentioned in the FAQ and it works fine there as well. However, when i submit my code, it gives a TLE.

The judge is very slow. From

tomaz_adm @ 7 Jun 2011 04:47 PM
The judge is very slow. From my experience it is at least 5 times slower than my local computer. Also note that the size of input data in this task is rather large which can be a problem for solutions written in Java.

I gave up....TLE...cant

ritesh_gupta @ 7 Jun 2011 06:01 PM
I gave up....TLE...cant optimise further.....Now waiting for the editorials....and the horrible june long contest 2 end.

Is it possible that the Java

tekas1234 @ 7 Jun 2011 10:47 PM
Is it possible that the Java judge that CodeChef has has possibly become slow? Seems silly, but I have submitted my practice problems(The first two) and they are giving unrealistically high time of 4-5 seconds. So I submitted the fastest running Java codes as my own, and lol, they were coming out to be slower than my own solution. Is it possible that the judge has become slower than usual?

Hi, If I run a program

vicky_iisc @ 7 Jun 2011 10:59 PM
Hi, If I run a program which does nothing, like int main() { return 0; } it still shows 2.6 M memory on my submission. What part of my program is taking that mem ?

@tekas1234: Indeed! One of

lesley_t @ 8 Jun 2011 08:07 PM
@tekas1234: Indeed! One of the best solution for enormous input test problem written in java which took 0 seconds to complete is now taking 7.89 seconds. Either the judge is showing the time incorrectly or is incredibly slower than usual.

Can I know the execution time

chirag.agrawal19 @ 9 Jun 2011 02:10 AM
Can I know the execution time of my code in case of TLE?

hard problem T_T

nonspec5 @ 9 Jun 2011 11:57 PM
hard problem T_T

In my PC its gets only 3.123s

Najmuzzaman @ 11 Jun 2011 02:27 PM
In my PC its gets only 3.123s for N=10000 but here is TLE Anyone help me my submission id is 571374

Contest Ended ; but y

rijin @ 12 Jun 2011 03:53 PM
Contest Ended ; but y solutions not open to public?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions