How the constraints n <= 17000 fit into this problem

#1

I applied MCM logic , got Runtime error in 1 test case ? why ?? https://ide.codingblocks.com/s/316513

#2

@aryan_007,
Runtime is because you are declaring small dp, and test case as clearly mentioned, has bigger n.
You should try to find the complexity of your code, maybe it can hint you that this problem won’t require memoization, just like merge sort doesn’t require one.

#3

but how can i make a dp array of 17000 and 17000 ???

#4

And when i am not applying memoization then i am getting TLE

#5

but i can see their are some overlapping sub problems so why memoization will not be applied ?

#6

@aryan_007,
Why weren’t we applying memoization in merge sort recurrence?

#7

because in that we break from k=mid , but here we are breaking from k=i to k<j so , it might happen that some range answer would have already been computed

#8

@aryan_007,
You don’t have to break it for all k in [i,j), you can simply find the exact index from where to break, and then break from there only. It would be just like merge sort than, just the difference would be, breaking would be different from mid, that’s it.
Think carefully, you don’t need MCM here.

#9

okay it is true that it will break at 1 point only but to check at which point it will break i will have to linearly traverse the array from i to j ??

#10

or is their any O(1) method to figure out the break point ?

#11

@aryan_007,
There is.

#12

okay what it is ?? i couldn’t figure that out ?

#13

@aryan_007,
Link

#14

okay sir , i actually returned after ending of loop , i need to return in loop only !! thankyou sir