You are not logged in. Please login at www.codechef.com to post your questions!

×

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

the65bit's gravatar image

4★the65bit
1.1k101328
accept rate: 13%

Please Help!!!

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

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

neo1tech9_7's gravatar image

6★neo1tech9_7
8.5k51537
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
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

Question tags:

×285
×116

question asked: 20 Sep '14, 04:07

question was seen: 1,106 times

last updated: 24 Sep '14, 21:53