In the contest yesterday Codeforces Round 698 (Div. 1) I submitted 1477B - Nezzar и бинарная строка two times (105735241 and 105747088), both of the got verdict "TLE on pretest 2". So I spent much time trying to find the reason but failed. Today I just submitted the exactly same code as 105747088, and its verdict changed to "WA on test 2"! (105792669)

The truth is the code was wrong, so WA is the correct verdict. But where did TLE come from?

Could anyone explain about it to me? Thanks a lot!

Summary: This blog gives a solution to 835D - Палиндромная характеристика which uses Palindromic Tree (also named Palindromic Automaton) and works in $$$O(n)$$$ time.

Solution

(we define "palindromic level" of string $$$s$$$ as the maximum $$$k$$$ that satisfies $$$s$$$ is $$$k$$$-palindromic)

Consider the $$$O(n^2)$$$ DP solution: let $$$dp[l][r]$$$ be the palindromic level of substring $$$[l,r]$$$. It is obvious that $$$dp[l][r]\ne 0$$$ only if substring $$$[l,r]$$$ is a palindrome. So only the palindromic substrings are useful DP states.

There is an important property of palindromes: there are only $$$O(n)$$$ different palindromic substrings in a string with length $$$n$$$, where the same string appearing in different positions are considered same. This is because if there are two palindromes with lengths $$$l_1$$$ and $$$l_2$$$ ending in a position $$$i$$$ ($$$l_2<l_1\le i$$$), then the substring $$$[i-l_2+1,i-l_2+l_1]$$$ is the same as $$$[i-l_1+1,i]$$$, for they are in the symmetrical positions of the palindrome $$$[i-l_2+1,i]$$$. According to this we can build a Palindromic Automaton and each vertex on the Palindromic Tree corresponds with a unique palindromic substring. Then we can easily express a palindromic substring with the corresponding vertex on the Palindromic Automaton. Let $$$dp[x]$$$ be the palindromic level of vertex $$$x$$$.

The transferring method is obvious. If there exists vertex $$$y$$$ satisfying $$$len[y]=[\frac{len[x]}{2}]$$$ ($$$len[x]$$$ denotes the length of corresponding substring of vertex $$$x$$$) then $$$dp[x]=dp[y]+1$$$. Otherwise, $$$dp[x]=1$$$.

Now let's see how to determine for each $$$x$$$ whether there exists a vertex $$$y$$$. Let $$$bd[x]$$$ be the longest palindromic suffix of $$$x$$$ which length doesn't exceed half of $$$len[x]$$$. When we create a new vertex $$$x$$$, we find vertex $$$p$$$, the substring left by cutting out the first and the last characters of string $$$x$$$. We iterate from $$$v=bd[p]$$$, each time we replace $$$v$$$ with $$$fail[v]$$$, until its corresponding son can be valid $$$bd[x]$$$. See my code to learn more details about this process.

Finally, the problem asks for substrings which differs in position, but we answered substrings which differs in contents. So we have to calculate $$$sz[x]$$$, the size of subtree for each $$$x$$$. $$$sz[x]$$$ is also the number of appearances of substring $$$x$$$.

It's obvious that this solution works in $$$O(n)$$$ time.

My AC code is here: 55849948

Summary: This blog talks about solving two kinds of simple recursions: F(n + 1) = aF(n) + b and F(n + 1) = aF(n) + bF(n - 1)

1. Preliminary Knowledge

(1) The solution of recursion F(n + 1) = aF(n) is F(n) = a^n - 1F(1).

(2) The solution of recursion F(n + 1) = F(n) + a is F(n) = (n - 1)a + F(1).

(3) The recursion F(n + 1) = kF(n) is the same as F(n) = kF(n - 1), also F(n + 1) = aF(n) + bF(n - 1) is the same as F(n) = aF(n - 1) + bF(n - 2) in this blog.

2. Solving F(n + 1) = aF(n) + b, a, b are constants, a > 1

The main idea is to create another function G(n) that satisfy G(n) = kG(n - 1) with constant k, solve G(n), and then solve F(n).

F(n + 1) = aF(n) + b

Let we have

G(n) = aG(n - 1)

G(n) = a^n - 1G(1)

3. Solving F(n + 1) = aF(n) + bF(n - 1), a, b are constants

The main idea is also to create G(n), but the method is different, and the function G(n) is more complicated.

F(n + 1) = aF(n) + bF(n - 1)

Let α, β be two real numbers that satisfy α + β = a, αβ =  - b, α ≤ β we have

F(n + 1) = (α + β)F(n) - αβF(n - 1)

F(n + 1) - αF(n) = βF(n) - αβF(n - 1)

F(n + 1) - αF(n) = β(F(n) - αF(n - 1))

Let G(n) = F(n + 1) - αF(n), also we have G(n - 1) = F(n) - αF(n - 1)

G(n) = βG(n - 1), therefore G(n + 1) = βG(n)

G(n) = β^n - 1G(1)

F(n + 1) - αF(n) = β^n - 1(F(2) - αF(1)) (1)

Similarly, because of F(n + 1) = (α + β)F(n) - αβF(n - 1) we have

F(n + 1) - βF(n) = αF(n) - αβF(n - 1)

F(n + 1) - βF(n) = α(F(n) - βF(n - 1))

Let H(n) = F(n + 1) - βF(n) we have H(n - 1) = F(n) - βF(n - 1)

H(n) = αH(n - 1), therefore H(n + 1) = αH(n)

H(n) = α^n - 1H(1)

F(n + 1) - βF(n) = α^n - 1(F(2) - βF(1)) (2)

Suppose that α ≠ β

(2) - (1) we have

(α - β)F(n) = α^n - 1(F(2) - βF(1)) - β^n - 1(F(2) - αF(1))

How to get the proper α, β?

According to the Vieta Theorem, α, β is the two solutions of quadratic equation x² - ax - b = 0.

Of course, we only talk about α ≠ β, a² ≠  - 4b.

Just solving the quadratic equation is OK. (You can get the formula for solving a quadratic equation from the problem 530A - Quadratic equation.)

This equation is called the characteristic equation.

Example: Solve the Fibonacci sequence F(1) = 1, F(2) = 1, F(n) = F(n - 1) + F(n - 2).

Solution: Here we have

(because we have )

What will happen if α = β, a² = 4b?

I am sorry that I cannot solve it yet.

I'll try to solve it later.

UPD: This method can be used to solve the recursions with lengths more than 2.

We replace the quadratic equation with an equation with higher degree, and do the same thing as quadratic.

This is suncongbo's blog. This entry is just for testing.

Markdown Test

Markdown Test

MD Test:

MD Test:

Created, edited and deleted successfully.

Inline Code: int main() { printf("Hello World!\n"); //Hello world }

Reference:

suncongbo refers to me at 20171013

suncongbo refers to me at 20180530

Codeforces Round 439 (Div. 2)

438A - Ребенок и игрушка refers to a contest by vfleaking

Block Code: Empty lines are now allowed in the code. An empty line is requested above the code.

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 2e5;
const int C = 1e6;
const int INF = 1e8;
struct Edge {int nxt,v,w;} e[(N<<1)+2];
int tmp[N+2];
int t[C+2];
int dis[N+2];
int dep[N+2];
int fe[N+2];
int sz[N+2];
int cur[N+2];
bool vis[N+2];
int n,m,mn,c,rt,siz,ans,tp;
void addedge(int u,int v,int w)
{
    m++; e[m].v = v; e[m].w = w;
    e[m].nxt = fe[u]; fe[u] = m;
}
void getroot(int u,int prv)
{
    sz[u] = 1; cur[u] = 0;
    for(int i=fe[u]; i; i=e[i].nxt)
    {
        if(e[i].v==prv || vis[e[i].v]==true) continue;
        getroot(e[i].v,u);
        sz[u] += sz[e[i].v]; cur[u] = max(cur[u],sz[e[i].v]);
    }
    cur[u] = max(cur[u],siz-sz[u]);
    if(cur[u]<mn) {mn = cur[u]; rt = u;}
}
void dfs(int u,int prv)
{
	tp++; tmp[tp] = u;
	for(int i=fe[u]; i; i=e[i].nxt)
	{
		if(vis[e[i].v]==true || e[i].v==prv) continue;
		dep[e[i].v] = dep[u]+1; dis[e[i].v] = dis[u]+e[i].w;
		if(dis[e[i].v]>c) dis[e[i].v] = c+1;
		dfs(e[i].v,u);
	}
}
void pdc(int u)
{
	vis[u] = true;
    tp = 0;
	for(int i=fe[u]; i; i=e[i].nxt)
	{
		if(vis[e[i].v]==true) continue;
		dis[e[i].v] = e[i].w; dep[e[i].v] = 1; 
		dfs(e[i].v,u);
		for(int j=1; j<=tp; j++) {if(dis[tmp[j]]<c) ans = min(ans,t[c-dis[tmp[j]]]+dep[tmp[j]]);}
		for(int j=1; j<=tp; j++) {if(dis[tmp[j]]<=c) t[dis[tmp[j]]] = min(t[dis[tmp[j]]],dep[tmp[j]]);}
		ans = min(ans,t[c]);
	}
	for(int i=1; i<=tp; i++) {if(dis[tmp[i]]<=c) t[dis[tmp[i]]] = INF;}
	for(int i=fe[u]; i; i=e[i].nxt)
	{
		if(vis[e[i].v]==true) continue;
		rt = 0; mn = INF; siz = sz[e[i].v];
		getroot(e[i].v,0); pdc(rt);
	}
}
int main()
{
    scanf("%d%d",&n,&c); m = 0;
    if(c==0) {puts("0"); return 0;}
    for(int i=1; i<n; i++)
    {
        int x,y,z; scanf("%d%d%d",&x,&y,&z); x++; y++;
        if(z>c) z = c+1;
        addedge(x,y,z); addedge(y,x,z);
    }
    for(int i=1; i<=c; i++) t[i] = INF;
    siz = sz[1] = n; rt = 0; ans = INF; mn = INF;
    getroot(1,0); pdc(rt);
    printf("%d\n",ans==INF ? -1 : ans);
    return 0;
}

Saved as a draft: "You are not allowed to view the requested page"

Deleted: "No such topic"

Have not yet been published: "No such blog entry"