There is no such thing as “optimal for both of them.” The total sum is constant, so if one player gains, the other must lose.
1 Like
Transition from Directi to Unacademy can be seen through this Lunchtime…
Same
The explanation of the lemma is not clear mathematically…IG
It’s way too easy to code it, but proving the above fact isn’t.
PS: When a reply gets more likes than the editorial 
5 Likes
We know, Chefu can get Y gold by using strategy “mine in same mine as Chef”, so any strategy getting him less than Y gold is not optimal.
1 Like
please tell me the difference in the codes…first solution and second solution …why the first solution got AC and second gave WA ??
And why using cout<<fixed<<showpoint it got AC and not without it??
because of this even after cracking the solution didn’t get AC 
1 Like
setprecision(5) worked for me
My approach is similar, I have used this formula:
Work = Efficiency * days
How Chefu can get Y gold by using strategy “mine in same as chef” was my question .
Can someone check where did I got wrong in my solution :-
CodeChef: Practical coding for everyone → Submission during the contest
My solution was working for partial testcases during the contest, but after reading the editorial I got to know that I’ve did the solution similar to editorial
I’ve provided my code here itself.
Someone please find the mistake for the code above.
Thank You!! 
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int t;
cin>>t;
while(t–){
int n;
cin>>n;
array<double, 3> gab[n];
for(int i = 0;i < n;i++){
cin>>gab[i][0];
cin>>gab[i][1];
cin>>gab[i][2];
}
double a1 = 0, a2 = 0;
for(int i = 0;i < n;i++){
a1 += (gab[i][0] * gab[i][2])/ (gab[i][1] + gab[i][2]);
a2 += (gab[i][0] * gab[i][1])/ (gab[i][1] + gab[i][2]);
}
cout << fixed << setprecision(6) << a1 <<" “<< a2 <<endl;
continue;
if(n == 1){
double a1, a2;
a1 = (gab[0][0] * gab[0][2])/ (gab[0][1] + gab[0][2]);
a2 = (gab[0][0] * gab[0][1])/ (gab[0][1] + gab[0][2]);
cout << fixed << setprecision(6) << a1 <<” "<< a2 <<endl;
}
else if(n == 2){
double a1[3], a2[3];
// Worked in same mine at same times from the start
a1[0] = ((gab[0][0] * gab[0][2])/ (gab[0][1] + gab[0][2])) + ((gab[1][0] * gab[1][2])/ (gab[1][1] + gab[1][2]));
a2[0] = ((gab[0][0] * gab[0][1])/ (gab[0][1] + gab[0][2])) + ((gab[1][0] * gab[1][1])/ (gab[1][1] + gab[1][2]));
//Both worked in different mines initially.
// A worked in 1st mine first
double ab = min(gab[0][1], gab[1][2]);
a1[1] = (gab[0][0] * ab)/ (gab[0][1]);
a2[1] = (gab[1][0] * ab)/ (gab[1][2]);
double g1 = gab[0][0] - a1[1];
double g2 = gab[1][0] - a2[1];
if(g1 != 0){
a1[1] += (g1 * gab[0][2])/ (gab[0][1] + gab[0][2]);
a2[1] += (g1 * gab[0][1])/ (gab[0][1] + gab[0][2]);
}
if(g2 != 0){
a1[1] += (g2 * gab[1][2])/ (gab[1][1] + gab[1][2]);
a2[1] += (g2 * gab[1][1])/ (gab[1][1] + gab[1][2]);
}
// A worked in 2nd mine first
ab = min(gab[1][1], gab[0][2]);
a1[2] = (gab[1][0] * ab)/ (gab[1][1]);
a2[2] = (gab[0][0] * ab)/ (gab[0][2]);
g1 = gab[1][0] - a1[2];
g2 = gab[0][0] - a2[2];
if(g1 != 0){
a1[2] += (g1 * gab[0][2])/ (gab[0][1] + gab[0][2]);
a2[2] += (g1 * gab[0][1])/ (gab[0][1] + gab[0][2]);
}
if(g2 != 0){
a1[2] += (g2 * gab[1][2])/ (gab[1][1] + gab[1][2]);
a2[2] += (g2 * gab[1][1])/ (gab[1][1] + gab[1][2]);
}
cout << fixed << setprecision(6) << a1[0] <<" "<< a2[0] <<endl;
}
}
}
What the heck!!! I just wrote the exact solution yesterday. But didn’t submitted due to optimization part. Thinking about that optimization part. 
After seeing this editorial I’ve just submitted yesterday’s solution and wahh got accepted!!!
@hello_dear It is so because if you only set the precision(6) it will show 1.2345678 as 1.234567 , but for 1.2 it will not show 1.200000 . So showpoint is used to show the trailing zeroes as well and it will show 1.2 as 1.200000 . For more you can refer to this link
1 Like
I believe that this problem could be mathematically invalid and I’ve explained my reasoning here and here. Can a problemsetter please take a look?
2 Likes
rate of mining of gold for both chef and chefu
Chef starts with the mine whose chef’s speed(rate of mining) is maximum and same for Chefu
In your solution , vector b is never used. On both lines 194 and 195, you are deciding the mine from vector a. Since first and second are same at the start, you are always going to enter if(mine1==mine2) this condition. Your else condition is never executed.
I had also submitted a somewhat similar solution except that I was using vector b on Line 195 to decide mine2.
I used different idea for this solution
I didn’t assume this lemma
I think you are still following the lemma, and that is why you have ignored vector b. After that it doesn’t matter whether vector a is sorted or not. So basically it’s the same solution as mentioned in the editorial. I actually got AC over here by just deleting vector b and the else condition.
1 Like
Now I’m feeling bad after looking at the implementation. It was easy after all!!
I don’t agree with the proof given in the editorial. It’s like you are forcing the answer by saying that any change would create problem for one of the miners.
Let me try to give an example test.
1
2
10 1 4
20 3 2
Output according to editorial - 16.00000 14.00000
Output according to actual problem - 14.00000 16.00000
First of all, any miner will choose optimal mine at any point of time according to the maximum gold digging rate available to him from all available non-empty mines.
In the example, let’s see the rate of gold digging of both miners at both the mines.
Mine 1 10(rate of A) 2.5(rate of B)
Mine 2 6.66(rate of A) 10(rate of B)
Now at t=0, it’s quite obvious that they will go in that mine which offers more gold units per unit time.
Up to Day 1, A will dig Mine 1 and B will dig Mine 2.
After Day 1 ends, Mine 1 is empty while Mine 2 has still 10 gold units remaining.
As Day 2 starts, both will dig the same Mine 2 as A has to join B because Mine 1 got emptied on Day 1.
This gives optimal answer 14.00000 16.00000 (after Mine 2 gets empty) which relies on optimal choice at every point of time.
I wasted around 1.5 hrs in this question as I thought my logic was correct but submission was unsuccessful every time.
1 Like
Use long double for better precision.
1 Like
Why?? Because you want that??