ZIO20002 - Editorial

editorial
, , , ,
1

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:

4 Likes
2

Thanks @sudheerays123 I really understood it. Thanks !!

4 Likes
3

I did it in mostly the same way but I managed to get an answer for the general question.
The first post is sort of lengthy(though effective) and will not be useful if the integer S is made very large. So I got some sort of a logic for the general case
The idea is this:

First for the given Integer S, determine the unique integer r with the property that 2^r \leq S < 2^{r+1}

Next check for the following:

If S<2^r + 2^{r-1}, then the answer is 2r-2.
If S \geq 2^r + 2^{r-1} then the answer is 2r-1.

Could anyone check for a certain values if this is correct.(Like does the idea give accurate results)

My solution :slightly_smiling_face:
First we develop some notation that will be useful. Define v_2(n) to be the exponent of the maximum power of 2, that divides n.
In other words we have 2^{v_2(n)} \mid n, but 2^{v_2(n) + 1} \nmid n.

Now we understand what the problem wants us to do. In terms of the notation we have just developed, it means that we have to given an integer S, we need to find positive integers x,y with x+y \leq S, and such that the quantity v_2(xy) is maximised.

Now we find an upper bound for the quantity v_2(xy).

For this we first determine the unique integer r with the property that 2^r \leq S < 2^{r+1}

Note that we have 2^{v_2(xy)} \mid xy and so 2^{v_2(xy)} \leq xy, that is v_2(xy) \leq \log_2(xy)

Using the AM-GM inequality we have xy \leq \tfrac{(x+y)^2}{4}
Thus v_2(xy) \leq \log_2(xy) \leq \log_2(\tfrac{(x+y)^2}{4}) = 2(\log_2(x+y) - 1)

Now by the statement of the problem x + y \leq S < 2^{r+1}
So v_2(xy) < 2(\log_2(2^{r+1}) - 1) = 2r
As v_2(xy) is an integer we have v_2(xy) \leq 2r-1

Thus no matter what numbers x,y we choose we can never do better than 2r-1.
But we are not done, for we still need to check whether this bound can be achieved, and as it happens in some cases it is not.

Now we consider 2 cases:

Case1: S \geq 2^r + 2^{r-1}

In this case we can simply choose x = 2^r, y = 2^{r-1} and get the maximum value of v_2(xy), 2r-1
So in this case 2r-1 is our answer.

Case2: S < 2^r + 2^{r-1}

Here we proceed indirectly. Suppose that our maximum of 2r-1, is achieved for some integers x,y.
Then v_2(xy) = 2r-1 that is v_2(x)+v_2(y) = 2r-1

Now since x+y \leq S < 2^{r+1}, both x,y < 2^{r+1}
This forces v_2(x) \leq r and v_2(y) \leq r

Now if none of v_2(x), v_2(y) equals r, then their sum will be atmost 2(r-1) which is impossible as their sum is 2r-1 .

So one of v_2(x),v_2(y), must be r.
Suppose that v_2(x) = r. This forces x = 2^r which automatically implies that v_2(y) = r-1 which means that 2^{r-1} \mid y, so we can write y = 2^{r-1}k for some integer k \geq 1.

Thus 2^r + 2^{r-1} > S \geq x + y = 2^r + 2^{r-1}k which gives 1 > k, an impossibility.
So the maximum value in this case cannot be 2r-1, which means it is at most 2r-2.
And this bound can be indeed achieved by choosing x=y=2^{r-1}(this choice is possible as x+y = 2^r \leq S)

Please let me know if you could not understand anything.

4

Please let me know if my method is correct.

5

I have the same method as well. If the 2 most significant bits are set, then take them giving the answer 2r - 1 else take 2 of the second most significant bit giving the answer 2r - 2.

6

Yeah, I guess you got it, that is exactly what I did

7

sir…i was unable to get any sorta clue out there…can you please find a simpler way out

8

It is one of the best explanation. …:blush:

1 Like
9

Which part of my solution do you have doubt in?

10

Actually i am beginner…so acc to me your answer wasn’t much beginner oriented bro…

11

Ok, I can help there:
I have just used AM-GM as an additional theorem.
The notation v_2(n) refers to the maximum exponent of 2 in n.
For eg, v_2(100) =2, as 2^2 \mid 100, but 2^3 \nmid 100.

Now are you able to understand my solution??

12

Bro the solution is good but its like
‘ki ab makhi ko marneke liye talvar nikaloge kya…’
we can even solve this question just by feel its simple as we know 2 raised to some power will give answer then we must find best possible combination and that’s all done with it…