Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### BessieTheCow's blog

By BessieTheCow, 11 days ago, , In CodeChef's June Lunchtime contest today, there was a problem called Gold Mining, which I'll summarise here:

There are a $N$ gold mines, and the $i$th one has $G_i$ units of gold in it. Chef and Chefu can extract gold from the mines at a constant rate. For the $i$th mine, Chef can extract $P_i$ units of gold per unit of time, and Chefu can extract $Q_i$ units of gold per unit of time. Note that time is continuous here, not discrete. Chef and Chefu each can extract gold from one mine at a time, and they can instantaneously move from one mine to another at any point in time. Chef always know where Chefu is, and Chefu always know where Chef is. Chef and Chefu are always trying to maximize the total amount of gold they get themselves. The task is to predict the total amount of gold which Chef will mine and the total amount of gold which Chefu will mine if Chef and Chefu act optimally.

The solution in the editorial goes like this:

Let $X = \sum_i G_i P_i / (P_i + Q_i)$ and $Y = \sum_i G_i Q_i / (P_i + Q_i)$. $X$ and $Y$ are the amounts of gold which Chef and Chefu will get if they are always in the same mine. Clearly, the sum of the amount of gold which Chef and Chefu will mine is equal to the total amount of gold in the mines. Assume that Chef and Chefu are in different mines at some point. If Chef will get at least $X$ units of gold continuing in this state, then Chefu will get no more than $Y$ units of gold this way. Therefore, it is always optimal for Chefu to move to the mine which Chef is in so that Chefu gets $Y$ units of gold and Chef gets $X$ units of gold. Similarly, if Chef will get no more than $X$ units of gold continuing in this state, then it will be optimal for Chef to move to the mine which Chefu is in so that Chef gets $X$ units of gold and Chefu gets $Y$ units of gold. Therefore, if both Chef and Chefu act optimally, they will always be in the same mine, and the answers are $X$ and $Y$.

I believe that this proof is invalid, and I will now attempt to demonstrate why. First of all, I'll state how I'm interpreting the editorial's proof a bit more formally:

Assume that at some time $t$, Chef and Chefu are in different mines. Let $X'$ and $Y'$ be the amount of gold which Chef and Chefu will get respectively if Chef and Chefu do not move into the same mine at time $t$. If $X' \geq X$, then $Y' \leq Y$, therefore it is optimal for Chefu to move into the mine that Chef is in, because Chefu will then be able to get $Y$ gold instead of $Y'$ gold. If $X' \leq X$, then it is optimal for Chef to move to the mine which Chefu is in so that he can get $X$ gold instead of $X'$ gold. Therefore, the optimal strategy for both Chef and Chefu is to always be in the mine which the other person is in, and they will get $X$ and $Y$ gold.

This proof assumes that if Chef and Chefu move into the same mine at time $t$, then they will get $X$ and $Y$ units of gold. However, the problem is that Chef and Chefu can still move to a different mine afterwards in the same instant. Let's say at time $t$, $X' \leq X$ so Chef moves into the mine which Chefu is in. The proof assumes that this will result in Chef getting $X$ gold and does not rule out the possibility that Chefu can move to a different mine in the same instant. In fact, the claim that it is always optimal for Chefu to not move to another mine immediately after Chef moves is the exact same as the statement that is supposedly proved, because the positions of Chef and Chefu at a given instant doesn't actually matter. We all know that the proof of the statement can't contain the assumption that the statement is true.

To think about it another way, the proof in the editorial is claiming that Chef can ensure that he is always in the same mine as Chefu, because he can move into the mine which Chefu is in at any moment. However, using the same logic we can conclude that as long as there are at least two nonempty mines, Chefu can ensure that he is always in a different mine than Chef by moving as soon as Chef moves into his mine. As far as I can tell, if Chef and Chefu are in different mines for any nonzero amount of time, the outcome would change.

So this is why I believe the proof in the editorial for this problem is invalid. I suspect that this problem is actually unsolvable, just like how it makes no sense to try to predict the outcome of a game where one player wants to make a bit 1, the other player wants to make it 0, and both players can instantaneously flip the bit at any moment. I haven't been able to find a rigorous proof of this though. I'm not sure how to even define "optimal" for this problem. What do you think about this? If anyone has a rigorous proof, please share it.

Link to same post on codechef: https://discuss.codechef.com/t/is-the-problem-golmine-invalid/70104?u=feixiang  Comments (38)
 » I had the same doubt but as pointed by the user over here, the goal is to maximize the total obtained gold for each person. If Chefu moves into the same mine as Chef to reduce his/her loss, Chef can move into a different mine at the same instance but if this leads to infinite switching, they will not have collected more gold than what they already have. Since the goal is to maximize the gold, neither of them can be greedy and keep switching and one of them is forced to let the other mine in the same gold mine in order to increase their gold.We can still argue that the one trying to get away from the same mine will not compromise and the other guy can compromise for a lesser gold than what he/she gets from mining at the same place so I'm still not entirely sure of the explanation but as pointed by the user in the discuss forum, at least one of them must compromise in order for both of them to get more gold and it makes some sense for the one who is greedy to compromise than the one who will get lesser gold.
•  » » It's a constant-sum game, so I don't think the idea of compromise makes any sense at all. I think the problem is that it's just not mathematically valid to try to predict a game like this, just like how it's not possible to predict the outcome of the bit flipping example that I mentioned.
•  » » If the switches are instantaneous, it doesn’t make sense to say that infinite switching is like a stalemate in which no one gets any more gold. It all happens in a total of 0 time, anyway; it is just undefined behavior like the quantity 0/0, it isn’t as if it is something undesirable to both players in which everyone loses.In this situation, compromising seems meaningless: you don’t lose anything from just switching one more time.
•  » » » Ya, makes sense .. and as you mentioned below there may not be infinite switching since it may be better for the one following to stop following once they reach a particular mine.
•  » » » I understood what you are saying. We don't lose anything from switching one more time but we aren't gaining either. The final outcomes of the 2 situations are - If they keep switching both will have 0 gold at time 0 If the one player compromises, both will have X and Y > 0 gold at some time t. So the player with less gold would not compromise because since he can't win but he is ensuring that the other one will suffer a loss greater than his loss.While the player with more gold can't win in infinite switching but if he goes for infinite switching, he'd be in more loss as compared to the one with less gold. He will suffer more loss than he will be able to affect on the other one. So why wouldn't he compromise??
 » Careful when you speak against Codechef ! Their control freak/dumb Codechef_admin might delete your codechef account if anything doesn't go according to their plan
•  » » Yeah, they are strict but I don't think they will delete his handle just because he pointed out some error. They are against the handles who dare to speak against there long challenge don't know why they love long so much
•  » » » 11 days ago, # ^ | ← Rev. 2 →   They deleted my account which was my 2+ years of hardwork and effort, ** poof ** all gone in a minute, just because i said "long contests are getting crappier recently".I'm never coming back to that shitty platform ! I hope the someone in authority at codechef takes some action against the person behind the admin. He acts like the wisest person on the Codechef (and indians take his word for granted) and is in fact a Dogmatic old guy
•  » » » » Seems extreme if this is in fact true. Could you provide the exact message you posted regarding long challenge? If it is just "long contest are getting crappier", I doubt anyone would delete your account! I just find it hard to believe as the admins I've encountered are knowledgeable and pragmatic.
•  » » » » » Who is this admin btw? Is he a competetive programmer ? Has he ever qualified for World Finals? Codejam ? or even won any prestigious contest? Can he even solve problems of his own contest?I think he got job into codechef by boasting his Codechef stars lmao I won't call a person knowledgeable and pragmatic only because we share same nationality !Afaik MikeMirzayanov has won two silver medals at the ACM-ICPC World Finals. He is a competetive programmer himself, maybe that is one of reason why codeforces is way better than codechef.So downvote me if u want, but its true codechef is not credible anymore
•  » » » » » » 11 days ago, # ^ | ← Rev. 2 →   Please don't disrespect someone you don't know. Btw for your answer, the admin of codechef is Red here on codeforces. Now you might get that he has enough knowledge. P.S.- Didn't mention him as it would be unnecessary spamming
•  » » » » » » » 11 days ago, # ^ | ← Rev. 2 →   When did blue became red? r u colorblind?Trying not to generalize the whole country, but you guys are crazy man ! You will probably accept any sort of Bullsh*t if it is covered in patriotism.And i had to go under an alt, because i read somewhere on quora how indians harrased a professor and his family just because he said indian exams are easy!So yeah quite a reputation you guys have made for yourself
•  » » » » » » » » 11 days ago, # ^ | ← Rev. 2 →   Again I say, check your facts before commenting. The admin of codechef is Cache . vijju123 is moderator of codechef
•  » » » » » » » » » Respect buddy.
•  » » » » » » » » » No Cache isn't the admin of codechef.
•  » » » » » » » » » orz CacheBut he's an occasional editorialist and problem setter and sometimes admin of contests, but he is not the admin of codechef u dumbo
•  » » » » » » » » What are you saying man? You just generalized the whole country by saying that.You think Indians accept any sort of Bullshit covered in patriotism? Wow!You know nothing about Indians, there are fools in every place of the world. This does not mean we speak like that for their whole country.But I can see you made a new ID just to say bad things about Indians, and you know what? You don't matter and it doesn't matter what you say. So bye bye Cutie, keep saying bad things about India...it's not going to change anything.
•  » » » » » » » » » You think Indians accept any sort of Bullshit covered in patriotism?According to my calculations its true for atleast 50% Indians
•  » » » » » » 11 days ago, # ^ | ← Rev. 3 →   I never mentioned that I thought he was pragmatic due to his nationality. I was just mentioning the fact that different people have had different experiences :) In response to the first part of your question, the admin/mod I was referring to and (the only one I know of) was vijju123 who is in fact a very good programmer:) Codeforces has better credibility, yeah I agree but nonetheless, I quite enjoy competing on codechef. I was just really surprised that someone got their account deleted due to criticism of long. It just does not seem rational.
•  » » » » Please share the username which you claim was banned for this. There are multiple admins who could have banned your account, but I am certain that there is no chance of events having transpired as you portray it. Even on our forum, no thread is closed just because it criticizes CC. In fact, our moderators are instructed to reject all community flags on such threads. A fresh troll account could be banned for a minor violation if we are positive that it is a duplicate account, but banning an account which has been active for a non-trivial amount of time would happen only rarely — probably some blatant cheating, or repeated abusive behavior. Anyway, just share your username and we'll see what the issue was.
•  » » » » » Ae madherchod sale bhosadi wale tumlog salo ek baar gujraat aa jao, bhen k lodo, agar maar maar k gand na faad diya na toh dekhna lodu salo. Sale jis codechef k office me muth maar raha hai na sale usi me ghus k jo pelunga na salo ki gand me se pura rajdhani express paar hoke jayega
•  » » » » » » That sounds lovely! It's a date then, the next time I get to Gujarat :)
•  » » 11 days ago, # ^ | ← Rev. 2 →   I remember once a problem with wrong intended solution was put on codeforces . Codforces changed the problem and after that gave option to get out of rating changes .Mike even made a blog and discussed about it (all this happened just after the contest).But on codechef , till now there is no official announcement on this.They can't handle even 2 short contests . They mess up with important contests like ICPC every year (ICPC India online should happen on codeforces) . They make long problem statements intentionally despite knowing English is not first language of Indians. Cheaters and people who make meme are / were top contributors on codechef . Problem setters themselves do plagiarism on codechef .
•  » » » Cheaters and people who make meme are / were top contributors on codechefThis is so true lmao, there are some really good orz-able indians who are red here, and they too stay away from Codechef lmao
 » I'm not sure if the problem is invalid, but I think the editorial's proof is certainly incomplete due to the bit analogy issue you mentionedI suspect that at any moment of the game, one of the guys has a dominant strategy (in other words, they have a mine such that switching mines wouldn't make them better off regardless of what the other guy did), and the other guy's just a dumbass if they don't followThis would imply that there could never exist a scenario in which the two guys had a conflict of interest with regard to being in the same mine or notBut also it seems that this entire issue could've been avoided if there was some constraint like "the guys can only switch mines every second" or something lol
•  » » Over on Codechef we figured that if there was some "reaction time" $r$ such that the moves have to be a minimum of $r$ units of time apart, then the outcome would approach $X$ and $Y$ as $r$ tends towards 0. But I don't know if it's right to say that the outcome is exactly $X$ and $Y$ when $r$ is exactly 0.
 » Yeah, I agree the proof is definitely faulty. The solution the proof gets you to seems at least somewhat reasonable though. (I’ll explain below) The question I have though is that is it really true that the optimal mines aren’t transitive? Like if I am at mine 1, and you come to mine 1, now I can switch to mine 2. If you come to mine 2, maybe I can go to mine 3. Could it really be the case that I would always want to be at some mine you aren’t at, rather than just at mine 3, then if that is empty at mine 2, otherwise at mine 1?If some player can come up with some optimal ordering that doesn’t depend on the other player. The other player can always guarantee they get an ‘even split’ of each mine, no matter how player 1 would play on his own. In games where both players can prevent the other from winning, it usually makes sense that is a tie.
 » I see your point that both players can choose to switch infinitely because it is an instantaneous process. However, mining gold by definition is non-instantaneous. Let dt be the period of time for which a player mines gold. If at the starting of this period, the other player decides to join in and mine in the same mine, there is nothing the first player can do to change that.To state a bit more formally, there will not exist a non-zero interval of time in which the miners are not in the same mine if at least one of them wants to be in the same mine."To think about it another way, the proof in the editorial is claiming that Chef can ensure that he is always in the same mine as Chefu, because he can move into the mine which Chefu is in at any moment."False. The proof in the editorial is claiming that for any non-zero (non-instantaneous) interval of time, Chef can obtain the gold from the same source as Chefu, because he can move into the mine which Chefu is in at the initial moment. I have explicitly replaced "in the same mine" with "obtain gold from the same mine" to emphasize the fact that moving to the same mine is instantaneous while mining gold is not.I think your bit game analogy is useful so I will use it to further illustrate my point. Just like you cannot guarantee whether the bit will be 1 or 0 in the end, I agree you cannot guarantee both players will be in the same mine or different (because you can prove both with the same argument you gave) at any moment in time. But for any interval in which player A is in mine M, player B can also be in mine M for that interval if he chooses to do so.
 » 11 days ago, # | ← Rev. 11 →   Let $eps$ be a very small interval time. The first player will work on any available mine for the first $eps$ time.Repeat: If the second player did nothing in previous $eps$ time, then he will continue picking any mine to work for next $eps$ time. Otherwise, imitating the second player (until the mines are empty).Be the way he does that, the first player can get an amount of gold in any mine at least ($\frac{G\cdot B}{A+B} - eps_2$) ($eps_2$ depends on $eps$). Let $X$ be $sum{\frac{G_i\cdot B_i}{A_i + B_i}}$, $Y$ be $sum{\frac{G_i\cdot A_i}{A_i + B_i}}$So for any arbitrary $eps$ the first player will have a strategy to get $X - eps$, same for the second player $Y - eps$, so the optimal (if any) for the first player will fall into $(X - eps, X + eps)$ for any small $eps$. Also, tolerance is $10^{-6}$ so can't we output $X\ Y$?I think there should be very small like $10^{-18}$. Adding constraint: each player works only on a mine in $(k\cdot 10^{-18}, (k + 1)\cdot 10^{-18})$. By that, the existence of optimal strategy is obvious.
 » I think if they can switch mines in zero time it is that they are not only in one mine, but in a set of mines at any point of time. If the strategy of one of them is to be in the same mineset as the other one then it is that they are both in the same mineset. This will end in same solution as the tutorial.
 » 11 days ago, # | ← Rev. 3 →   Since the problem is with infinite switching, if we prove that it's not optimal for the first person to switch infinitely in order to get away from the second guy mining in the same place we won't have the problem.Let's say the guy trying to avoid the other guy mining at the same place is Chef and other guy is Chefu. So, If we have 2 mines $i, j$. Mining at the same place should give less gold to Chef than both Chef mining at 1, Chefu Mining at 2 and Chef mining at 2, Chefu Mining at 1. Because if only one of them is better for Chef, Chefu does not need to follow Chef when Chefu reaches the mine optimal for him/her.Let us say the mines are $G_1, a_1, b_1$ and $G_2, a_2, b_2$.If both mine together Chef gets $\frac{G_1b_1}{a_1 + b_1} + \frac{G_2b_2}{a_2 + b_2}$Case 1: Chef at mine 1 and Chefu at mine 2. Subcase 1:$a_1 < b_2$Chef gets $G_1 + \frac{G_2(b_2 - a_1)}{b_2}\frac{b_2}{a_2 + b_2}$ gold which is equal to $G_1 + \frac{G_2(b_2 - a_1)}{a_2 + b_2}$For this to be greater than when they work together:$G_1 + \frac{G_2(b_2 - a_1)}{a_2 + b_2} > \frac{G_1b_1}{a_1 + b_1} + \frac{G_2b_2}{a_2 + b_2}$$\frac{G_1a_1}{a_1 + b_1} > \frac{G_2a_1}{a_2 + b_2}Thus, \frac{G_1}{a_1 + b_1} > \frac{G_2}{a_2 + b_2} Subcase 2:a_1 \ge b_2Chef gets \frac{G_1b_2}{a1} + \frac{G_1(a_1 - b_2)}{a1}\frac{b1}{a1 + b1} gold.For this to be greater than when they work together:\frac{G_1b_2}{a1} + \frac{G_1(a_1 - b_2)}{a1}\frac{b1}{a1 + b1} > \frac{G_1b_1}{a_1 + b_1} + \frac{G_2b_2}{a_2 + b_2}$$\frac{G_1b_2}{a_1 + b_1} > \frac{G_2b_2}{a_2 + b_2}$Thus, $\frac{G_1}{a_1 + b_1} > \frac{G_2}{a_2 + b_2}$So, In both subcases $\frac{G_1}{a_1 + b_1} > \frac{G_2}{a_2 + b_2}$ in order for Chef to mine at 1 if Chefu follows Chef to 2.Similarly, if we compute the relation for Case 2: $\frac{G_1}{a_1 + b_1} < \frac{G_2}{a_2 + b_2}$ in order for Chef to mine at 2 if Chefu follows Chef to 1.They both contradict each other and hence Chef cannot infinitely switch since it would actually lead to him getting lesser gold
 » We can prove by invariant:let's define $W(t)$ as function denoting the amount of gold Chef's has gathered when time is $t$, clearly before the game start we have $W(0) = 0$ (Note chef is the one who finish's i-th gold mine in $A_i$ time and Chefu finishes in $B_i$ time)let's define $g_i(t)$ as the amount of gold that i-th gold mine still has in time $t$, clearly before the game start we have $g_i(0) = G_i$let's define another function of time $H(t)$ which is equal to $H(t) = W(t) + \sum_{i}{g_i(t) \cdot \frac{B_i}{A_i + B_i}}$, before the game start we have $H(0) = \sum_{i}{G_i \cdot \frac{B_i}{A_i + B_i}}$Fact 1: Chef can play in a way that $H(t)$ never decreases by time. Fact 2: Chefu can play in a way that $H(t)$ never increases by time. proof: We know that if Chef was mining i-th gold mine for very tiny amount of time $dt$ then amount of gold he will gather is $\frac{G_i}{A_i} \cdot dt$, so the increase of $W(t)$ will be $dW(t) = \frac{G_i}{A_i} \cdot dt$ and decrease in $g_i(t)$ will be $dg_i(t) = -\frac{G_i}{A_i} \cdot dt$, let's put those in formula of $H(t)$ and see how much it will change:$dH(t) = dW(t) + dg_i(t) \cdot \frac{B_i}{A_i + B_i}$$dH(t) = (\frac{G_i}{A_i} -\frac{G_i}{A_i} \cdot \frac{B_i}{A_i + B_i})\cdot dt$$dH(t) = (\frac{G_i \cdot (A_i + B_i) - G_i \cdot B_i}{A_i \cdot (A_i + B_i)} )\cdot dt$$dH(t) = (\frac{G_i \cdot A_i}{A_i \cdot (A_i + B_i)} )\cdot dt$$dH(t) = (\frac{G_i}{A_i + B_i} )\cdot dt$which means that if chef mined i-th gold mine for $dt$ then $H(t)$ will increase by $(\frac{G_i}{A_i + B_i} )\cdot dt$, obviously Chef should greedily pick the gold mine with maximum $\frac{G_i}{A_i + B_i}$ to maximize the increase in $H(t)$, but we still need to consider the change caused by Chefu. we know if Chefu gathered from i-th gold mine for duration $dt$ then $W(t)$ will not change because by definition it's what Chef gathered not Chefu, but $g_i(t)$ will decrease by amount $dg_i(t) = -\frac{G_i}{B_i} \cdot dt$, so let's see the change of $H(t)$$dH(t) = dW(t) + dg_i(t) \cdot \frac{B_i}{A_i + B_i}$$dH(t) = 0 -\frac{G_i}{B_i} \cdot \frac{B_i}{A_i + B_i} \cdot dt$$dH(t) = -\frac{G_i}{A_i + B_i} \cdot dtclearly we see that Chefu should pick the gold mine with maximum \frac{G_i}{A_i + B_i} to maximize the decrease in H(t).the total change on H(t) made by both Chef and Chefu is (\frac{G_i}{A_i + B_i} -\frac{G_i}{A_i + B_i}) \cdot dt = 0which means H(t) will never change from the beginning of the game until the end. let's recall definition of H(t)$$H(t) = W(t) + \sum_{i}{g_i(t) \cdot \frac{B_i}{A_i + B_i}}$since in the end of the game all mines will be empty so $g_i(t) = 0$ which means in the end of the game we have $H(t) = W(t)$, and since $H(t)$ never changes we conclude that $W(t) = H(0) = \sum_{i}{G_i \cdot \frac{B_i}{A_i + B_i}}$Summary:the optimal strategy is to always gather gold from the mine which has maximum $\frac{G_i}{A_i + B_i}$, and this means that Chef and Chefu will always gather from the same mine, unless there are multiple maximums, and in this case Chef and Chefu can be gathering from different mines but it doesn't change the final answer.
•  » » I think you've got a valid proof there, thanks for settling this!
•  » » 10 days ago, # ^ | ← Rev. 2 →   What if Chef and Chefu switch mines at every instant though, such that there is never a nonempty time interval where they stay in place? Is that "possible"?
•  » » I have not studied game theory in depth, so that might be the reason but I have a doubt about what the problem is asking us to find in the first place.When there's a perfect information game, we can formulate a "strategy" as a decision tree right? In that case, we can well-define what the "best" move of a player is mathematically. Decision tree also carries the image of how we make a decision in normal life.We can't do that for this problem. Even though the statement sounds like a normal game theory problem, its mathematical specification widely differs from what CPers usually encounter, and such specification necessarily involves dealing with continuous space, which seems very counter-intuitive since our usual image of a "strategy" is a discrete process.In short, I think the problem is unclear, at least for me, on how to mathematically interprete a continuous game, and I doubt most of the people who solved it knew it either.
•  » » » I think there is a field of study revolving around determining whether infinite games have winning strategies, but I'm not familiar with it at all. I don't know if it even applies to this game. Like I said before I don't know how to precisely define "optimal" for this game.
 » I too think that explanation is wrong. If one player wishes to always extract in same mine as other and other in different than how is it possible even though their claim suggests that both things are possible simultaneously. However I think the problem and answer are still correct. Lets say $G_iP_i/(P_i+Q_i)$ gold in mine $i$ belongs to chef. If chef is taking gold at rate $P_i$ from mine $i$ than he is taking chefu's gold at rate $P_iQ_i/(P_i+Q_i)$ because for any amount $x$ he takes, $xQ_i/(P_i+Q_i)$ belongs to chefu. To maximize his gold, chef wants to maximize (the amount of gold he steals) $-$ (the amount of gold chefu steals). Hence, both chef and chefu will mine gold from mines in decreasing order of $P_iQ_i/(P_i+Q_i)$. Therefore since both are stealing at same rate none of them will steal anything effectively.
 » 8 days ago, # | ← Rev. 2 →   My solution is https://www.codechef.com/viewsolution/34889657 I am getting a TLE. Can anyone please explain why?