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.
So optimising the solution here means that the difference between the gold tally of the two should be minimum??
Atleast that’s what I think
1 Like
It’s not that they “agree” to it. The editorial’s argument is that if they don’t mine the same mine, it will lead to either exactly the same answer or it will be suboptimal for one of them. Then, the best move for the player who it’s suboptimal for is to switch to the same mine as the other, increasing their amount.
3 Likes
Oh yea, got it
1 Like
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.