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

×

TLE in STRMRG

Kindly help me know why am I getting TLE in my solution.

Link to solution.

I have used LCS approach in my solution.

Thank You.

asked 15 Jan '18, 21:16

shraeyas's gravatar image

3★shraeyas
1.3k2619
accept rate: 10%

edited 15 Jan '18, 21:23


See this solution. The reason is in C++, string object are passed to function as call by value unlike C string of character array which passed as call by reference. Hence every time the compiler allocate new memory for every recursion call and hence will lead to TLE.

As you can see in my solution, I have passed the string as call by reference and thus got AC

link

answered 15 Jan '18, 22:05

bansal1232's gravatar image

5★bansal1232
2.8k1419
accept rate: 16%

OK. Thank You.

(15 Jan '18, 22:07) shraeyas3★

How do I write an iterative DP solution if I already know the recursive one?

(15 Jan '18, 22:12) shraeyas3★

Have you tried implementing the iterative version of the LCS instead of the recursive one you are using? That might help.

link

answered 15 Jan '18, 21:32

piyush_ravi's gravatar image

1★piyush_ravi
92
accept rate: 0%

I have seen that the iterative ones work but cannot understand why this one doesn't. I have used dp array to store results so that there is no repitition. Hence, this solution should have also worked!

(15 Jan '18, 21:45) shraeyas3★
1

maybe the recursion depth goes so high that the system stack pop in and pop out takes time? (considering too many parameters?)

(15 Jan '18, 22:01) swetankmodi ♦♦6★

Yes. Right. That maybe a reason.

(15 Jan '18, 22:03) shraeyas3★
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:

×191
×20

question asked: 15 Jan '18, 21:16

question was seen: 301 times

last updated: 15 Jan '18, 22:12