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

Why does using logarithmic approach give me TLE?
Автор dorasainath955, история, 2 месяца назад, По-английски

Submission Problem

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

»
2 месяца назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Cause when k == 1 it will run n time which is of order 1e9.... But log approach still gives WA on larger tescase as it might have precision errors..

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

    could you give me an example for precision error, i mean int x = ln(n)/ln(k)

    we dont have to precisely find out the value of exponent, we can just find the one that's closest, could you give me an example where this approach will fail.

    i also did this approach, when n<k then there will be n operations, this also gave TLE

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

    Can you check this out:

    Comment-1203949

    I tried the log approach, one with multiples of k^x and one with just k^x. (Where k^x will be the largest power of k <= n)

    → Ответить