help with MLE!

general
,
1

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

my soln : Submission #34501132 - Codeforces

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.

2

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.

1 Like
3

please comment on this solution.

4

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

5

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

6

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

1 Like
7

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.

2 Likes
8

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.