Flaw in my logic.. - Codeforces

Блог пользователя Kaneki_04

Flaw in my logic..

Автор Kaneki_04, история, 9 лет назад, По-английски

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..

help needed

Kaneki_04
9 лет назад
4

Комментарии (4)

Написать комментарий?

Fred_Flintstone

9 лет назад, скрыть # |

← Rev. 2 →

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).

→ Ответить

Kaneki_04

9 лет назад, скрыть # ^ |

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?

→ Ответить

Fred_Flintstone

9 лет назад, скрыть # ^ |

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.

→ Ответить