# CHEFUNI UNOFFICIAL EDITORIAL

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

F(x,y,z)=min(F(x-1,y,z)+a,F(x,y-1,z)+a,F(x,y,z-1)+a,F(x-1,y-1,z)+b,F(x-1,y,z-1)+b,F(x,y-1,z-1)+b,F(x-1,y-1,z-1)+c)

Complexity=O(n^3)

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:

1. Take all βaβ type steps: Cost=(x+y+z)*a
2. 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.
3. Take combination of βaβ and βcβ type steps: We can take atmax x βcβ type steps and rest βaβ type.
4. 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
5. 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

13 Likes

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.

My solution:
https://www.codechef.com/viewsolution/16430878

(For finding b-type u can just sort p,q,r to x,y,z see if z>=x+y and z<x+y)
(If any1 waants exact eqns ,feel free to ask)

1 Like

nice method mate thanks for sharing. P.S: H.W karne do bachcho ko xD

Very nice editorial

2 Likes

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 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

can u please share the equations? or a hint how to reach there?

The ones for case 2?

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β¦

Thanks for the editorial, it really helped.

2 Likes

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

I have done the same, taking all cases and printing minimum

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.

1. (6a <= 3b && 6a <= 2c)
2. (2c <= 3b && 2c <= 6a)
3. (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.

My solution

1 Like

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)

CHEFUNI - https://www.codechef.com/viewsolution/16510087

Here you go. Use this as a checker code

how do yo know that the question wants O(1) solution ?, i also want to know how to figure out this thing by analysing the constraints.

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

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 -

1 7905 7405 8836 913 444 711

expected: 3744320 got: 5360412

https://www.codechef.com/viewsolution/16565970