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

×

GOLDMINE - Editorial

PROBLEM LINK:

Contest

Author: Aman Kumar Gupta

Editorialist: Aman Kumar Gupta

DIFFICULTY:

EASY-MEDIUM.

PREREQUISITES:

DP, Math, Matrix, Fast exponentiation.

PROBLEM:

The number of ways you can mine a row of size 1 * n using given types of bombs modulo 10^9+7.

EXPLANATION:

The first method which can be used is DP of course. It seems to be a classical DP problem.

So when the size of the row is 1 * 1, dp[1] = 0. When the size of the row is 1 * 2, dp[2] = 1 and similarly dp[3] = 1, where dp[i] refers to the ways in which the row of size i can be mined.

And from here upon, build the dp array as: dp[i] = (dp[i - 2] + dp[i - 3]) % 1000000007;

Finally dp[n] would be our answer.

But this will fail here because of the large constraint.

Now, suppose we have an equation like this: [dp[0], dp[1], dp[2]] * M = [dp[1], dp[2], dp[3]], where M is a matrix of size 3 * 3, then we can say [dp[0], dp[1], dp[2]] * M^2 = [dp[2], dp[3], dp[4]].

On generalizing, [dp[0], dp[1], dp[2]] * M^(N - 2) = [dp[n - 2], dp[n - 1], dp[n]] for N > 2

To find the matrix, consider the matrix cells unknown and multiply it with the dp array on the left and equate it with the RHS. Leaving the task upon you, the matrix will be:
0 0 1
1 0 1
0 1 0

Now M^(n - 2) can be found in 27 * log n and after all the multiplications of the above equation, our answer will simply be FinalArray[2] (the last element of our resulting array on the RHS).

Note: You need to take care of taking modulo on every operation to avoid the overflow. See the solution for more references.

AUTHOR'S SOLUTION:

Author's solution can be found here.

This question is marked "community wiki".

asked 15 Dec '18, 17:57

aman_58472's gravatar image

4★aman_58472
11
accept rate: 0%

edited 16 Dec '18, 09:15

admin's gravatar image

0★admin ♦♦
19.7k350498541

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:

×15,490
×2,086
×1,648
×24
×13

question asked: 15 Dec '18, 17:57

question was seen: 89 times

last updated: 16 Dec '18, 09:15