TLE in No string attached in O(n) complexity

[honeybuzz]

Write your question here.


Guys, I have almost cracked NSA.I have used DP/memoization and have reduced my complexity to O(n) but am getting only 30 pts...I think its because of the number of times I have iterating over the string...I am iterating over the string 4 times for memoization...I am marginally missing the 100 pts...Any suggestions to reduce the the time?
Thank you.

[blackmamba]

@honeybuzz PM me ur code

[honeybuzz]

I am getting TLE for the third subtask...I have coded in Python and its has taken a maximum of 0.23 secs for 30 points.

[honeybuzz]

It would have worked had the time limit been around 2.5 s

[honeybuzz]

I am confident because I only have 2 nested loops-one runs till n and the other one till 0 to 26...making a total of 26*n iterations per loop...these loops run 5 times making a total of 26*5*100000 operations...since we have 20 test cases, therefore number of operations become 26*5*100000...also i need 100000 operations to calculate the default cost (26*5*100000)+100000...this is exceeding the number of operations a language can perfoem as in 1.5s

[honeybuzz]

1 0 AC
(0.070000)
1 1 AC
(0.110000)
Subtask Score: 10.00% Result - AC
2 2 AC
(0.110000)
2 3 AC
(0.080000)
Subtask Score: 20.00% Result - AC
3 4 AC
(0.700000)
3 5 AC
(0.710000)
3 6 AC
(0.730000)

Finally, it worked!!!I had to convert my code to Java :/