Substring (Codeforces 919D)
Tags: DP, dfs and similar

You are given a graph with $$$n$$$ nodes and $$$m$$$ directed edges. One lowercase letter is assigned to each node. We define a path's value as the number of the most frequently occurring letter. For example, if letters on a path are "abaca", then the value of that path is $$$3$$$. Your task is find a path whose value is the largest.

Input: The first line contains two positive integers $$$n, m$$$ ($$$1 \leq n, m \leq 300\,000$$$), denoting that the graph has $$$n$$$ nodes and $$$m$$$ directed edges.The second line contains a string $$$s$$$ with only lowercase English letters. The $$$i$$$-th character is the letter assigned to the $$$i$$$-th node.Then $$$m$$$ lines follow. Each line contains two integers $$$x, y$$$ ($$$1 \leq x, y \leq n$$$), describing a directed edge from $$$x$$$ to $$$y$$$. Note that $$$x$$$ can be equal to $$$y$$$ and there can be multiple edges between $$$x$$$ and $$$y$$$. Also the graph can be not connected.

Output: Output a single line with a single integer denoting the largest value. If the value can be arbitrarily large, output -1 instead.

Note: In the first sample, the path with largest value is $$$1 \to 3 \to 4 \to 5$$$. The value is $$$3$$$ because the letter 'a' appears $$$3$$$ times.

Sample Inputs:
5 4
abaca
1 2
1 3
3 4
4 5

6 6
xzyabc
1 2
3 1
2 3
5 4
4 3
6 4

10 14
xzyzyzyzqx
1 2
2 4
3 5
4 5
2 6
6 8
6 5
2 10
3 9
10 9
4 6
1 10
2 8
3 7

Sample Outputs:
3

-1

4

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def topological_sort():
    (q, k) = ([], 0)
    cnt = [0] * (n + 1)
    for i in range(1, n + 1):
        for l in range(s0[i], s0[i + 1]):
            j = G[l]
            cnt[j] += 1
    for i in range(1, n + 1):
        if not cnt[i]:
            q.append(i)
    while len(q) ^ k:
        i = q[k]
        for l in range(s0[i], s0[i + 1]):
            j = G[l]
            cnt[j] -= 1
            if not cnt[j]:
                q.append(j)
        k += 1
    return q

def f(u, v):
    return u * 26 + v
(n, m) = map(int, input().split())
s = [0] + list(input().rstrip())
s0 = [0] * (n + 3)
v = []
for _ in range(m):
    (x, y) = map(int, input().split())
    s0[x + 2] += 1
    v.append(x)
    v.append(y)
for i in range(1, n + 3):
    s0[i] += s0[i - 1]
G = [0] * m
for i in range(m):
    (x, y) = (v[2 * i], v[2 * i + 1])
    G[s0[x + 1]] = y
    s0[x + 1] += 1
g = topological_sort()
if len(g) ^ n:
    ans = -1
    print(ans)
    exit()
dp = [0] * (26 * (n + 1))
for i in g:
    dp[f(i, s[i] - 97)] += 1
    for j in range(26):
        dp0 = dp[f(i, j)]
        for l in range(s0[i], s0[i + 1]):
            k = G[l]
            u = f(k, j)
            dp[u] = max(dp[u], dp0)
ans = max(dp)
print(ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def topological_sort():
    (q, k) = ([], 0)
    cnt = [0] * (n + 1)
    for i in range(1, n + 1):
        for l in range(s0[i], s0[i + 1]):
            j = G[l]
            cnt[j] += 1
    for i in range(1, n + 1):
        if not cnt[i]:
            q.append(i)
    while len(q) ^ k:
        i = q[k]
        for l in range(s0[i], s0[i + 1]):
            j = G[l]
            cnt[j] -= 1
            if not cnt[j]:
                q.append(j)
        k += 1
    return q

def f(u, v):
    return u * 26 + v
(n, m) = map(int, input().split())
s = [0] + list(input().rstrip())
s0 = [0] * (n + 3)
v = []
for _ in range(m):
    (x, y) = map(int, input().split())
    s0[x + 2] += 1
    v.append((x, y))
for i in range(1, n + 3):
    s0[i] += s0[i - 1]
G = [0] * m
for (x, y) in v:
    G[s0[x + 1]] = y
    s0[x + 1] += 1
g = topological_sort()
if len(g) ^ n:
    ans = -1
    print(ans)
    exit()
dp = [0] * (26 * (n + 1))
for i in g:
    dp[f(i, s[i] - 97)] += 1
    for j in range(26):
        dp0 = dp[f(i, j)]
        for l in range(s0[i], s0[i + 1]):
            k = G[l]
            u = f(k, j)
            dp[u] = max(dp[u], dp0)
ans = max(dp)
print(ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def topological_sort():
    (q, k) = ([], 0)
    cnt = [0] * (n + 1)
    for i in range(1, n + 1):
        for j in G[i]:
            cnt[j] += 1
    for i in range(1, n + 1):
        if not cnt[i]:
            q.append(i)
    while len(q) ^ k:
        i = q[k]
        for j in G[i]:
            cnt[j] -= 1
            if not cnt[j]:
                q.append(j)
        k += 1
    return q

def f(u, v):
    return u * 26 + v
(n, m) = map(int, input().split())
s = [0] + list(input().rstrip())
G = [[] for _ in range(n + 1)]
for _ in range(m):
    (x, y) = map(int, input().split())
    G[x].append(y)
g = topological_sort()
if len(g) ^ n:
    ans = -1
    print(ans)
    exit()
dp = [0] * (26 * (n + 1))
for i in g:
    dp[f(i, s[i] - 97)] += 1
    for j in range(26):
        dp0 = dp[f(i, j)]
        for k in G[i]:
            u = f(k, j)
            dp[u] = max(dp[u], dp0)
ans = max(dp)
print(ans)