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..
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)cmpcorrect?And use
long longanswer can be larger than 2^32if(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 intable[in][k]is correct.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.
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