Pinball (Codeforces 1936B)
Tags: Math, two pointers

There is a one-dimensional grid of length $$$n$$$. The $$$i$$$-th cell of the grid contains a character $$$s_i$$$, which is either '<' or '>'.When a pinball is placed on one of the cells, it moves according to the following rules:   If the pinball is on the $$$i$$$-th cell and $$$s_i$$$ is '<', the pinball moves one cell to the left in the next second. If $$$s_i$$$ is '>', it moves one cell to the right.  After the pinball has moved, the character $$$s_i$$$ is inverted (i. e. if $$$s_i$$$ used to be '<', it becomes '>', and vice versa).  The pinball stops moving when it leaves the grid: either from the left border or from the right one. You need to answer $$$n$$$ independent queries. In the $$$i$$$-th query, a pinball will be placed on the $$$i$$$-th cell. Note that we always place a pinball on the initial grid.For each query, calculate how many seconds it takes the pinball to leave the grid. It can be shown that the pinball will always leave the grid within a finite number of steps.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$).The second line of each test case contains a string $$$s_1s_2 \ldots s_{n}$$$ of length $$$n$$$ consisting of characters '<' and '>'.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output: For each test case, for each $$$i$$$ ($$$1 \le i \le n$$$) output the answer if a pinball is initially placed on the $$$i$$$-th cell.

Note: In the first test case, the movement of the pinball for $$$i=1$$$ is shown in the following pictures. It takes the pinball $$$3$$$ seconds to leave the grid.  The movement of the pinball for $$$i=2$$$ is shown in the following pictures. It takes the pinball $$$6$$$ seconds to leave the grid.  

Sample Inputs:
3
3
><<
4
<<<<
6
<><<<>

Sample Outputs:
3 6 5 
1 2 3 4 
1 4 7 10 8 1

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    s = str(input())
    sl = []
    spr = []
    smsl = [0]
    smspr = [0]
    for i in range(n - 1, -1, -1):
        if s[i] == '<':
            spr.append(i)
            smspr.append(smspr[-1] + i)
    ans = []
    for i in range(n):
        if s[i] == '>':
            sl.append(i)
            smsl.append(smsl[-1] + i)
            if len(spr) >= len(sl):
                ans.append((smspr[-1] - smspr[-len(sl) - 1] - smsl[-1]) * 2 + i + 1)
            else:
                ans.append((smspr[-1] - smsl[-2] + smsl[-2 - len(spr)]) * 2 + n - i)
        else:
            spr.pop()
            smspr.pop()
            if len(spr) >= len(sl):
                ans.append((smspr[-1] - smspr[-len(sl) - 1] - smsl[-1]) * 2 + i + 1)
            else:
                ans.append((smspr[-1] + i - smsl[-1] + smsl[-2 - len(spr)]) * 2 + n - i)
    print(' '.join(map(str, ans)))

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    s = str(input())
    sl = []
    spr = []
    smsl = [0]
    smspr = [0]
    for i in range(n - 1, -1, -1):
        if s[i] == '<':
            spr.append(i)
            smspr.append(smspr[-1] + i)
    ans = []
    for i in range(n):
        if s[i] == '>':
            sl.append(i)
            smsl.append(smsl[-1] + i)
            if len(spr) >= len(sl):
                ans.append((smspr[-1] - smspr[-len(sl) - 1] - smsl[-1]) * 2 + i + 1)
            else:
                ans.append((smspr[-1] - smsl[-2] + smsl[-2 - len(spr)]) * 2 + n - i)
        else:
            spr.pop()
            smspr.pop()
            if len(spr) >= len(sl):
                ans.append((smspr[-1] - smspr[-len(sl) - 1] - smsl[-1]) * 2 + i + 1)
            else:
                ans.append((smspr[-1] + i - smsl[-1] + smsl[-2 - len(spr)]) * 2 + n - i)
    print(' '.join(map(str, ans)))

Solution (Python):
""""""
import os
import sys
from io import BytesIO, IOBase
from math import *
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
    return sys.stdin.readline().rstrip('\r\n')

def prod(a, mod=10 ** 9 + 7):
    ans = 1
    for each in a:
        ans = ans * each % mod
    return ans

def gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x

def lcm(a, b):
    return a * b // gcd(a, b)

def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else '0' * (length - len(y)) + y

def check_freq(x):
    freq = {}
    for c in set(x):
        freq[c] = x.count(c)
    return freq

def numToDigit(x):
    box = []
    while x:
        tmp = x % 10
        x = x // 10
        box.append(tmp)
    box.reverse()
    return box

def ii():
    return int(input())

def si():
    return input()

def mi():
    return map(int, input().strip().split(' '))

def li():
    return list(mi())
MAXX = 100000000
''
N = 1000010
(LOGN, TMD, INF, T, n, Sl, Sr, IDl, IDr) = (28, 0, 2147483647, 0, 0, [0] * N, [0] * N, [0] * N, [0] * N)
import sys

def findpre(x):
    L = 0
    R = n + 1
    while L + 1 != R:
        M = (L + R) // 2
        if Sr[M] < x:
            L = M
        else:
            R = M
    return R

def findsuf(x):
    L = 0
    R = n + 1
    while L + 1 != R:
        M = (L + R) // 2
        if Sl[n] - Sl[M - 1] < x:
            R = M
        else:
            L = M
    return L
import sys

def main():
    for _ in range(int(input())):
        n = int(input())
        s = str(input())
        Sl = []
        Sr = []
        IDl = [0]
        IDr = [0]
        for i in range(n - 1, -1, -1):
            if s[i] == '<':
                Sr.append(i)
                IDr.append(IDr[-1] + i)
        ans = []
        for i in range(n):
            if s[i] == '>':
                Sl.append(i)
                IDl.append(IDl[-1] + i)
                if len(Sr) >= len(Sl):
                    ans.append((IDr[-1] - IDr[-len(Sl) - 1] - IDl[-1]) * 2 + i + 1)
                else:
                    ans.append((IDr[-1] - IDl[-2] + IDl[-2 - len(Sr)]) * 2 + n - i)
            else:
                Sr.pop()
                IDr.pop()
                if len(Sr) >= len(Sl):
                    ans.append((IDr[-1] - IDr[-len(Sl) - 1] - IDl[-1]) * 2 + i + 1)
                else:
                    ans.append((IDr[-1] + i - IDl[-1] + IDl[-2 - len(Sr)]) * 2 + n - i)
        print(' '.join(map(str, ans)))
if __name__ == '__main__':
    main()
    sys.stdout.flush()