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

×

Linear Reccurrence - Harejump

I was solving harejump using matrix exponentiation. To do so we need the base matrix F1 containing the solutions for the first 15 nos. So i used standard dp to solve for the first 15 nos. and then used matrix exponentiation. Here's my AC solution. However seeing other solutions, i noticed that they have not created the base matrix. eg but their solutions still work. So I wanted to know why isnt it necessary to precompute the answers for the first 15 nos.?

asked 13 Jan '13, 18:55

karan173's gravatar image

5★karan173
68591119
accept rate: 0%


Hello,

I also struggled a lot with that problem and, in fact, got discouraged when I saw that the base matrix needed to be 15x15, so I ended up reading the editorial for the problem...

As you will see, they formulate it in a different way... Hope it can help you out:

HAREJUMP editorial

Good luck,

Bruno

link

answered 13 Jan '13, 19:03

kuruma's gravatar image

3★kuruma
17.7k72143209
accept rate: 8%

well i have already solved the problem, but with a slow time due to precomputing answers for nos<=15. My problem is that i cant understand why solutions like these http://www.codechef.com/viewsolution/731949 w/o any base matrix work?

(14 Jan '13, 01:23) karan1735★

But, there is a matrix on that solution... In fact, a Matrix class is created..

(14 Jan '13, 01:30) kuruma3★

but no base matrix , i mean F1, like the one we create for fibonacci

(14 Jan '13, 01:48) karan1735★

here's my solution http://www.codechef.com/viewsolution/1714517, i hope u can make out what i m trying to ask through the difference in the 2 solutions.

(14 Jan '13, 01:51) karan1735★
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:

×303
×116

question asked: 13 Jan '13, 18:55

question was seen: 1,244 times

last updated: 14 Jan '13, 01:51