GOLMINE - Editorial

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

#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. :expressionless: :expressionless: :expressionless: :expressionless: :expressionless: :expressionless:

After seeing this editorial I’ve just submitted yesterday’s solution and wahh got accepted!!! :expressionless: :expressionless:

@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

@roshan_mehta

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

@taran_1407

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

Refer to this comment of mine.

Why?? Because you want that??

That’s what I thought. But it is not optimal.


anishray042

1m

At any point of time, A or B will have n(<=N) options of non-empty mines.

They have to mine from one of all available mines. Since, they are earning gold per unit time, they will choose the mine with maximum gold rate.

So basically, both of them are trying to earn maximum gold units per unit time.

In the process, it might happen that they may start working in the same mine. In that case, they will work together till that mine gets empty.

Also, I am assuming instantaneous switching of mines which I think I can safely assume.

Why?

One thought is … when Chef mines in A , then chefu thinks that he should also mine from A bcz if he mines in A then chef will get less coins so it is optimal .

1 Like

Each of them wants to gather the maximum amount of gold for himself.

Read the problem statement carefully.

Optimise means maximise. Each of them tries to maximize the gold they mined. That’s what the optimal means. Problem was not poorly written, it looks like you don’t have comfort with game theory. Almost all almost game theory problems use similar statements. It is not something uncommon and poorly written.

1 Like

The one who will end up having less gold would realise this that this strategy is not best for him (since they are playing optimally) and hence he won’t do that.

2 Likes

I don’t know why people think the editorial is unclear. I admit I wasn’t able to prove this in-contest. But the proof of the editorial, it makes perfect sense to me.

Both Chef and Chefu can achieve exactly X and Y, by always taking from the same mine. Now notice that, if Chef tries somehow to take more than X (for example, by taking from a different mine than Chefu), since sum of X + Y is constant, this would lead to less than Y gold for Chefu.

So essentially, Chef can take at least X gold and Chefu can take at least Y gold. And also, neither of them can take more than that, since X + Y is constant, the other guy will not find this optimal(The other guy will switch to the same mine as the first one). So they will take exactly X and Y respectively.

1 Like

Total gold available is X+Y
If one gets X gold then other one will get total-X gold.
Now my claim is both of them will work on same mine at a time. They will never work on different mines.
Because, let’s say they aren’t working on same mine. Now if one of them knows that the other one is getting more gold than expected ( expected = answer given in editorial) then he will start using the mine which the other person is mining. And as a result both will end up working on the same mine. (Or similar mine)

1 Like