@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.
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
Yeah , but it might be possible that one of them sees that if he goes to another mine it is profitable and thus he will jump to that mine . The series of jumps of will go on .
1 Like
Well question says
At each point of time, both Chef and Chefu know the gold mine in which the other miner is working.
XD
or u can say that that if chef mines in mine A then Chefu also mines in A not just to gain more gold but he wants that Chef get less gold so he will also work in same mine @l_returns
1 Like
But they will eventually mine and the answer can’t be different that what editorial said. Why will they just shifting instead of mining when they know that they won’t get anything if they just keep shifting without mining.
Both of them knows the truth that they will not get more than what is given in editorial. They will just mine and go away. ( to focus on other business maybe XD)
1 Like
Someone really need to post this problem on math.stackexchange.
1 Like
Is rating change being delayed just because of this problem?
Yes, that’s what I’m trying to say.
If one miner is copying other miner because he will get less gold otherwise, the first will switch to different mine as he knows he will get more gold than what was expected from working in same mine all the time.
This will go indefinitely.
Also, after reading one comment on Codeforces, it suggests that one will try to catch other but it won’t give answer at all.
I think question should have one constraint that one should dig at least some gold to be able to switch to other mine. Then answer would be feasible.
I think the problem is more with the proof than the answer itself. There is no doubt that the answer will be the same as mentioned in the editorial. (if we don’t consider the fact that they keep switching mines in infinitesimal time)
1 Like