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

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

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

Thaanks for your explaining your solution mate.

(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

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!

Thanks for the editorial, it really helped.

2 Likes

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

can anyone please help me, what’s wrong in my code of CHEF AND UNIVERSE.
CHEFUNI - CodeChef: Practical coding for everyone

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.

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

Thanks in advanced.

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.

Really bad format.
It wouldn’t hurt to add a few white space in that colossal paragraph.

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

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

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…

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 you go. Use this as a checker code :slight_smile:

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