Are the test cases weak for the 4th question?

Once you get f(n+1) = 3*f(n) — f(n-1) + n you can solve it directly using matrix exponentiation. You don't need to reduce it again to a function g(n).

F(n+1) = 3*F(n) + (-1)*F(n-1) + 0*F(n-2) + 1*n

F(n) = 1*F(n) + 0*F(n-1) + 0*F(n-2) + 0*n

F(n-1) = 0*F(n) + 1*F(n-1) + 0*F(n-2) + 0*n

n = 0*F(n) + 0*F(n-1) + 0*F(n-2) + 1*n

You can express the 4 eq's in the form of a matrix.

Link:- http://zobayer.blogspot.in/2010/11/matrix-exponentiation.html.

I solved this problem using Hashing.

Here goes my idea:-

1) First I would hash the given string and its reverse.

2) Then If H1 is the hash of the 1st string(s1) and H2 is the hash of the 2nd string(s2 reverse string) then I would say that s1[1...L] is represented by a value equal to H1[L](An Integer) and s1[L+1...R] = H1[L+1...R] = H1[R]-H1[L]*Power(R-L+1).(Compute all the powers first)

3) Now I would say that if s1[1...i] = s2[N-i+1,N] then H1[i] = H2[N-i+1,N].

4) So I would iterate i from 1 to N-1.

5) Now I would say that the given string is an "alindrome" if H1[1...i] = H2[N-i+1,N] and H1[i+1...N] = H2[1.....N-i];(For any i)

6) Else if s1==s2 then a palindrome.

7) Otherwise, it would be simple.

Here is my Source Code:- http://ideone.com/ugA4Es

Still, if you want to know where your went wrong u can check your code with the test cases in udebug.

They were given in an atcoder problem.

Hey, it would be a way better if you add Lightoj also.

Even I use Mo's algorithm to solve this question, in addition, I do a binary search to find the larger number of occurrences, but I'm getting a W.A. I tried all the t.c. given in the forums and also in the U.V.Debug and my code satisfies for all those inputs. Here is my Code. Can u please tell me where I am going wrong or provide me a t.c. Thanks in advance.

Edit: -Sorry I was doing a small mistake.Thanks for t.c. given.

N is the length of the first string and M is the length of the second string. void Compute_Ways() { lli i,j;

rep(i,0,N+1)
{
    Ways[i][0]=1;
}

rep(i,0,M+1)
{
    Ways[0][i]=1;
}

rep(i,1,N+1)
{
    rep(j,1,M+1)
    {
        if(s[i-1]==s1[j-1])
        {
            Ways[i][j]=Ways[i-1][j-1];
        }
        else
        {
            if(LCS[i-1][j]==LCS[i][j-1])
            {
                Ways[i][j]=Ways[i-1][j]+Ways[i][j-1];
            }
            else
            {
                if(LCS[i-1][j]>LCS[i][j-1])
                Ways[i][j]=Ways[i-1][j];
                else
                Ways[i][j]=Ways[i][j-1];
            }
        }
    }
}

}

Now I get it. Thank you so much.

Auto comment: topic has been updated by desik (previous revision, new revision, compare).

Can someone please send me the code for K-th ancestor in a successor graph. I have understood the algorithm but still not clear about writing the code. Thanks in advance.

It's working for me now.You guys made some modifications. But the previous was a way better.

Stopstalk is not working I don't know why.

For undirected that is required but not for directed. For directed instack[i] is sufficient.

https://www.youtube.com/watch?v=fpGr2dk3UOoa