ENCODING : DP Approach giving TLE

https://www.codechef.com/viewsolution/25924573

The above DP solution gives TLE. Can’t figure out the reason behind it.

Because of void init :sweat_smile::sweat_smile:

It might be due to the modulo operations, try to reduce the modulo operation as much as you can (by storing the required products modulo). You can take a look here:
https://www.codechef.com/viewsolution/25732989

Pick a large testcase and add some debugging at the first line of “solve” - something like:

cout << "solve: ind " << ind << " len: " << last << " s.length: " << s.length() << endl;

and run it locally - this will give you a hint.

Edit: The above was a crap hint - please ignore XD

However:

Useful hint: solve() is deeply recursive, and you are passing the string s by value, which will kill performance for large “numbers” (it basically turns in from O(N) to O(N x N)).

With local testing of your solution on a large testfile - your original solution just runs out of RAM almost straight away(!), whereas changing it to pass “s” by reference instead of by value allows it to complete in about 3.5 seconds.

Still no improvement.

That’s surprising - can you link to the newest submission?

Edit: found it

Well, there’s some improvement - two more testcases are AC.

Hmmm … it could be that the recursion just adds too much overhead - I think this is asymptotically good, now, but the constant factor is perhaps a teeny bit too high :confused: