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

APAC Round A, Problem C
Автор 10pullupsin2019, история, 8 лет назад, По-английски

In this problem many did binary search and calculated the value of the function and stored the values in doubles and compared the results.

Shouldn't there be precision errors? As you are multiplying something with like (1.99999)^100?

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Also why is the polynomial an increasing function? Because xy is greater than xy + 1 for x < 1.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    At r=-1, the value of the polynomial is clearly positive, because cm is positive. And since there is only one root in the range -1<r<1, thus the polynomial has one root dividing the function into two parts. That is why you can do binary search.

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If you directly try to find the value of (1.99999)^100 then it is not possible. So, what we can do is divide the whole equation by the highest power of (1+r) so that (1+r)^x for all x is in the denominator. Now we can define a variable denom = 1/(1+r) and if we do denom/=(1+r) for x times then it is equivalent to 1/((1+r)^x). We can use this value with the corresponding cost values.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    okay, If u divide it with the highest power of (1+r) then the one which originally had power 0, now has power (1+r) ^ (-highest_power) . Now this value is very small! and again, shouldn't it cause precision errors?

    → Ответить