Editorial for Yet Another Contest 2 P1 - Betting
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
Let Mike bet dollars that the Geese will win and
dollars that the Kangaroos will win. Then, he will bet a total of
dollars, and in the worst case scenario, he will win
dollars.
We can brute force over all possible values of and
, and check if there exists a combination such that
.
Time complexity:
Subtask 2
For Mike to guarantee a profit, we require both and
to be true.
Rearranging the first equation, we see that .
Rearranging the second equation, we see that .
Combining these equations, we obtain . Dividing both sides by
, we obtain
. Therefore, if a solution exists, then
must be true. To avoid precision errors, we can instead check whether
is true.
It turns out that if this inequality is true, then a solution must exist. For example, we can set and
to any value greater than
and less than
.
Hence, we can solve each scenario in time.
Time complexity:
Comments
Wait, I'm confused. If
and
, then how can we assume that
?
We know that
is SMALLER than
, so why do we suddenly assume they are equal in the third equation?
From the equation \(X<Y \cdot (\frac{D}{C}-1) \), we have \(X \cdot (\frac{B}{A}-1)<Y \cdot (\frac{D}{C}-1) \cdot (\frac{B}{A}-1)\).
Since \(Y < X \cdot (\frac{B}{A}-1) \), we see that \(Y<Y \cdot (\frac{D}{C}-1) \cdot (\frac{B}{A}-1)\).