ZIO20002 - Editorial

Editorialist : Sudheera Y S

Problem Link : https://www.iarcs.org.in/inoi/2020/zio2020/zio2020-question-paper.pdf

Prerequisites : Logical thinking

Problem statement :

We have to choose a pair say (a,b) and have to keep dividing a by 2 until it becomes an odd number and each time we divide a by 2 , it is counted as an extra operation and same for b i.e keep dividing b by 2 until it becomes an odd number and each time b is divided by 2, it is counted as an extra operation. Given an S , you have to maximize the total number of operations and a+b <= S

Observations :

We keep dividing by 2 and when we it becomes an odd number we stop there. Let us take some numbers and then see after how many steps it will stop :

18 : 9

28 : 14,7

62 : 31

64 : 32,16,8,4,2,1

What can we see here ?

If the number can be represented as 2^x then it will give us the largest answer , because the number which is of the form 2^x is obtained by multiplying 2 ‘x’ times.

Therefore , both a and b should be of the form 2^x and 2^y respectively to get the maximum number.

Observation 1 : Once a is fixed , b is also fixed which is the maximum number smaller than or equal to (s-a) which can be represented as 2^x

Observation 2 : The answer for (a,b) where a = 2^x and b = 2^y i.e answer for (2^x , 2^y) is x+y as to make ‘a’ 1 we have to divide it x times and to make ‘b’ equal to 1 we have to divide it y times , dividing total of x+y times.

Idea :

Therefore answer for (a,b) which is of the form (2^x,2^y) is x+y and we should make sure a+b is smaller than or equal to S , so we will iterate through all x such that 2^x is smaller than S and then find maximum y such that 2^y is smaller than or equal to S-(2^x) and then find the answer for the particular x which is x+y and then take the maximum over all x+y we have obtained and that would be our answer :slight_smile:

Subtask A :

S = 9

x = 0 , a = 1 , S-a = 8 , max y = 3 , b = 8 , a+b <= S , x+y = 3

x = 1 , a = 2 , S-a = 7 , max y = 2 , b = 4 , a+b <= S , x+y = 3

x = 2 , a = 4 , S-a = 5 , max y = 2 , b = 4 , a+b <= S , x+y = 4

x = 3 , a = 8 , S-a = 1 , max y = 0 , b = 1 , a+b <= S , x+y = 3

We can’t continue because if we take x = 4 , then ‘a’ would become greater than S

Maximum x+y = 4

Answer : 4

Subtask B :

S = 58

x = 0 , a = 1 , S-a = 57 , max y = 5, b = 32 , a+b <= S , x+y = 5

x = 1 , a = 2 , S-a = 56 , max y = 5 , b = 32 , a+b <= S , x+y = 6

x = 2 , a = 4 , S-a = 54 , max y = 5 , b = 32 , a+b <= S , x+y = 7

x = 3 , a = 8 , S-a = 50 , max y = 5 , b = 32 , a+b <= S , x+y = 8

x = 4 , a = 16 , S-a = 42 , max y = 5 , b = 32 , a+b <= S , x+y = 9

x = 5 , a = 32 , S-a = 26 , max y = 4 , b = 16 , a+b <= S , x+y = 9

We can’t continue because if we take x = 6 , then ‘a’ would become greater than S

Maximum x+y = 9

Answer : 9

Subtask C :

S = 2008

x = 0 , a = 1 , S-a = 2007 , max y = 10, b = 1024 , a+b <= S , x+y = 10

x = 1 , a = 2 , S-a = 2006 , max y = 10 , b = 1024 , a+b <= S , x+y = 11

x = 2 , a = 4 , S-a = 2004 , max y = 10 , b = 1024 , a+b <= S , x+y = 12

x = 3 , a = 8 , S-a = 2000 , max y = 10 , b = 1024 , a+b <= S , x+y = 13

x = 4 , a = 16 , S-a = 1992 , max y = 10 , b = 1024 , a+b <= S , x+y = 14

x = 5 , a = 32 , S-a = 1976 , max y = 10 , b = 1024 , a+b <= S , x+y = 15

x = 6 , a = 64 , S-a = 1944 , max y = 10 , b = 1024 , a+b <= S , x+y = 16

x = 7 , a = 128 , S-a = 1880 , max y = 10 , b = 1024 , a+b <= S , x+y = 17

x = 8 , a = 256 , S-a = 1752 , max y = 10 , b = 1024 , a+b <= S , x+y = 18

x = 9 , a = 512 , S-a = 1496 , max y = 10 , b = 1024 , a+b <= S , x+y = 19

x = 10 , a = 1024 , S-a = 984 , max y = 9 , b = 512 , a+b <= S , x+y = 19

We can’t continue because if we take x = 11 , then ‘a’ would become greater than S

Maximum x+y = 19

Answer : 19

Hope you understood :slight_smile:

Thanks @sudheerays123 I really understood it. Thanks !!

1 Like