Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

VastoLorde95's blog

By VastoLorde95, history, 9 years ago, In English

Hi, In this problem, I am using the idea that AM >= GM just like in the editorial but with slightly different steps.

Equality should hold when all elements are equal. So according to me, x = y = z and the solution I arrive at is that x = y = z = S / 3

But this is incorrect as seen from the test case

S = 10

a = 1, b = 6, c = 3

My solution gives x = y = z = 3.33 and hence xa·yb·zc =  169350.87

But the optimal solution is x = 1.0, y = 6.0, z = 3.0 with xa·yb·zc =  1259712

What is the flaw in my math? Is this not a correct way to use GM <= AM? I don't understand why my solution differs from the solution given in the editorial even though the principle behind both is the same.

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

why equal?

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

As far as I understood, you have to solve with x + y + z = S, where a, b, c, S is given.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But for AM=GM inequality to hold shouldn't all elements be equal? So ax+by+cz means a x's b y's and c z's should all be equal right?

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You wrote which is true and that equality will hold at x = y = z which is also true but there is no fixed value for the right hand side so it may be better for you to be less than a huge value than equal to a smaller one.

This is why we go according to this method

therefore,

I would have gone on but I am tired of manipulating LaTex symbols.

Some manipulation should show you that the term we want to maximize is now bounded above by a constant value (this is where the difference is between what your solution and authors solution) so you know that you can only get to that constant when and x + y + z = S.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why is it an issue if there is no fixed value on the right hand side? Also if x+y+z <= S then it has to be bounded right?

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it +2 Vote: I do not like it

      Look at the example you have given.

      For the solution you find (x=y=z=3.33) lhs = rhs, but for the optimum solution(x=1,y=6,z=3) lhs < rhs.

      What I am saying is that if your rhs is extremely huge and your lhs is slightly smaller than it then that is better than having a small rhs and an equal lhs.

      Hence, you want a constant rhs so that you know that the term you are maximizing can never do better than that.

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Aahhhhh... I get it. So I found the condition for equality of AM and GM but that is not the condition for upper bound of GM?

        From what I understand you have manipulated to use AM >= GM in such a way that the AM is the upper bound and equality also guarantees optimality. Am I right?

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Exactly.

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why should GM give maximum when you use it that way?

          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You have found an inequality which gives a constant upper bound for the GM. Now you know the conditions for which you can achieve equality. You use those conditions to maximize GM.

            I would prefer it if someone more experienced than me would verify my approach but I can't see any reason as of now for it to be wrong.

            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              I found out for 2 dimension why x/a = y/b gives maximum.

              I am assuming NO z at all so eq. is (x^a)*(y^b) and x+y=S x=S-y so the eqn. becomes ((S-y)^a)*(y^b)

              for max. we derive w.r.t y and equate to 0 i.e -a*(S-y)^(a-1)*(y^b) + b*(y^(b-1))*(S-y)^a = 0 solving we get (S-y)*b — a*y =0 => b*x=a*y => x/a=y/b i.e if x/a=y/b the eq. will be a maximum or minimum (Double derive and check i think it will be maximum)

              I have no idea how to do for 3d i.e with z included