suppose we are applying memoization in which we check if we have already calculated the value for some value of N. If yes we simply return that value; like if DP[N]>-1 return DP[N] else compute for N and store it in DP[N].
But how to apply memoization when N is too large upto 10^9. After all we cant have size of array DP[] upto 10^9.
In such situations i often memorize only first 1000000, or, if it is posible — try to memorize, for example, answers for n=1, n=1000, n=2000, ... n=1000000000, and try to write algo which calculate answers, using only this information. Hope, this trick will help you in some problems, and sorry for my poor English =)
P.s. Or, if there is no chanse to use some tricks, it means that there is another solution, which will not have TLE, and you must find it )
It's memoize
Fun fact: It's not called Memorization, even though this name really suits it as well. It's actually called Memoization after the act of making a 'memo' or a note for future reference.
Probably You NOT need computed values for each possible value in range 1..10^9. (If yes, O(N) memory is necessary)
So, solution is simple. Store answer only for necessary values and use container like
std::map
. Space complexity is linear (_O(m)_, where m is a number of stored items) and time complexity of single lookup is O(lg m). This is the price, which we must pay (or take out memoisation :P).if i am not wrong basically u are pointing towards hash tables. Am i correct?
Yes.
Hash tables and fine for this purpose too. But in this case is good to know the final number of elements; in this kind of problem this is often hard to guess.
Using of red-black tree instead MAY be better.
dude i dont know even a single thing about how to implement hashing and red-black trees in code. Can u give some link of tutorial or code by which i can learn it. Its scary :(
Best solution (especially for contests like CF (CF = Codeforces)) is using STL version of data structures :)
std::map
is an implementation of RBT, example of use: http://www.cplusplus.com/reference/stl/map/operator[]/ (for DP purpose You can use something likemap<int, int>
)std::unordered_map
is a good hash table implementation from STL http://www.cplusplus.com/reference/stl/unordered_map/ [Before C++11 standard, unordered_map stuff was been under tr1 namespace, sostd::tr1::unordered_map
is full name in CF GNU G++ version]excellent bro excellent. You guys make me learn a lot. Great :)
when i used vector< pair<int,int> > for hashing then for larger values of N it gave runtime error. Pls somebody help