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