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
SOLVING FOR 100 POINTS:
As the constraints suggest its clearly O(1) per query or rather O© 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.
Finally min of all above cases gives the ans.
**COMPLEXITY: O(1) per query **
If anyone has better solution please share