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

×

help with MLE!

prob : http://codeforces.com/contest/914/problem/F

my soln : http://codeforces.com/contest/914/submission/34501132

I am using suffix tree for every blocks. It takes O(n*28) space atmost but I don't know why it is giving MLE. Please help me to figure out the reason.

asked 24 Jan '18, 20:03

pk301's gravatar image

2★pk301
62710
accept rate: 16%

please comment on this solution.

(25 Jan '18, 08:25) pk3012★

@vijju123 can you please comment on the space complexity. It is the same code that u had debugged.

(25 Jan '18, 18:03) pk3012★

You are kind of close to the memory limit. On CF, try that you dont exceed $4.5*{10}^{6}$ total size of arrays. $3*{10}^{6}$ size arrays take $100MB$ there.

Now coming to your problem.

Your struct sqrts has 8 parameters, out of which 1 is string of length $N$ and other is another struct with ~$32$ more variables (counting the child[28] as 28 variables).

Thats around 40 variables and a string of size $N$ per sqrt thing. It seems you are making $\sqrt{N}$ such structures. That becomes $40N\sqrt{N}$ , and in my opinion the constant is a bit too high.

link

answered 25 Jan '18, 19:13

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

My string size is not 'N' it's sqrt(N). so, overall $40N$

(26 Jan '18, 12:45) pk3012★
1

$40N$ is still quote close. Remeber we didnt take into account any memory needed for recursive calls and etc. I think you are just on the edge. Try and see if those trivial optimisations help (converting unnecessary long long to int) etc.

I also got my first MLE in CSUBQ of long challenge- making long long as ints reduced it to 90 MB from >256MB

(26 Jan '18, 18:38) vijju123 ♦♦5★
2

Note that it goes into MLE after certain time, not immediately. So you arent getting MLE in/after input output. While processing your queries, you are running out of memory. Recursive calls need memory as well. Might be the reason.I'd say, check out others code and see how it can be optimized.

(26 Jan '18, 18:43) vijju123 ♦♦5★

Thanks! Actually i'd seen many codes but none of them solved it using Suffix_tree. That's why i post it here.

Btw i have no long longs in my code lol.

(26 Jan '18, 19:33) pk3012★
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:

×643
×241

question asked: 24 Jan '18, 20:03

question was seen: 315 times

last updated: 26 Jan '18, 19:33