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

×

How to solve ITRIX12E from SPOJ?

I have been trying to solve ITRIX12E - R Numbers since very long unfortunately I couldn't solve this. Can anyone please help in solving this problem.

asked 13 May, 15:12

arpit728's gravatar image

2★arpit728
6831149
accept rate: 10%


Matrix exponentiation should work i think so

Let say dp[i][j] denoted the number of R-numbers of length i ending with j

So dp[i][1]=dp[i-1][1]+dp[i-1][2]+dp[i-1][4]+dp[i-1][6]

..

..

..

dp[i][9]=dp[i-1][2]+dp[i-1][4]+dp[i-1][8]

So we have to calculate ,sum(dp[n][j]) for all j

We can represent this with matrix :

N.                          N-1

1. |1 1 0 1 0 1 0 0 0| 1 2. |.................|. 2 3. |..................| 3 4. |..................| 4 5 = |.................|* 5 6. |.................|. 6 7. |.................|. 7 8. |.................|. 8 9. |.................|. 9

So we get a matrix ,dp[n]=X*dp[n-1]

We can expand,dp[n-1] similarly

So dp[n]=X^(n-1)*dp[1]

`

link

answered 13 May, 19:27

vivek_1998299's gravatar image

6★vivek_1998299
1.3k29
accept rate: 22%

edited 18 May, 10:53

@vijju123 do u know how to correct this latex issue,in preview it was showing

(13 May, 20:03) vivek_19982996★

@vivek_1998299

dp[i][1]=dp[i-1][2]+dp[i-1][4]+dp[i-1][6] ........dp[i][9]

Can you please explain why dp[i][9] has been included and dp[i-1][1] is missing since 2 is also the prime no.

(17 May, 10:00) arpit7282★

dp[i][9] is not included

That ...... means the recurrence relation for dp[i][2],dp[i][3] upto dp[i][9]

(17 May, 10:54) vivek_19982996★

@vivek_1998299

and why dp[i-1][1] is not included in dp[i][1] since here 1+1 will produce 2 which is prime no.

(18 May, 08:31) arpit7282★

@vivek_1998299

dp[2][1]=3 dp[2][2]=4 dp[2][3]=3 dp[2][4]=4 dp[2][5]=3 dp[2][6]=3 dp[2][7]=2 dp[2][8]=3 dp[2][9]=3

If we add them all then it becomes 28, but answer when n=2 is 30

(18 May, 09:10) arpit7282★

Yeah dp[i-1][1] should be there,i havemt wrote the exact equations,just written so u could get what i mean.

By the wayy for n=30,ans is 29,and in ur above case dp[2][1]=4,so ur ans is also 29

Sum of R-nos of length less than equal to 2 =4+29=33

(18 May, 10:50) vivek_19982996★
showing 5 of 6 show all
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:

×1,599
×1,071
×251
×118

question asked: 13 May, 15:12

question was seen: 176 times

last updated: 18 May, 10:53