Problem:


Score : 1200 points

Problem Statement

In Takahashi's mind, there is always an integer sequence of length 2 \times 10^9 + 1: A = (A_{-10^9}, A_{-10^9 + 1}, ..., A_{10^9 - 1}, A_{10^9}) and an integer P.

Initially, all the elements in the sequence A in Takahashi's mind are 0, and the value of the integer P is 0.

When Takahashi eats symbols +, -, > and <, the sequence A and the integer P will change as follows:

When he eats +, the value of A_P increases by 1;

When he eats -, the value of A_P decreases by 1;

When he eats >, the value of P increases by 1;

When he eats <, the value of P decreases by 1.

Takahashi has a string S of length N. Each character in S is one of the symbols +, -, > and <.
He chose a pair of integers (i, j) such that 1 \leq i \leq j \leq N and ate the symbols that are the i-th, (i+1)-th, ..., j-th characters in S, in this order.
We heard that, after he finished eating, the sequence A became the same as if he had eaten all the symbols in S from first to last.
How many such possible pairs (i, j) are there?

Constraints

1 \leq N \leq 250000

|S| = N

Each character in S is +, -, > or <.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

5
+>+<-

Sample Output 1

3

If Takahashi eats all the symbols in S, A_1 = 1 and all other elements would be 0.
The pairs (i, j) that leads to the same sequence A are as follows:

(1, 5)

(2, 3)

(2, 4)

Sample Input 2

5
+>+-<

Sample Output 2

5

Note that the value of P may be different from the value when Takahashi eats all the symbols in S.

Sample Input 3

48
-+><<><><><>>>+-<<>->>><<><<-+<>><+<<>+><-+->><<

Sample Output 3

475



Sample input:
5
+>+<-


Sample output:
3

Submission status: Wrong Answer

Solution code:
import random
from collections import defaultdict


def solve(n, s, xs, m):
    ans = [10 ** 9] * (n + 1)
    for x in xs:
        p = 0
        h = 0
        y = 1
        r = pow(x, m - 2, m)
        pos = [0] * (n + 1)
        hashes = [0] * (n + 1)
        for i, c in enumerate(s, start=1):
            if c == '>':
                p += 1
                y = y * x % m
            elif c == '<':
                p -= 1
                y = y * r % m
            elif c == '+':
                h = (h + y) % m
            else:
                h = (h - y) % m
            pos[i] = p
            hashes[i] = h

        pow_x = [1]
        for _ in range(max(pos)):
            pow_x.append(pow_x[-1] * x % m)
        mp = min(pos)
        if mp < 0:
            pow_x.append(pow(r, -mp, m))
            for _ in range(-mp + 1):
                pow_x.append(pow_x[-1] * x % m)

        ideal = hashes[-1]
        required = defaultdict(lambda: 0)
        for i, (p, h) in enumerate(zip(pos, hashes)):
            ans[i] = min(ans[i], required[h])
            req = (ideal * pow_x[p] + h) % m
            required[req] += 1

    return sum(ans)


n = int(input())
s = input()

xs = random.sample(range(10 ** 9, 10 ** 10), 3)
m = 2305843009213693951
print(solve(n, s, xs, m))

Submission status: Wrong Answer

Solution code:
import random
from collections import defaultdict


def solve(n, s, x, m):
    p = 0
    h = 0
    y = 1
    r = pow(x, m - 2, m)
    pos = [0] * (n + 1)
    hashes = [0] * (n + 1)
    for i, c in enumerate(s, start=1):
        if c == '>':
            p += 1
            y = y * x % m
        elif c == '<':
            p -= 1
            y = y * r % m
        elif c == '+':
            h = (h + y) % m
        else:
            h = (h - y) % m
        pos[i] = p
        hashes[i] = h

    pow_x = [1]
    for _ in range(max(pos)):
        pow_x.append(pow_x[-1] * x % m)
    mp = min(pos)
    if mp < 0:
        pow_x.append(pow(r, -mp, m))
        for _ in range(-mp + 1):
            pow_x.append(pow_x[-1] * x % m)

    ans = 0
    ideal = hashes[-1]
    required = defaultdict(lambda: 0)
    for p, h in zip(pos, hashes):
        ans += required[h]
        req = (ideal * pow_x[p] + h) % m
        required[req] += 1
    return ans


n = int(input())
s = input()

xs = random.sample(range(10 ** 9, 10 ** 10), 5)
m = 2305843009213693951
ans = min(solve(n, s, x, m) for x in xs)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def takahashi(s):
    a = defaultdict(lambda: 0)
    P = 0
    for c in s:
        if c == '+':
            a[P] += 1
        elif c == '-':
            a[P] -= 1
        elif c == '>':
            P += 1
        else:
            P -= 1
    keys = a.keys()
    return {k:v for k, v in a.items() if v != 0}

def main():
    N = int(input())
    s = input()
    ans = takahashi(s)
    # print(ans)
    n = 0
    for i in range(N):
        for j in range(i+1, N+1):
            # print(s[i:j], takahashi(s[i:j]) == ans)
            if takahashi(s[i:j]) == ans:
                n += 1
    print(n)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = str(input())

all_eaten = [0] * (2 * N + 1)
p = N
for i in S:
    if i == ">":
        p += 1
    elif i == "<":
        p -= 1
    elif i == "+":
        all_eaten[p] += 1
    elif i == "-":
        all_eaten[p] -= 1

counter = 0
for i in range(1, N+1):
    for j in range(i, N+1):
        part_eaten = [0] * (2 * N + 1)
        p = N
        s = S[i-1:j]
        for k in s:
            if k == ">":
                p += 1
            elif k == "<":
                p -= 1
            elif k == "+":
                part_eaten[p] += 1
            elif k == "-":
                part_eaten[p] -= 1
        if part_eaten == all_eaten:
            counter += 1


print(counter)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def takahashi(s):
    a = defaultdict(lambda: 0)
    P = 0
    for c in s:
        if c == '+':
            a[P] += 1
        elif c == '-':
            a[P] -= 1
        elif c == '>':
            P += 1
        else:
            P -= 1
    keys = a.keys()
    return {k:v for k, v in a.items() if v != 0}

def main():
    N = int(input())
    s = input()
    ans = takahashi(s)
    # print(ans)
    n = 0
    for i in range(N):
        for j in range(i+1, N+1):
            # print(s[i:j], takahashi(s[i:j]) == ans)
            if takahashi(s[i:j]) == ans:
                n += 1
    print(n)

main()

Submission status: Accepted

Solution code:
import random
from collections import defaultdict


def solve(n, s, xs, m):
    ans = [10 ** 9] * (n + 1)
    for x in xs:
        p = 0
        h = 0
        y = 1
        r = pow(x, m - 2, m)
        pos = [0] * (n + 1)
        hashes = [0] * (n + 1)
        for i, c in enumerate(s, start=1):
            if c == '>':
                p += 1
                y = y * x % m
            elif c == '<':
                p -= 1
                y = y * r % m
            elif c == '+':
                h = (h + y) % m
            else:
                h = (h - y) % m
            pos[i] = p
            hashes[i] = h

        pow_x = [1]
        for _ in range(max(pos)):
            pow_x.append(pow_x[-1] * x % m)
        mp = min(pos)
        if mp < 0:
            pow_x.append(pow(r, -mp, m))
            for _ in range(-mp - 1):
                pow_x.append(pow_x[-1] * x % m)

        ideal = hashes[-1]
        required = defaultdict(lambda: 0)
        for i, (p, h) in enumerate(zip(pos, hashes)):
            ans[i] = min(ans[i], required[h])
            req = (ideal * pow_x[p] + h) % m
            required[req] += 1

    return sum(ans)


n = int(input())
s = input()

xs = random.sample(range(10 ** 9, 10 ** 10), 3)
m = 2305843009213693951
print(solve(n, s, xs, m))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
from collections import defaultdict

N = int(readline())
S = np.frombuffer(read().rstrip(),'S1')

MOD = 10**9 + 7

Sright = (S==b'>')
Sleft = (S==b'<')
Sadd = (S==b'+')
Ssub = (S==b'-')

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def calc_hash_data(MOD,base):
    inv = pow(base,MOD-2,MOD)
    x = np.ones(N+1,dtype=np.int64)
    x[1:][Sright] = base
    x[1:][Sleft] = inv
    power = cumprod(x,MOD)
    x = np.pad(power[1:] * Sadd - power[1:] * Ssub,(1,0),mode='constant')
    np.cumsum(x,out=x); x %= MOD
    return power,x

b1 = 123450
b2 = 314159
pow1,H1 = calc_hash_data(MOD,b1)
pow2,H2 = calc_hash_data(MOD,b2)

X1 = (H1+H1[-1]*pow1)%MOD
X2 = (H2+H2[-1]*pow2)%MOD
X = (X1<<32)^X2

H = (H1<<32)^H2

# x[i] == H[j] となる i<j の個数を答える

X = X.tolist(); H = H.tolist()
counter = defaultdict(int)
for h in H:
    counter[h] += 1

answer = 0
for x,h in zip(X,H):
    counter[h] -= 1
    answer += counter[x]

print(answer)