I did a bit different. First i convert b and c such that b<=2a and c<=3a.For that u can easily notice that to obtain a change using b-type,u can do it using two a-type or 1 b-type.
So if(b>2a): b=2a
Similarly if(c>(b+a)): c=b+a
So now we are set to start.We have to find a (c,b,a) combination of minimum value.Now its obvious that you should take as minimum ‘a’ as possible.So lets say you do x c-type operations(where x is less than equal to min(p,q,r)),for this find after applying this whats the maximum b-type operations.Now we have to do this for all x<=min(p,q,r).
If u actually try solving it,u’ll get some equations which can be easily minimised to get the best value of x ,ie best value of (c,b,a) pair.
hello soham
in comments of CHEFUNI someone asked if (p,q,r)–>(p-1,q,r) i.e. reverse steps are allowed or not. then admin said NO.Then why did u take reverse steps? Means I did not understand the diagonally reverse steps part!
I have solved this problem using ternary search. Range of searching is low=0 to hi=Min(x, y, z).
If you think using these three conditions you will feel it easily.
(6a <= 3b && 6a <= 2c)
(2c <= 3b && 2c <= 6a)
(3b <= 6a && 3b <= 2c)
Ternary search is only required for condition 2 and 3. Also you can feel both conditions are redundant.
You have to apply ternary search two time one for odd values in range [low, hi] another for even values in range [low, hi]. Result will be minimum of those two results.
I tried using the approach suggested by @chef_keshav. However, the solution is still wrong, can anyone please help me ? I am unable to figure out why this test case gives wrong answer -
Does anyone know of any other question which is similar to this one? Because I couldn’t understand more than a few things in this editorial and I am really looking forward for an in-depth and intuitive explanation to the solution of this problem. Thanks already.
I did not take reverse steps. What i did was not take k ‘c’ type steps. This is equivalent to take x ‘c’ type steps and later move ‘k’ steps diagonally backward. Hope this helps
Suppose x<=y<= z. Try simulating as many possible B moves as you can. U’ll notice that when x+y <= z, optimal moves will be x B-type moves in xz direction and y B-type moves in yz direction. After that, x=0 and y=0, making further B-type moves impossible.
In other case where x+y>= z, we can make floor((x+y+z)/2) B type moves, because after this moves, either we have reaches our destination, or are just one A-type move far from destination, so no more B-type moves possible…
First sort p,q,r lets say we obtain A,B,C.
After x c’type operation,we have A-x,B-x,C-x.
So for case z>=x+y,C-x>=A-x+B-x i.e.x<=C-A-B,similarly for other case x>=C-A-B,so u can separately find for these ranges[0,C-A-B] and (C-A-B,min(p,q,r)] ,now for the first range and second range 'b’type ans is as @taran_1407 said.lets say we do k 'b’type operation,so 'a’type operations=p+q+r-3x-2k
Thanx for sharing this solution!! I was stuck at this,I knew that for some x,f(a)>f(b) a<b<=x and for x<a<b<=high f(a)<f(b) ,but didnt knew how to minimise it(i havent used ternary search till now)
Here T=1e5. And x,y,z=1e5 and a,b,c=1000. So its clear we cant write a dp solution. Now permissible time per testcase is 1000 iterations at max as 1e8 takes about 2 sec roughly. So u can go for log(max(x,y,z)) per query or max(a,b,c) per query. There exists a log() per query as pointed out in comments above using ternary search
thanks for sharing. P.S: H.W karne do bachcho ko xD
