Editorial for Mock CCC '18 Contest 1 J3/S1 - A Math Problem

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

If we start by evaluating f(1), then f(2), and so on, we note that f might be decreasing but eventually starts increasing. We note that MX increases by X every time M increases by 1, but eventually \dfrac{KP}{M} will not decrease quickly enough to offset.

The intended solution is therefore to increase X until f(X) \le f(X+1) and report f(X).

The most common pitfall observed in solutions was contestants not following instructions and printing out the value to an incorrect number of decimal places.

It is possible to use calculus or other techniques to directly evaluate the minimum, but those were not necessary to solve this problem.


  • 2
    ScriptKitty  commented on Feb. 14, 2018, 1:30 a.m.

    Use Am-Gm!

    MX + KP/M >= 2 math.sqrt(XPM)

    I hope I'm allowed to say this... After-all, this page is for people who are stuck.

  • 3
    Totom3  commented on Feb. 6, 2018, 10:57 p.m.

    Couldn't we use a little calculus to find the minimum, and then simply check the integers above and below?

    • 3
      Xue_Alex  commented on Feb. 6, 2018, 11:38 p.m.

      That's what I did, try it for yourself and see what happens!