×

# Linear Reccurrence - Harejump

 0 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 5★karan173 685●9●11●19 accept rate: 0%

 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 answered 13 Jan '13, 19:03 3★kuruma 17.7k●72●143●209 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 community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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