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