Logic behind TROO1 Trinity 2014 ( Notorious Gunner ) ?

I have seen many solutions and they all look like this :

int f( int x)
{ int ans ;
    while ( x > 1)
    {
     ans++ ; x /= 2 ; 
    }
    return ans ;
}
final_ans = max ( f(a) , f(b)) ;
where a and b are no.of rows and no.of columns .

I want to know the logic behind it ?

@alphaparticle
Question has adhoc solution.

Here is my solution in python

import math
t=input()
i=0
while(i<t):
	P,Q=map(int,raw_input().split())
	fool=max(P,Q) #max becuase we are calculating ans for worst case so we will go to maximum of (row,col)
	print int(math.log(fool,2))
	i+=1

i came across this logic after reading question.

suppose we have nn matrix ,for calculating the answer for worst case scenario suppose chef first open box which is placed on middle of matrix(n/2,n/2),now this box would tell us which sub-matrix we will choose in order to reach the final box(whether right-up,right-down,left-up,left-down),now we would have have sub-matrix of only 1/4th sizeof original,again choose middle of this sub-matrix and open the box which is placed on it, it will again break matrix into 4 parts ,and this would go on till we reach at the end of matrix… at the end you would find the final box . Simply this recursive solution would take LOG(N) steps,now formalize this into mn matrix,and find max of m and n,and answer would be as simply as it is LOG(max(M,N));

I would like to explain it in simple words.

The strategy to get to the box fastest would involve looking at the box at the center of the matrix, so that you can reduce the search space in the next trial by 1/2 the size of the original side by using the directions given in the box.

So it is like you are moving into smaller and smaller squares after each guess, but the bottleneck would be the larger side.

Hence the search will take floor(log(max(m,n))), which is the answer.

1 Like