GOLMINE - Editorial

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.

2 Likes

Can you define “optimal” ?

If Chef optimises Chefu’s gold decreases and Chef’s increases, and vice versa.

I’d really appreciate any one from the contest admins/editorialists/setters/testers or more importantly “statement verifiers” solve my doubt ?

Because I think the problem was so poorly written, that it should have been rejected during problem submissions. What is the reader supposed to understand by “optimise” ?

IMO, optimise will mean greedily start mining the mine, which gives more profit.

Consider this example:

1
4
10 1 9
20 9 1
40 1 9
50 9 2

for this case, I think, Chefu will go for G4, because he can get 25 units of gold per day, and Chef will go for mine G3, because it’s optimal for him.

So, if they both play optimally, Chef should take away (40+10+2) = 52 and Chefu should take (50+18) = 68 units of gold.

But the “intended” solution gives 64.0909090909091 55.9090909090909

14 Likes

“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.”

@taran_1407 or anyone else please tell how chefu will gain atleast Y units of gold after switching .

If someone has different but concrete proof please share.

1 Like

Getting TLE, can someone point out what to change in this code. Here’s the gist:

typedef long double lld
int main(){
int t; cin>>t;
while(t–){
lld A=0, B=0;
int n; cin>>n; lld g[n]; lld a[n]; lld b[n];
for(int i=0; i<n; i++){
cin>>g[i]>>a[i]>>b[i];
}
for(int i=0;i<n;i++){
A += g[i] * b[i] / ( a[i]+ b[i]);
B += g[i] * a[i] / ( a[i]+ b[i]);
}
cout<<fixed<<setprecision(6)<<A<<" "<<B<<endl;
}

Same doubt

use fast input output.
check this Fast I/O for Competitive Programming - GeeksforGeeks

1 Like

(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)

But they could switch at any instant, so the one in loss would switch immediately. Also if both of them know that working together is optimal for both of them, they would simply start together from any mine. No ??

1 Like

Yes, If it’s optimal for both they would. But if it’s optimal only for one they’ll keep swtiching right ?

“Well, probably you won’t understand anything, because you didn’t try to understand anything in your life, you expect all hard work to be done for you by someone else”

-by um_nik

6 Likes

Yeah. I understand your point, you are saying infinite switching since the one who would be gaining would see it as a loss when the 2nd person would join him. Something like the 2nd person will always follow the 1st person and 1st person would keep moving to get rid of the 2nd person. But this way both of them will end up with 0 0. So I guess 1st person would agree to work together. You may argue it’s a never ending process, I understand that.

3 Likes

You, as the one solving the problem, aren’t optimizing anything. You can reformulate the problem as: for each unit of gold Chef mines, he gains a point, and for each unit Chefu mines, Chef loses a point. Chef wants to maximize his score, Chefu wants to minimize it. Figure out what the final score is.

Now, in your test case, Chef’s best possible (starting) rate is 40/day, but Chefu’s is only 25. So no matter what, as long as Chef can mine at 40/day, Chefu will lose. So Chefu’s best option is to switch to mine 3 and reduce the amount of time Chef can get a rate of 40/day. Then, once that mine is depleted, 25/day will be the best possible rate Chefu can obtain and 20/day is the best Chef can get. So Chef will want to reduce the amount of time Chefu can get 25/day, and so on…

8 Likes

Ya, Makes sense now… Since we want to collect more than 0 gold and maximise we will have to agree to not switch infinitely.

2 Likes

Your explanation seems correct (Chefu trying to reduce Chef’s opportunity to gain)

BUT

The point is when I have 2 outputs, how do I tell which is more optimal, which one is correct.
Shouldn’t we have a clear way to know.

How do I know that 64.0909090909091 55.9090909090909 is optimal form both, the question doesn’t tell clearly what both players consider “optimal”, is it increasing their own collection of gold or does the player also worry about other’s gain, and try to reduce it, at the cost of his own loss.

Because according to your explanation when Chefu moves to mine 3, he loses his opportunity to collect more gold, and thus editorialist’s answer gives less gold to Chefu, which is not optimal, where as my solution gives 68 units to Chefu, so my solution should be more optimal.

At the same time, counter argument would be, my solution gives less gold to Chef than editorialist’s solution. But I’m not arguing over correct/incorrect solutions, my point is THE PROBLEM STATEMENT IS UNCLEAR

3 Likes

There is a total amount of gold in the mines, each unit can only go to one player. So if Chef’s amount increases, Chefu’s amount decreases automatically.

Because according to your explanation when Chefu moves to mine 3, he loses his opportunity to collect more gold

This isn’t true, because when Chefu is done sabotaging Chef, they can both move to the mine where Chefu gets 25/day (so Chefu doesn’t “lose” anything by initially doing the sabotage).

2 Likes

I think I’m getting it now, that optimal means, both of them should get as much as possible, both should maximise their profit, which will only be possible when they mine at the same gold-mine all the time.

I mean both agreeing to mine the same goldmine will be in the best interest for both of them, this is what the setter wanted us to notice.

1 Like

No I don’t. Based on how easy the problem was, no one would have expected that it was a Div 1 second problem. Secondly, the problem was quite unclear too, and that can be proved by the number of correct submissions vs how easy the problem was. And btw, if I expected that all hardwork should have been done by others, I wouldn’t have reached such a stage.