Kaneki_04's blog

Flaw in my logic..
By Kaneki_04, history, 7 years ago, In English

I was thinking of a way to solve this problem in O(1) and I am not getting the right answer..

My logic was that..

the answer is (a+b)(a+1)(b+1)/2 and the equation is x+my=mc(I changed b to c for convinience..)

so upon applying the am>=gm inequality in the following way..

((a+b)+(a+1)+(2*m-1)(b+1)/3>=((2*m-1)^1/3)*answer

so answer would be floor(LHS/(2*m-1)^1/3) and LHS is (2*m*c+2*m)/3 as (a,b) lies on the line..

but I was getting a wrong answer..

Sorry if I missed something obvious and any help would be really appreciated..

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Hi, well first of all the right side of your inequality should be ((2*m -1)*2*ans)^1/3 instead of ((2*m-1)^1/3)*ans, but then when you found x = floor(...) you found the biggest integer solution that satisfies your inequality, however it may be impossible for (a+b)(a+1)(b+1)/2 to take the value of x, so you must find the largest integer solution for (a+b)(a+1)(b+1)/2 = y where y <= x which can be tricky but with some help from wolfram alpha is possible. BTW i really like the way you used am>=gm to solve this problem in O(1).

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

    oops missed the cube!! so you are saying that the maximum value for that expression may not occur at integral points and we are supposed to find max val for integral points?

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

      Yes, for example I wrote the code:

      #define three(x) x*x*x

int main()
{
    long long m, c, x;
    cin >> m >> c;
    double LHS = (double)(2*m*c+2*m)/3;
    LHS = three(LHS);
    x = floor(LHS/(4*m-2));
    cout << x;
    return 0;
}

      and for m = 1, c = 5 it outputs 32, however the answer is 30, because 32 occurs at non integral point.

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

        thanks bud!! appreciate your help. Gonna be more careful when dealing with integers next time :)

        → Reply