Memoization!! - Codeforces

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

Memoization!!

Автор red_coder, 14 лет назад, По-английски

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.

red_coder
14 лет назад
10

Комментарии (10)

Написать комментарий?

Berezin

14 лет назад, скрыть # |

← Rev. 2 →

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 )

→ Ответить

niyaznigmatul

14 лет назад, скрыть # ^ |

+12

It's memoize

→ Ответить

frank44

14 лет назад, скрыть # ^ |

+16

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.

→ Ответить

Przemek

14 лет назад, скрыть # |

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

→ Ответить

red_coder

14 лет назад, скрыть # ^ |

if i am not wrong basically u are pointing towards hash tables. Am i correct?

→ Ответить

Przemek

14 лет назад, скрыть # ^ |

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.

→ Ответить

red_coder

14 лет назад, скрыть # ^ |

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 :(

→ Ответить

Przemek

14 лет назад, скрыть # ^ |

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 like map<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, so std::tr1::unordered_map is full name in CF GNU G++ version]

→ Ответить