TLE in Family of Recurrences

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

asked 20 Sep '14, 04:07

4★the65bit
1.1k●10●13●28
accept rate: 13%

Please Help!!!

(21 Sep '14, 02:06) the65bit4★

One Answer:

oldest answers newest answers popular answers

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.

link

answered 21 Sep '14, 02:16

6★neo1tech9_7
8.5k●5●15●37
accept rate: 19%

edited 21 Sep '14, 02:18

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!!

(24 Sep '14, 21:53) the65bit4★

toggle preview

community wiki:

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

learn more about Markdown

Question tags:

matrix-expo ×285
recurrence ×116

question asked: 20 Sep '14, 04:07

question was seen: 1,106 times

last updated: 24 Sep '14, 21:53

TLE in Family of Recurrences

Follow this question

Related questions