anupamshah_'s blog

By anupamshah_, history, 4 years ago, In English

How to solve the following recurrence relation for N ≤109

F(n)=F(n−1)+F(n−2)+F(n−1)∗F(n−2)

(Assuming that we are provided with the values of F(1) and F(2) )

(EDIT: The problem link is attached.)

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it

By anupamshah_, history, 4 years ago, In English

Here is the link to the problem . I have gone through the editorial but didn't got the approach ( Although I got that we don't need to take more than 2 occurences of a partical triplet [x1,x1+1,x1+2] ) ,I was thinking of DP with three states position i, frequency of i-1th character we took and frequency of i-2nd character we took.

But wasn't able to come up with a solution. Can anybody help me with the solution ?

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

By anupamshah_, history, 5 years ago, In English

How to approach Constructive Algorithm problems?

Can you share some of the good problems ?

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it