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

getting TLE… plz help with ths solution
Автор sentinel45, 12 лет назад, По-английски

the following code is my soln to 38E - Let's Go Rolling!

i m using memoization in table

k is the index of last index to be pinned

and

in is the value of index for which decision will be made

the submission can be found here.. http://www.codeforces.com/contest/38/submission/1811242

plz help...optimizing my code or any general useful suggestions regarding implementation of dp..

thanx..

Теги 38e
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

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

Try to use other "empty" value, not just zero. memset(table, 0x05, sizeof(table));... if(table[in][k] != 0x05050505) ...
BTW, are you sure is this conversion (compfn)cmp correct?
And use long long answer can be larger than 2^32

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

    if(table[in][k] != 0x05050505)
    I think it's a bad practice: on Codeforces Round it can be easily hacked.
    It's better to use boolean array: calculated[in][k] is true if the value stored in table[in][k] is correct.

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

      it can't be hacked if there can't be such value. use 0x7F7F7F7F7F7F7F7FLL. maximum value is about 3000 * 10^9, so you can use 0x0101010101010101LL for example.

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

ohh, i figured it out...

the answer for test 18 was zero... so every entry was supposed to be equal to zero... and my table was initialized to zero as well..!!! ths led the algorithm to exponential tym coz memoization was rendered useless...

gosh..!!! lesson of a lyftym...:)

thnx guys goo.gl_SsAhv and dalex

→ Ответить