sentinel45's blog

getting TLE… plz help with ths solution
By sentinel45, 13 years ago, In English

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

Tags 38e
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
13 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

    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.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

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

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

→ Reply