Submission #1353190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1353190		vjudge1	Palinilap (COI16_palinilap)	Pypy 3	100 / 100	332 ms	309264 KiB

palinilap

import sys

def solve():
    # Read all contents from standard input
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    w = input_data[0]
    n = len(w)
    
    # 1. Manacher's Algorithm to find maximal palindromic bounds
    T = ['#'] * (2 * n + 1)
    for i in range(n):
        T[2 * i + 1] = w[i]
        
    P = [0] * len(T)
    C = R = 0
    for i in range(len(T)):
        i_mirror = 2 * C - i
        if R > i:
            P[i] = min(R - i, P[i_mirror])
        else:
            P[i] = 0
            
        while i - 1 - P[i] >= 0 and i + 1 + P[i] < len(T) and T[i - 1 - P[i]] == T[i + 1 + P[i]]:
            P[i] += 1
            
        if i + P[i] > R:
            C = i
            R = i + P[i]
            
    # 2. Difference Array technique to count covering palindromes
    D2 = [0] * (n + 5)
    for i in range(1, 2 * n):
        if P[i] == 0:
            continue
        if i % 2 == 1:       # Center is exactly on a character
            c = i // 2
            k = P[i] // 2
            L = c - k
            D2[L] += 1
            D2[L + k + 1] -= 2
            D2[L + 2 * k + 2] += 1
        else:                # Center is between two characters
            c = i // 2
            k = P[i] // 2
            L = c - k
            D2[L] += 1
            D2[L + k] -= 1
            D2[L + k + 1] -= 1
            D2[L + 2 * k + 1] += 1

    A = [0] * (n + 5)
    d1_curr = 0
    a_curr = 0
    for p in range(n):
        d1_curr += D2[p]
        a_curr += d1_curr
        A[p] = a_curr
        
    lost = [0] * n
    for p in range(n):
        # A[p] holds total valid palindromic coverages
        # (P[2 * p + 1] // 2 + 1) offsets the unaffected identically centered palindromes
        lost[p] = A[p] - (P[2 * p + 1] // 2 + 1)
        
    # 3. Initial baseline Weight W
    W = 0
    for i in range(1, 2 * n):
        W += P[i] // 2 + (i % 2)
        
    # 4. Double Hashing constraints initialization mapping the String and its Reverse
    M1, B1 = 10**9 + 7, 313
    M2, B2 = 10**9 + 9, 317
    
    P1_pow = [1] * (n + 1)
    P2_pow = [1] * (n + 1)
    for i in range(1, n + 1):
        P1_pow[i] = (P1_pow[i - 1] * B1) % M1
        P2_pow[i] = (P2_pow[i - 1] * B2) % M2
        
    H1, H2 = [0] * (n + 1), [0] * (n + 1)
    HR1, HR2 = [0] * (n + 1), [0] * (n + 1)
    
    w_rev = w[::-1]
    
    for i in range(n):
        H1[i + 1] = (H1[i] * B1 + ord(w[i])) % M1
        H2[i + 1] = (H2[i] * B2 + ord(w[i])) % M2
        HR1[i + 1] = (HR1[i] * B1 + ord(w_rev[i])) % M1
        HR2[i + 1] = (HR2[i] * B2 + ord(w_rev[i])) % M2
        
    # 5. Build Gained palindromes tracking
    gain = [[0] * 26 for _ in range(n)]
    
    for i in range(1, 2 * n):
        c, k = i // 2, P[i] // 2
        
        # Mismatch bounds
        if i % 2 == 1:
            L, R = c - k - 1, c + k + 1
        else:
            L, R = c - k - 1, c + k
            
        if L >= 0 and R < n:
            p1, p2 = L - 1, R + 1
            low = 1
            high = p1 + 1 if p1 + 1 < n - p2 else n - p2
            ans_lcp = 0
            idx_rev = n - 1 - p1
            
            # Binary search to verify LCP beyond the patched character
            while low <= high:
                mid = (low + high) >> 1
                
                r_rev = idx_rev + mid - 1
                h1_1 = (HR1[r_rev + 1] - HR1[idx_rev] * P1_pow[mid]) % M1
                h1_2 = (HR2[r_rev + 1] - HR2[idx_rev] * P2_pow[mid]) % M2
                
                r_fwd = p2 + mid - 1
                h2_1 = (H1[r_fwd + 1] - H1[p2] * P1_pow[mid]) % M1
                h2_2 = (H2[r_fwd + 1] - H2[p2] * P2_pow[mid]) % M2
                
                if h1_1 == h2_1 and h1_2 == h2_2:
                    ans_lcp = mid
                    low = mid + 1
                else:
                    high = mid - 1
                    
            E = ans_lcp
            
            # Formulating 1 bridge character fixes the current layout + matches E bounds outer
            gain[L][ord(w[R]) - 97] += E + 1
            gain[R][ord(w[L]) - 97] += E + 1
            
    # 6. Assess optimum change and construct Maximum Value
    ans = W
    for p in range(n):
        orig_char = ord(w[p]) - 97
        base_val = W - lost[p]
        gain_p = gain[p]
        for chr_dest in range(26):
            if chr_dest != orig_char:
                cand = base_val + gain_p[chr_dest]
                if cand > ans:
                    ans = cand
                    
    print(ans)

solve()

Compilation message (stdout)

Compiling 'palinilap.py'...

=======
  adding: __main__.pyc (deflated 46%)

=======

• Subtask 1: 17 / 17
• Subtask 2: 37 / 37
• Subtask 3: 46 / 46