Editorial for Wesley's Anger Contest 3 Problem 2 - Eat, Sleep, Code, Repeat - Olympiads Online Judge

Editorial for Wesley's Anger Contest 3 Problem 2 - Eat, Sleep, Code, Repeat

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: Zeyu

Subtask 1

For subtask 1, one can loop through all possible integer value of hours from $1$ $1$ to $H_i$ $H_{i}$ for all three variables. All that's left is to check whether or not the sum of the three variables is equal to $H_i$ $H_{i}$ and whether or not its product is the greatest.

Time Complexity: $\mathcal{O}(D \cdot H_i^3)$ $O (D \cdot H_{i}^{3})$

Subtask 2

For subtask 2, one can loop through all pairs of hours from $1$ $1$ to $H_i$ $H_{i}$ for two variables, then solve for the third one algebraically.

Time Complexity: $\mathcal{O}(D \cdot H_i^2)$ $O (D \cdot H_{i}^{2})$

Subtask 3

For subtask 3, one can loop through $1$ $1$ to $H_i$ $H_{i}$ for the first number, then solve a simpler version of this problem:

Given an integer $K$ $K$ , find two nonnegative integers $A$ $A$ and $B$ $B$ such that $A + B = K$ $A + B = K$ and the product of $A$ $A$ and $B$ $B$ is maximized.

This value is maximized when the absolute difference between $A$ $A$ and $B$ $B$ is minimized. Try expanding $(A - 1)(A + 1)$ $(A - 1) (A + 1)$ and compare it to $A^2$ $A^{2}$ !

Careful steps must be taken to ensure that the three variables must sum up to $H_i$ $H_{i}$ .

Time Complexity: $\mathcal{O}(D \cdot H_i)$ $O (D \cdot H_{i})$

Subtask 4

For the full solution, we can apply the same idea and extend it to $3$ $3$ variables. To solve for three variables, the maximum absolute difference should be minimized while ensuring that they still sum up to $H_i$ $H_{i}$ .

Time Complexity: $\mathcal{O}(D)$ $O (D)$

Comments

There are no comments at the moment.