I can try [Spoj LKS Problem][1] many times …but failed…Please say me - what is the wrong in my
[2].
[1]: http://www.spoj.com/problems/LKS/
[2]: http://ideone.com/1rW8SQYour 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.
1 Like
@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!
1 Like
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?
First of all @meooow, before arguing to someone please make sure that you have all concept clear in right way!
You can see First, Second where they give a clear cut explanation about how many instruction you can perform! And in this you will see for value of N=1000,000,000 O(N) would not be the good case! You should optimize the algorithm.
Basically it almost depend upon the server configuration and your computer! Suppose if you try to use super computer for calculation then N can go beyond 10^8 or 10^9 easily.
And for ideone there can be chance that there server is faster than our codechef or spoj judge etc so it is been accepted in 10^9 instruction!
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 : fRsDkQ - Online C++ Compiler & Debugging Tool - Ideone.com
1 Like
This should help.
It has two articles. See the second one.
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.
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… How to overcome Time Limit Exceed(TLE)? - GeeksforGeeks
@bansal1232 what is your source for this information about 108 instructions being the strict upper limit? I can simply [run a loop 109 times][1] 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.
[1]: 1j6xjW - Online C++0x Compiler & Debugging Tool - Ideone.com
You really don’t believe me, do you? 
SPOJ, Ideone and Codechef are all powered by the same Sphere Engine. Here is the loop running in 0.65 seconds on Codechef judge- [link][1].
I know that usually an algorithm with 109 iterations time out, but that is because the calculations involved are much more complex than simple addition. However, if you decide to trust your own eyes, you can see that it does manage to execute in cases such as these. This is not at all about concepts, this is a very practical matter!
[1]: CodeChef: Practical coding for everyone
2 Likes
@bansal1232 please feel free to experiment on your own! That is the most reliable way to convince yourself 
1 Like
Oh god! U still arguing, try to run this code in Compile and run the code with online compiler and IDE | CodeChef, you will exceed 1 sec definitely. Don’t try to run your code in dummy question.
In Codechef IDE the code takes ~1.2 sec. About the two links you shared, I’m sure betlista and xellos0 are very experienced coders, but their answers are dated 2012 and 2014. Spoj switched from their clusters on 2015-03-02, so solutions now execute “30 to 50 times faster”. So one can consider their answers to be a bit inaccurate now. However this is not my main argument. I have shown you the code running and asked you to try it yourself. If you can see it run and still disagree I have nothing more to add. Please believe what you will 
2 Likes
Exactly! I m also saying that the whole process depends upon server configuration.
1 Like