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 to 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 and whether or not its product is the greatest.

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

Subtask 2

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

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

Subtask 3

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

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

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

Careful steps must be taken to ensure that the three variables must sum up to H_i.

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

Subtask 4

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

Time Complexity: \mathcal{O}(D)


Comments

There are no comments at the moment.