Getting memory limit exceeded

#1

Here i am doing this question…based on dp…
https://codeforces.com/problemset/problem/1320/A
I am trying do this using top - down approch… But for the memoization i have to take dp[200005][200005]… which is giving memory limit excedded and if i am taking dp[20005][20005]… then it is giving wrong answer due to out of bound.
Please have a look at my solution… How i can memoize it in more efficient way…
https://codeforces.com/contest/1320/submission/96342607
Thanks

#2

hello @ashishnnnnn

a) dp[20005][20005] this much space u cannot allocate in any program.

b) did u observe this ci+1−ci=bci+1−bi ?
it is same as ci+1 - bi+1 =ci-bi
which is basically saying we can move only on cities whose i-bi is same.
now the problem is very simple.
group all cities whose i-bi valye is same , and compute answer .

#3

Actually … I wanted to deliberately solve it using DP… Can you give some though regarding this… :slight_smile:

#4

Although… This is nice… Greedy way… To solve this…
Thanks … :slight_smile:
But i want to ask… if someone wants it solve by dp… what should be his approch…

#5

as per given constraint it is not solvable using db becuase of high memory requirement.
this should be the dp approach.

solve(i, diff) =
pick ith if it i-b[i]==diff and call (i+1 ,diff)
or
start new chain from i itself by ignoring previous diff
return whatherevr is maximum

this should be the two cases at each index i . and 2 d matrix will be required for memoisation

#6

One … Thing i want to ask… In contest… Does bottom up… approach… gives more benefits… as compared to top down… Or it is okay to use top down ??

#7

no, during thr contest top down is best (i feels) becuase u just have to think of a recursion and then just add an array to memoise ur result (always worked for me).

#8

Thanks… I also feel the sae way… :slight_smile: