Editorial for Yet Another Contest 2 P1 - Betting - Olympiads Online Judge

Editorial for Yet Another Contest 2 P1 - Betting

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Josh

Subtask 1

Let Mike bet $X$ $X$ dollars that the Geese will win and $Y$ $Y$ dollars that the Kangaroos will win. Then, he will bet a total of $X+Y$ $X + Y$ dollars, and in the worst case scenario, he will win $\min(X \times \frac{B}{A}, Y \times \frac{D}{C})$ $min (X \times \frac{B}{A}, Y \times \frac{D}{C})$ dollars.

We can brute force over all possible values of $X$ $X$ and $Y$ $Y$ , and check if there exists a combination such that $X+Y < \min(X \times \frac{B}{A}, Y \times \frac{D}{C})$ $X + Y < min (X \times \frac{B}{A}, Y \times \frac{D}{C})$ .

Time complexity: $\mathcal{O}(100^2 \times T)$ $O (100^{2} \times T)$

Subtask 2

For Mike to guarantee a profit, we require both $X+Y < X \times \frac{B}{A}$ $X + Y < X \times \frac{B}{A}$ and $X+Y < Y \times \frac{D}{C}$ $X + Y < Y \times \frac{D}{C}$ to be true.

Rearranging the first equation, we see that $Y < X \times (\frac{B}{A} - 1)$ $Y < X \times (\frac{B}{A} - 1)$ .

Rearranging the second equation, we see that $X < Y \times (\frac{D}{C} - 1)$ $X < Y \times (\frac{D}{C} - 1)$ .

Combining these equations, we obtain $Y < (\frac{B}{A} - 1) \times (\frac{D}{C} - 1) \times Y$ $Y < (\frac{B}{A} - 1) \times (\frac{D}{C} - 1) \times Y$ . Dividing both sides by $Y$ $Y$ , we obtain $1 < (\frac{B}{A} - 1) \times (\frac{D}{C} - 1)$ $1 < (\frac{B}{A} - 1) \times (\frac{D}{C} - 1)$ . Therefore, if a solution exists, then $(\frac{B}{A} - 1) \times (\frac{D}{C} - 1) > 1$ $(\frac{B}{A} - 1) \times (\frac{D}{C} - 1) > 1$ must be true. To avoid precision errors, we can instead check whether $(B-A) \times (D-C) > A \times C$ $(B - A) \times (D - C) > A \times C$ is true.

It turns out that if this inequality is true, then a solution must exist. For example, we can set $X = 1$ $X = 1$ and $Y$ $Y$ to any value greater than $\frac{1}{\frac{D}{C} - 1}$ $\frac{1}{\frac{D}{C} - 1}$ and less than $(\frac{B}{A} - 1)$ $(\frac{B}{A} - 1)$ .

Hence, we can solve each scenario in $\mathcal{O}(1)$ $O (1)$ time.

Time complexity: $\mathcal{O}(T)$ $O (T)$

Comments

0

ev_code commented on Oct. 26, 2024, 4:51 p.m.

Wait, I'm confused. If $Y < X × ((B/A) - 1)$ $Y < X \times ((B / A) - 1)$ and $X < Y × ((D/C) - 1)$ $X < Y \times ((D / C) - 1)$ , then how can we assume that $Y < ((B/A) - 1) × ((D/C) - 1) × Y$ $Y < ((B / A) - 1) \times ((D / C) - 1) \times Y$ ?

We know that $X$ $X$ is SMALLER than $Y × ((D/C) - 1)$ $Y \times ((D / C) - 1)$ , so why do we suddenly assume they are equal in the third equation?

0

Dequan_Kong commented 81 days ago

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)$ .