Editorialist: Sudheera Y S
Problem Link: ZIO 2012 Problem 1
Prerequisites: ad-hoc
Problem statement :
There are ‘x’ white color balls and ‘y’ black color balls in a bag. You pick two ball at a time and follow the procedure :
- If both are white , throw both of them
- If both are black , throw one ball , and return another in the bag
- If they are different colors , then throw the black ball and return the white ball in the bag
Compute the minimum and maximum values of N ( number of times you pick the balls ) and the color of the last ball
Idea :
Here we find a pattern ( with logic ) :
From points 2,3 ( problem statement ) , we find that in either of the cases the number of black ball reduces only by 1 , therefore we need :
Let’s denote the number of black balls by x :
- If x is odd → one by one reduces , therefore we need x operations to completely throw the black balls
- If x is even → we cant throw away the last ball , no matter what therefore we need exactly x-1 operations to throw away all x-1 black balls and only 1 ball will be left
Here we should also observe that Min N = Max N because we are performing the same operations and if we do the operations in any order , it doesn’t matter because to throw away all the black balls , we need exactly x or x-1 operations NO MATTER WHAT ( i.e even if we do operations 2 or 3 , the black ball reduces only by 1 ) therefore Min N = Max N ( because we can only lose white balls by operation 1 )
Minimum ( and maximum ) number of operations to throw away all black balls → x or x-1
Minimum ( and maximum ) number of operations to throw away all white balls → floor(y/2)
Therefore , Min N = Max N = ( x or x-1 ) + floor(y/2)
Here we are doing floor because , if y is odd then we will end up with last one ball therefore we need exactly (y-1)/2 for y being odd and floor does that 
If y is odd , we end up last ball being white because white ball only reduces by 2 and if y is even , then we will end up with last ball being black because black reduces only by 1
Summing it up , Min N = Max N = ( x or x-1 ) + floor(y/2) , color of the last ball is white if y is odd , or else if y is even then the last ball color will be black ( now let us start doing the subtasks )
Subtask A: 17 black, 23 white
Min N = Max N = 17 + (23/2) = 17 + 11 = 28
Number of white balls is odd, therefore color of the last ball is white
Answer: 28, 28, white
Subtask B: 42 black, 32 white
Min N = Max N = 41 + (32/2) = 41 + 16 = 57
Number of white balls is even, therefore color of the last ball is black
Answer: 57, 57, black
Subtask C: 111 black, 99 white
Min N = Max N = 111 + (99/2) = 111 + 49 = 160
Number of white balls is odd, therefore color of the last ball is white
Answer: 160, 160, white
Hope you understood