You are not logged in. Please login at www.codechef.com to post your questions!

×

Spoj LKS Problem

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

rashedcs's gravatar image

2★rashedcs
49761756
accept rate: 4%


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.

link

answered 30 Jan '17, 04:20

meooow's gravatar image

6★meooow ♦
7.3k720
accept rate: 48%

edited 30 Jan '17, 16:47

@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!

link

answered 30 Jan '17, 19:53

bansal1232's gravatar image

5★bansal1232
2.8k1419
accept rate: 16%

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

link

answered 03 Oct '17, 00:55

pranto84's gravatar image

2★pranto84
111
accept rate: 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?

link

answered 30 Jan '17, 20:21

bansal1232's gravatar image

5★bansal1232
2.8k1419
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) bansal12325★

@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★

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!

link

answered 31 Jan '17, 11:07

bansal1232's gravatar image

5★bansal1232
2.8k1419
accept rate: 16%

edited 31 Jan '17, 11:13

2

You really don't believe me, do you? :P
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.
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!

(31 Jan '17, 11:57) meooow ♦6★
1

@bansal1232 please feel free to experiment on your own! That is the most reliable way to convince yourself :)

(31 Jan '17, 11:58) meooow ♦6★

Oh god! U still arguing, try to run this code in www.codechef.com/ide, you will exceed 1 sec definitely. Don't try to run your code in dummy question.

(31 Jan '17, 12:12) bansal12325★
2

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 :)

(31 Jan '17, 19:55) meooow ♦6★
1

Exactly! I m also saying that the whole process depends upon server configuration.

(31 Jan '17, 21:57) bansal12325★

https://www.geeksforgeeks.org/space-optimized-dp-solution-0-1-knapsack-problem/

This should help. It has two articles. See the second one.

link

answered 24 Dec '17, 14:38

akashbhalotia's gravatar image

5★akashbhalotia
875214
accept rate: 10%

edited 24 Dec '17, 14:40

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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