Is the problem GOLMINE invalid?

But can’t we apply the same limit argument to show that there is a defined outcome? Any advantage Chefu will get by evading Chef will be of the form c \cdot r, where c is some constant based on the input. This is definitely not indeterminate, and thus tends to 0 as r does.

edit: maybe c is more complex than a constant, as the mines deplete. But it should still be just some function of the input that doesn’t depend on r.

Okay, I agree with you that there may not be a defined outcome. To be honest, my intuition with this weird type of continuity isn’t strong enough to tell. But we also shouldn’t immediately conclude that there isn’t one, unless you can prove so or concretely prove its similarity to the bit problem (or something similar). I’m starting to doubt myself like crazy, so it definitely shouldn’t be me.

Can we get @taran_1407, @kingofnumbers, and/or @chemthan (or someone else, too) to resolve this?

2 Likes

I used the bit problem just to illustrate that a game where players can make instantaneous moves at any time may not have a defined outcome. I think it may be similar if we define the outcome as the total time that the bit is 1, after the game continues for some fixed amount of time. One player wants to maximize the outcome and the other player wants to minimize it. The outcome would approach half of the total time as the reaction time approaches 0, but I don’t know if it’s correct to say that the outcome is exactly half the total time when the reaction time is exactly 0.

An issue with the bit problem is that there are multiple conflicting ways to define it, too. For example, let r instead be the time that a player must spend between their own moves, rather than as a reaction. As r tends to 0, it models the same game, but the limit evaluates to 1 (because the player who starts off with the bit in their favor can always instantly counter their opponent) (1 meaning 100% of total time). And the way you choose to define r leads to the outcome being \frac{1}{2}.

1 Like

the solution will still be uncertain for the second interpretation as say r be infinitesimally small dt say what if i other player changes it at T-dt time .(I am not sure tho i am having trouble properly defining this game)

I agree. But I should point out, there’s a distinct difference between a limit and an actual value. Take any function with a removable discontinuity:

(example)

image

We can say \lim\limits_{x \to 2}{f(x)} = k (whatever k is), but f(x) is certainly not k - it doesn’t exist. Nonetheless, if the limit for f(x) doesn’t exist, then f(x) definitely doesn’t either (and in the bit problem’s context, it’s indeterminate).

Yeah, that’s what I meant when I said “I don’t know if it’s correct to say that the outcome is exactly half the total time when the reaction time is exactly 0.” Maybe there’s some other way to make sense of it, but the limit isn’t a rigorous proof.

What if we frame it this way for any time interval dt chef will have to choose a set of mines he works in that period and since both players are rational no matter what set chef chooses chefina can always choose the same due to each player know what other player will do.

Many people just wrote the solution for n=1, and submitted and got 100 points, without even thinking the details. This was the reason why there were a huge number of submissions on the problem. Many people wasted their time on this problem. :disappointed:

Don’t be so serious, it is a just puzzle, fictional puzzle. Many CP problems are fictional, why you care much about its reality? Let X, Y be fictional optimal for two players. Then the first player always has a strategy to get (X - EPS) with any arbitrary EPS , the same for the second player, always ensure to get (Y - EPS) and our tolerance is 1e-6?

1 Like

The issue was with the case when both of them refuse to work each other as a strategy i cannot figure out how will it converge

1 Like

Here’s an idea: Assume there’s 2 mines for simplicity. Define a strategy as a function that takes two nonnegative real numbers G_0 and G_1 and returns 0 or 1 indicating which mine the player should be in when one mine has G_0 units of gold left and the other mine has G_1 units of gold left. Let’s say that one player uses strategy f and the other uses strategy g. Define h(i, t) as the amount of gold left in the i th mine after t units of time if the players follow their strategy functions. Then h(i, t) can be expressed in terms of \int_0^t (f(h(0, x), h(1, x)) + g(h(0, x), h(1, x))) dx (I think).

What ? can u give solution link like this .

The two player try to maximize their mine, so if they idle, they get nothing, then should they idle?

2 Likes

Bro, for n=1, they have only one mine, and will work in that simultaneously. Working together is the answer to the whole problem.

Bro , I also did same :slight_smile: and got AC ( see my submission)

Yeah, that was the reason why the 4th problem in div2 had so many submissions. :sweat_smile:

Can it be proven that the players can force the outcome to be arbitrarily close to X and Y though?

@anon30011516 How to prove this ?

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, he can get an amount of gold in any mine at least (\frac{G\cdot B}{A+B} - eps_2) (eps_2 depends on eps).

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 dt

clearly 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 = 0

which 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.

7 Likes