red_coder's blog

Memoization!!
By red_coder, 12 years ago, In English

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.

  • Vote: I like it
  • +14
  • Vote: I do not like it

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

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 )

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

    It's memoize

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

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

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

      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.

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

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

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

when i used vector< pair<int,int> > for hashing then for larger values of N it gave runtime error. Pls somebody help

→ Reply