| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
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::mapis 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_mapis 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_mapis 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