TLE in Family of Recurrences

general
,
1

Here is the problem.

I have implemented matrix multiplication to solve the recurrence relation. the order of the solution should be O(m^3 * log(n) * T) which is approximately 32 * 10^6 * 20 = 64 * 10^7, which should be done in 1 sec.The time limit of the problem is 15 sec, still I am getting TLE.

Please Help, here is my solution

2

Please Help!!!

3

Try using 2 d arrays instead of vector < vector < long long > > as you have to clear them for each test case (which you are not doing and will result in wa) and resize() function also has complexity O(n) if i remember correctly. Also declare the arrays globally.

1 Like
4

Thanks for the help.
Now I have implemented using arrays I am getting WA now.
Here is the solution http://www.codechef.com/viewsolution/4891445
Please Help!!