_Charizard_'s blog

By _Charizard_, 4 weeks ago, In English

Today I was trying to solve the problem CF R1600 — Camp Schedule. I realized that I will need the longest prefix of a string which is also a suffix of that string. I searched it on google and found that it is called 'Prefix Function'. I tried to understand this concept from the CP Algorithms article, but I am too dumb to understand it.

Though I got the code from there what I needed, I can't understand how it works. Can anyone please help me to understand this concept? (with some examples?)

Prefix Function Code

Note: I am very new to this type of algorithms.

Read more »

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

By _Charizard_, history, 6 weeks ago, In English

As I am very new to dynamic programming I am facing many problems in understanding the states of the DP. Here is a problem which I have tried to solve by iterative method but failed. Can anyone please help me with this problem by giving me a bit description on how to understand the states of this type of problems?

Problem Statement: Find a sub-sequence $$$(a_{b1}, a_{b2}, a_{b3},\dots)$$$ of array $$$a$$$ of size $$$n(n < 1001)$$$ to maximize the following expression: $$$1*a_{b1} + 2*a_{b2} + 3*a_{b3} + \dots$$$. Print the maximum value of the expression.

Read more »

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