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)$ ~\mathcal{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)$ ~\mathcal{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)$ ~\mathcal{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)$ ~\mathcal{O}(D)~

Comments

There are no comments at the moment.