10pullupsin2019's blog

APAC Round A, Problem C
By 10pullupsin2019, history, 8 years ago, In English

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?

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

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

      what if the function has a double root

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

        it's specified in the question that there is only one root in the range (-1,1)

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

      But how can you guarantee the function is decreasing

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

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.

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

    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?

    → Reply