ZIO12001 - Editorial

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 :

  1. If both are white , throw both of them
  2. If both are black , throw one ball , and return another in the bag
  3. 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 :

  1. If x is odd → one by one reduces , therefore we need x operations to completely throw the black balls
  2. 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 :slight_smile:

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 :slight_smile: ( 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

:slight_smile: