Torn Lucky Ticket (Codeforces 1895C)
Tags: Math, hashing

A ticket is a non-empty string of digits from $$$1$$$ to $$$9$$$.A lucky ticket is such a ticket that:   it has an even length;  the sum of digits in the first half is equal to the sum of digits in the second half. You are given $$$n$$$ ticket pieces $$$s_1, s_2, \dots, s_n$$$. How many pairs $$$(i, j)$$$ (for $$$1 \le i, j \le n$$$) are there such that $$$s_i + s_j$$$ is a lucky ticket? Note that it's possible that $$$i=j$$$.Here, the + operator denotes the concatenation of the two strings. For example, if $$$s_i$$$ is 13, and $$$s_j$$$ is 37, then $$$s_i + s_j$$$ is 1337.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of ticket pieces.The second line contains $$$n$$$ non-empty strings $$$s_1, s_2, \dots, s_n$$$, each of length at most $$$5$$$ and consisting only of digits from $$$1$$$ to $$$9$$$.

Output: Print a single integer — the number of pairs $$$(i, j)$$$ (for $$$1 \le i, j \le n$$$) such that $$$s_i + s_j$$$ is a lucky ticket.


Sample Inputs:
10
5 93746 59 3746 593 746 5937 46 59374 6

5
2 22 222 2222 22222

3
1 1 1

Sample Outputs:
20

13

9

Solution (Python):
from collections import defaultdict
MAX_DIGITS = 9

def solve(N, L):
    whole = [defaultdict(int) for _ in range(1 + MAX_DIGITS)]
    part = [defaultdict(int) for _ in range(1 + MAX_DIGITS)]
    for piece in L:
        s = len(piece)
        prefix = [0]
        for c in piece:
            prefix.append(prefix[-1] + ord(c) - ord('0'))
        sum = prefix[s]
        whole[s][sum] += 1
        part[s][sum] += 1
        for k in range(1, (s + 1) // 2):
            part[s - 2 * k][sum - 2 * prefix[k]] += 1
            part[s - 2 * k][2 * prefix[s - k] - sum] += 1
    result = 0
    for length in range(1, 1 + MAX_DIGITS):
        for (sum, count) in whole[length].items():
            result += count * part[length][sum]
    return result
if __name__ == '__main__':
    N = int(input())
    L = input().split()
    print(solve(N, L))

Solution (Python):
def solve(n, m):
    t = {i: {j: 0 for j in range(0, 45 + 1)} for i in range(1, 5 + 1)}
    for s in m:
        a = 0
        for i in s:
            a += int(i)
        t[len(s)][a] += 1
    res = 0
    for s in m:
        old_res = res
        if len(s) == 1:
            res += t[1][int(s[0])]
        elif len(s) == 2:
            res += t[2][int(s[0]) + int(s[1])]
        elif len(s) == 3:
            a = int(s[0])
            b = int(s[1])
            c = int(s[2])
            res += t[3][a + b + c]
            res += t[1].get(b + c - a, 0)
            res += t[1].get(a + b - c, 0)
        elif len(s) == 4:
            a = int(s[0])
            b = int(s[1])
            c = int(s[2])
            d = int(s[3])
            res += t[4][a + b + c + d]
            res += t[2].get(b + c + d - a, 0)
            res += t[2].get(a + b + c - d, 0)
        elif len(s) == 5:
            a = int(s[0])
            b = int(s[1])
            c = int(s[2])
            d = int(s[3])
            e = int(s[4])
            res += t[5][a + b + c + d + e]
            res += t[3].get(b + c + d + e - a, 0)
            res += t[3].get(a + b + c + d - e, 0)
            res += t[1].get(c + d + e - b - a, 0)
            res += t[1].get(a + b + c - d - e, 0)
    return res
n = int(input())
m = [i for i in input().split()]
print(solve(n, m))

Solution (Python):
import math
import os
import random
import re
import sys
from collections import *
from functools import lru_cache

def solute():
    n = int(sys.stdin.readline())
    s_list = list(map(lambda x: list(map(int, list(x))), sys.stdin.readline().split()))
    first_half = [defaultdict(int) for _ in range(6)]
    second_half = [defaultdict(int) for _ in range(6)]
    len_sum = [defaultdict(int) for _ in range(6)]
    for s in s_list:
        _sum = sum(s)
        len_sum[len(s)][_sum] += 1
        if len(s) == 5:
            first_half[5][_sum] += 1
            first_half[3][_sum - 2 * s[-1]] += 1
            first_half[1][sum(s[0:3]) - s[3] - s[4]] += 1
            second_half[3][_sum - 2 * s[0]] += 1
            second_half[1][sum(s[2:]) - s[0] - s[1]] += 1
        elif len(s) == 4:
            first_half[4][_sum] += 1
            first_half[2][_sum - 2 * s[-1]] += 1
            second_half[2][_sum - 2 * s[0]] += 1
        elif len(s) == 3:
            first_half[3][_sum] += 1
            first_half[1][_sum - 2 * s[-1]] += 1
            second_half[1][_sum - 2 * s[0]] += 1
        elif len(s) == 2:
            first_half[2][_sum] += 1
        else:
            first_half[1][_sum] += 1
    ans = 0
    for i in range(6):
        for key in first_half[i].keys():
            ans += first_half[i][key] * len_sum[i][key]
        for key in second_half[i].keys():
            ans += second_half[i][key] * len_sum[i][key]
    print(ans)
solute()