×

# Spoj LKS Problem

 0 I can try Spoj LKS Problem many times ......but failed......Please say me - what is the wrong in my code. asked 29 Jan '17, 21:01 2★rashedcs 497●6●17●56 accept rate: 4%

 1 Your solution is exceeding the memory limit of 1536 MB as you are making a 2-dimensional array of size (N+1)×(K+1), where K ≤ 2000000 and N ≤ 500, so N×K is a little over 109 in the worst case. You cannot fit that many ints in the given memory limit, so you need to optimize the memory usage of your algorithm. You will notice that for any value dp[i][m] you just need to know all the computed values for certain dp[i-1][x] where x depends on the current m. But the important thing is we only need all the values from i-1 and nothing beyond that. So it is possible to solve this problem using two 1-D arrays of length W+1 which we use alternately in our original algorithm. Take a look at the implementation, it will hopefully make things clear. answered 30 Jan '17, 04:20 6★meooow ♦ 7.3k●7●20 accept rate: 48%
 1 @meoow is right! you are exceeding the memory limit! According to given constraint K <= 2000000 N <= 500  So you should change your algorithm. I used a different approach like this... if you notice that in 2-D Knapsack we had only need two consecutive rows of matrix to get our max() result so here i used same concept with exception that it is not purely 2-D matrix. i just used extra space in 1-D for making odd even concept such that i m only looking for previous row only! here is my accepted solution! Feel free to ask again, if you have still doubt! answered 30 Jan '17, 19:53 2.8k●1●4●19 accept rate: 16%
 1 I am using vector , but i am getting TLE, is it for push_back() ?? i want to know about the time of push_back(); here my code : https://ideone.com/fRsDkQ answered 03 Oct '17, 00:55 2★pranto84 11●1 accept rate: 0%
 0 But I still woundered how can a O(N*k) worst case can get AC which have approx 10^9 instruction! I mean how it can be handle in 2 sec? And even if i changed from int data type to long long data type in c++. It gives TLE? Why? answered 30 Jan '17, 20:21 2.8k●1●4●19 accept rate: 16% 109 instructions is quite possible, especially in 2 sec. Try it on ideone and see for yourself. And operations on long long are slower than those on int due to the difference in size. This is the worst case performance for int and this is for long long. You can see the difference in execution times. (30 Jan '17, 21:08) meooow ♦6★ No @meooow It's not possible! In one second up to 10^7 considered to be best and 10^8 would be considered as base (Lower chance to accept). You can refer my own article here.. http://www.geeksforgeeks.org/overcome-time-limit-exceedtle/ (30 Jan '17, 23:59) @bansal1232 what is your source for this information about 108 instructions being the strict upper limit? I can simply run a loop 109 times and show you that it takes less than a second to execute. For the LKS problem it took 1.5 seconds as the calculations are more complex, but it is very much possible. (31 Jan '17, 02:19) meooow ♦6★
 0 https://www.geeksforgeeks.org/space-optimized-dp-solution-0-1-knapsack-problem/ This should help. It has two articles. See the second one. answered 24 Dec '17, 14:38 875●2●14 accept rate: 10%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,214

question asked: 29 Jan '17, 21:01

question was seen: 964 times

last updated: 24 Dec '17, 14:40