GOLMINE - Editorial

No. Consider this case:

1
2
4 1 2
4 2 2

If Chef takes mine 2 and Chefu takes mine 1, then they can make it 50/50 (and the difference would be 0). But Chef can do better and increase his own score by starting on mine 1, while Chefu has no such option.

Thanks!!

Got it. Thanks a lot

My Idea was simple that both were greedy and could not see each other digging gold in other mines. So they would run to the same mine and would try to get best out of that mine for themselves.

Why will you waste your maybe precious time in replying and justifying yourself to a stranger and that too at such such a trivial point.

Chill dude… there’s nothing wrong in saying that problem statement was unclear. In fact I have also several times said the same thing on codeforces but that was before I read this.

Just relax buddy and next time, whenever you find the problem statement difficult, just read it slowly and with some pen-paper, examples and dry-run, understand it and then proceed with the logic. It will be very beneficial.

3 Likes

Yeah, I realized that at the end of the competition. But I am not feeling that bad too coz I just got an end minute AC (using a pen and paper). Just the difference was of 50 points :slight_smile:

I was stuck at the 5th question (Sum of Square Submatrices one) because everytime, I was thinking of an O(N^3) code. Then, I realized that the 3rd dimension could have been minimized to O(N^2logN) using binary search. I was neither happy (coz of this question) nor sad (for the 50 points) at the end.

1 Like

Even I thought of this approach. But I was stuck at the case where suppose the maximum of both will come to same mine. Then their actual maximum will decrease. Hence I couldn’t come up with a solution.

This post was flagged by the community and is temporarily hidden.

exactly! it was the 4th question in Div B, so I thought it must be hard. Seeing that it has such a simple solution, feels so bad.

they will both work together in each mine, and will move to the next mine after the previous mine has no gold left.
Since they will both work together at any particular time, thus there is no need to sort the mines.

1 Like

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

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

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 .