GOLMINE - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Tester: Trung Nguyen
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Observations

PROBLEM

Chef and Chefu work as gold miners. There are N gold mines numbered from 1 to N, i-th mine having G_i gold. If Chef alone works in mine numbered i, it’d take him A_i days to completely mine it. Similarly, if Chefu alone works in mine numbered i, it’d take him B_i days to completely mine it.

Find the maximum amount of gold each miner can mine if both mine optimally.

QUICK EXPLANATION

  • Both Chef and Chefu always work in the same gold mine till it is empty, so we can consider each gold mine independently and divide gold in ratio B_i: A_i among Chef and Chefu.
  • We don’t even need to obtain the order of mining since this sum remains same for each order.

EXPLANATION

Firstly, Let’s denote P_i = G_i/A_i and Q_i = G_i/B_i denote the amount of gold Chef and Chefu mines from i-th mine in a day.

Now, let’s assume X and Y denote the total gold Chef and Chefu respectively can collect if both of them work in same mine at all times.

Lemma: Chef and Chefu always work in the same mine at all times in the optimal choice of mines.
Proof: Suppose, at some time, Chef and Chefu are working in the different mine, and Let’s say Chef is about to get more than X gold (implying Chefu would get less than Y gold). Then Chefu can always switch to the mine Chef is working, to gain at least Y units of gold, which is the optimal choice for Chefu.

Similarly, if Chefu is about to get more than Y gold (implying Chef would get less than X gold), then Chef would immediately switch to mine the same as Chefu, to obtain X gold, which is the optimal choice for Chef.

Hence, we can see that in the optimal choice by both Chef and Chefu, they would always work in same mine, till it’s empty.

So, all we need to do is to calculate the values of X and Y, which shall be our required maximum amount of gold Chef and Chefu can mine.

For some mine i, in one day, P_i+Q_i gold is mined, Chef and Chefu works in this mine for \displaystyle \frac{G_i}{P_i+Q_i} days. Hence, Chef mines \displaystyle P_i*\frac{G_i}{P_i+Q_i} and Chefu mines \displaystyle Q_i*\frac{G_i}{P_i+Q_i} from i-th mine. So, we take this sum for all mines.

TIME COMPLEXITY

The time complexity is O(N) per test case.

SOLUTIONS

Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
 
 
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
		
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
 
 
int T;
long long G[100100];
long long A[100100],B[100100];
int n;
 
int main(){
	//freopen("02.txt","r",stdin);
	//freopen("02o.txt","w",stdout);
	cout.precision(13);
	cout<<fixed;
	T=readIntLn(1,10000);
	while(T--){
		n=readIntLn(1,100000);
		for(int i=0;i<n;i++){
			G[i] = readIntSp(1,100000);
			A[i]= readIntSp(1,100000);
			B[i] = readIntLn(1,100000);
		}
		long double a=0,b=0;
		for(int i=0;i<n;i++){
			a += G[i] * B[i] / (long double) ( A[i]+ B[i]);
			b += G[i] * A[i] / (long double) ( A[i]+ B[i]);
		}
	
		cout<<a<<" "<<b<<endl;
	}
	assert(getchar()==-1);
} 
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int) 1e9 + 23111992;
const ll LINF = (ll) 1e18 + 23111992;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int mrand() {return abs((int) mt());}
inline int mrand(int k) {return abs((int) mt()) % k;}
#define db(x) cerr << "[" << #x << ": " << (x) << "] ";
#define endln cerr << "\n";
 
void chemthan() {
	int test; cin >> test;
	assert(1 <= test && test <= 1e3);
	int sumn = 0;
	while (test--) {
	    int n; cin >> n;
	    sumn += n;
	    assert(1 <= n && n <= 1e5);
	    assert(1 <= sumn && sumn <= 1e6);
	    double x = 0, y = 0;
	    FOR(i, 0, n) {
	        int g, a, b; cin >> g >> a >> b;
	        assert(1 <= g && g <= 1e5);
	        assert(1 <= a && a <= 1e5);
	        assert(1 <= b && b <= 1e5);
	        x += (double) g * b / (a + b);
	        y += (double) g * a / (a + b);
	    }
	    cout << prec(9) << x << " " << y << "\n";
	}
}
 
int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0), cin.tie(0);
	if (argc > 1) {
	    assert(freopen(argv[1], "r", stdin));
	}
	if (argc > 2) {
	    assert(freopen(argv[2], "wb", stdout));
	}
	chemthan();
	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.DecimalFormat;
class GOLMINE{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int N = ni();
	    double ans1 = 0.0, ans2 = 0.0;
	    for(int i = 0; i< N; i++){
	        double G = nl(), A = nl(), B = nl();
	        double sp = 1/A+1/B;
	        ans1 += (G/sp)*(1/A);
	        ans2 += (G/sp)*(1/B);
	    }
	    DecimalFormat df = new DecimalFormat("0.000000000");
	    pn(df.format(ans1)+" "+df.format(ans2));
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new GOLMINE().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

19 Likes

Considering it a Div1 B question, I expected it to be a lot harder than this. Just having this expectation and thinking too much about that “optimally” part spoiled the question for me. If this question would have been a DIV2 B, there would have been almost twice the number of correct submissions on it. But yeah, great question. It teaches you that sometime you don’t have to think so much.

62 Likes

Poor sentence construction. Please make sure that the question can be understood by any person who does coding, and thus, is in the simplest form. Nobody wants to play with words here!

15 Likes

I might not able to sleep due to this question

37 Likes

https://www.codechef.com/viewsolution/34818317
I submitted this solution and got wrong answer. after the contest i saw other submissions, and the difference between my answer and other answer was that, other answer had, set the precision of 8, using setprecision(8), so when i added this line to my answer i got AC.
In the question it was written that -

Your answer will be considered correct if the absolute or relative error of each amount of gold does not exceed 10−6

but even if my answer is 10 instead of 10.000000, even then the relative or absolute error is less than 10^-6, then why did I get Wrong Answer.

1 Like

10 is different from 10.000000

Try printing a large number, like 1 billion, without any setprecision (locally), and see what happens

7 Likes

After this editorial many users got -

Screenshot_2020-06-27-kidney-me-heart-attack-meme---Google-Search.png

32 Likes

Because by default, double values print decimal points upto 2 places. Thus, your answer would have been correct if the absolute error did not exceed 10^{-2}. Using setprecision(8) makes the answer print upto 8 decimal places. That is the difference.

1 Like

Both of them are trying to maximize their gold, so wouldn’t it be optimal to go to a mine where the gold digging rate g/a (or g/b) is maximum ?

16 Likes

No. Default precision is 6 significant figures. Note that significant figures are different from decimal places.

1 Like

Even I did same mistake cout takes scientific notation by default for large values so it might fail there

@aryan12 @galencolin @hetp111 Ok, i got it now.

1 Like

By significant digits do you mean the values in before the decimal point too? Because usually I have noticed that on my terminal they print 2 decimal places. Maybe I have my facts wrong, thanks for correcting me.

I understand the idea behind this, but does this problem really make sense mathematically? The proof says “Suppose, at some time, Chef and Chefu are working in the different mine, and Let’s say Chef is about to get more than X gold (implying Chefu would get less than Y gold). Then Chefu can always switch to the mine Chef is working, to gain at least Y units of gold, which is the optimal choice for Chefu.” But the problem is that at Chef can move to a different mine at the same instant, so you end up with Chef and Chefu switching mines at an infinite rate. The idea is that both Chef and Chefu have the ability to force the outcome to be X and Y, but I think that might not be mathematically correct.

To illustrate my point, let’s say we have a single bit that is either 1 or 0. At any moment in time Chef and Chefu can instantaneously flip the bit. Chef wants to maximize the total time when the bit is 1 and Chefu wants to do the opposite. What will be the outcome after one hour then if both Chef and Chefu play optimally? Using a similar argument to the one in the editorial, you could say that Chef can make the bit 1 any time it is 0, therefore Chef will win. But this obviously isn’t valid. With the gold mines, if Chef always switched to whatever mine Chefu was in, Chefu can always move to another mine whenever Chef is in the same mine. Therefore the outcome is indeterminate.

29 Likes

Yes. Significant figures counts the number of digits of precision after and including the first nonzero digit.

1 Like

Not really satisfied with the editorial…needs more clarification with the proof of the lemma

7 Likes

This is better…

I have been scammed

Hi Guys try this video Solution,:raised_hands::raised_hands:
Hope it helps.

1 Like