Here i am with my second editorial on CHEFUNI . It will also be kind of guideline how to approach when you cant disprove yourself but get WA. One advantage I had was that the testcase generation and verifying was pretty simple. Anyways let’s proceed.
SOLVING SUBTASK 1: Solution of subtask 1 is pretty simple. Just do a dp with the recursion
As the constraints suggest its clearly O(1) per query or rather O(c) where c can be upto 1000. Now as one can guess its clearly greedy. So lets approach slowly towards the correct solution just like i did. Sort such that x<y<z. First of all one can easily think why only one of 5 possibilities are there:
Take all ‘a’ type steps: Cost=(x+y+z)*a
Take combination of ‘a’ and ‘b’ type steps: Two possibilities: 1)when z>(x+y) we can take only (x+y) ‘b’ type steps rest we need to take ‘a’ type steps. 2)else we can take (x+y+z)/2 ‘b’ type steps and (x+y+z)%2 ‘a’ type steps.
Take combination of ‘a’ and ‘c’ type steps: We can take atmax x ‘c’ type steps and rest ‘a’ type.
Take combination of ‘a’ and ‘b’ and ‘c’ type steps. Now this is where things get tricky. First we all would think of taking greedily as many ‘c’ type steps as possible, followed by greedy choosing of ‘b’ type steps and rest ‘a’ type steps. But this gives WA. You can use your bruteforce solution generating random testcases to see that there are cases where actually this greedy assignment doesnot work. A little brainstorming gives you the reason. What if **a is greater than b and c ** by such an amount that this greedy assignment cost increases because of choosing so many ‘a’ type steps. The count being ** (z-y) **. (Proof is left for readers). Now our main aim will be to reduce ‘a’ type steps. But HOW?? By compensating a few ‘c’ type steps and changing them into ‘b’ and ‘a’ type steps such that overall count of ‘a’ type steps gets reduced. Now greedy choosing of ‘c’ ,‘b’, and ‘a’ type steps, we had to take x ‘c’ type steps (y-x) ‘b’ type steps and (z-y) ‘a’ type steps. Now suppose we do not take the (z-y) ‘a’ type steps. The point where we stand we have to move more (z-y) steps along z direction. Let us take away k ‘c’ type steps from this position i.e. we move diagonally in reverse direction by k steps. From the point we are at we need to take more k steps along x direction, k steps along y direction and k+(z-y) steps along z direction. So considering this pt. as the origin our destination is at (k,k,k+z-y). Now we take the remaining steps to be of ‘b’ and ‘a’ types. Now we discussed a point before that taking ‘b’ and ‘a’ type steps had 2 conditions- z>(x+y) and z<=(x+y) where in the latter we needed only (x+y+z)%2 steps of ‘a’ type. So for minimizing ‘a’ type steps we must satisfy z<=x+y . Or, k+z-y<=2*k which implies k>=(z-y). So if we take away more than (z-y) ‘c’ type steps we might find an optimal ans. Now here i used a bit complexity analysis. Seeing atmax O(1000) per query is permissable i ran a loop from (z-y) to (z-y+1000) seeing when i get the optimal ans. Here is the code to that. Then later i verified at (z-k) only it gives minimum. Here . IDK THE PROOF FOR UPPERBOUND. If anyone has proved this kindly share please
The last case is from the relation 3b=2c i.e. we can compensate 2 ‘c’ type steps by taking 3 ‘b’ type steps. So we will be left with (2c)%3 ‘c’ type steps which can be 0,1 or 2. 0 case being greedy choosing of ‘a’ and ‘b’ type steps. So we need to handle the case of 1 ‘c’ and rest ‘b’ and ‘a’ and case of 2 ‘c’ and rest ‘b’ and ‘a’ seperately.
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