Problem:
 Score : 600 points    Problem Statement There are 2N balls, N white and N black, arranged in a row. The integers from 1 through N are written on the white balls, one on each ball, and they are also written on the black balls, one on each ball.
The integer written on the i -th ball from the left ( 1  ≤  i  ≤  2N ) is a_i , and the color of this ball is represented by a letter c_i . c_i  =  W represents the ball is white; c_i  =  B represents the ball is black.  Takahashi the human wants to achieve the following objective:   For every pair of integers (i,j) such that 1  ≤  i  <  j  ≤  N , the white ball with i written on it is to the left of the white ball with j written on it.  For every pair of integers (i,j) such that 1  ≤  i  <  j  ≤  N , the black ball with i written on it is to the left of the black ball with j written on it.   In order to achieve this, he can perform the following operation:   Swap two adjacent balls.   Find the minimum number of operations required to achieve the objective.      Constraints  1  ≤  N  ≤  2000  1  ≤  a_i  ≤  N  c_i  =  W or c_i  =  B .  If i  ≠  j , (a_i,c_i)  ≠  (a_j,c_j) .         Input Input is given from Standard Input in the following format:  N  c_1  a_1  c_2  a_2  :  c_{2N}  a_{2N}       Output Print the minimum number of operations required to achieve the objective.        Sample Input 1 3
B 1
W 2
B 3
W 1
W 3
B 2      Sample Output 1 4  The objective can be achieved in four operations, for example, as follows:   Swap the black 3 and white 1 .  Swap the white 1 and white 2 .  Swap the black 3 and white 3 .  Swap the black 3 and black 2 .        Sample Input 2 4
B 4
W 4
B 3
W 3
B 2
W 2
B 1
W 1      Sample Output 2 18       Sample Input 3 9
W 3
B 1
B 4
W 1
B 5
W 9
W 2
B 6
W 5
B 3
W 8
B 9
W 7
B 2
B 8
W 4
W 6
B 7      Sample Output 3 41

Solution (Python):
N = int(input())
L = []
C = []
A = []
b = w = 0
b_d = {}
w_d = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    n = 0
    for cc, aa in zip(C, A):
        if cc == c and aa > a:
            n += 1
    L.append([0] * (N + 1))
    cnt = 0
    for j in range(N, -1, -1):
        L[-1][j] = cnt+n
        if j in (b_d if c=="W" else w_d):
            cnt+=1

    if c=="B":
        b_d[a] = i
        b+=1
    else:
        w_d[a] = i
        w+=1
    C.append(c)
    A.append(a)


dp = [[0]*(N+2) for i in range(N+2)]
for i in range(N+1):
    for j in range(N+1):
        if i==j==0:
            continue
        if i==0:
            dp[i][j] = dp[i][j-1] + L[b_d[j]][i]
        elif j==0:
            dp[i][j] = dp[i-1][j] + L[w_d[i]][j]
        else:
            dp[i][j] = min(dp[i-1][j] + L[w_d[i]][j],
                           dp[i][j-1] + L[b_d[j]][i])
print(dp[-2][-2])

Solution (Python):
from itertools import accumulate


def solve(n, rev):
    def existence_right(rev_c):
        n2 = n * 2
        acc = [[0] * n2]
        row = [0] * n2
        for x in rev_c:
            row[n2 - x - 1] += 1
            acc.append(list(reversed(list(accumulate(row)))))
        return acc

    
    
    cost_w, cost_b = list(map(existence_right, rev))

    dp = [0] + list(accumulate(c[y] for y, c in zip(rev[1], cost_b)))
    for w, x in enumerate(rev[0]):
        ndp = [0] * (n + 1)
        cwx = cost_w[w][x]
        ndp[0] = prev = dp[0] + cwx
        for b, y in enumerate(rev[1]):
            ndp[b + 1] = prev = min(dp[b + 1] + cwx + cost_b[b + 1][x],
                                    prev + cost_w[w + 1][y] + cost_b[b][y])
        dp = ndp
    return dp[n]


n = int(input())

rev = [[0] * n, [0] * n]
for i in range(n * 2):
    c, a = input().split()
    a = int(a) - 1
    rev[int(c == 'B')][a] = i
print(solve(n, rev))

Solution (Python):
from itertools import accumulate


def solve(n, rev):
    def existence_right(rev_c):
        n2 = n * 2
        acc = [[0] * n2]
        row = [0] * n2
        for x in rev_c:
            row[n2 - x - 1] += 1
            acc.append(list(reversed(list(accumulate(row)))))
        return acc

    
    
    cost = list(map(existence_right, rev))

    dp = [0] + list(accumulate(c[y] for y, c in zip(rev[1], cost[1])))
    for x, cw0, cw1 in zip(rev[0], cost[0], cost[0][1:]):
        ndp = [0] * (n + 1)
        cw0x = cw0[x]
        ndp[0] = prev = dp[0] + cw0x
        for b, (y, cb0, cb1) in enumerate(zip(rev[1], cost[1], cost[1][1:])):
            ndp[b + 1] = prev = min(dp[b + 1] + cw0x + cb1[x], prev + cw1[y] + cb0[y])
        dp = ndp
    return dp[n]


n = int(input())

rev = [[0] * n, [0] * n]
for i in range(n * 2):
    c, a = input().split()
    a = int(a) - 1
    rev[int(c == 'B')][a] = i
print(solve(n, rev))

Solution (Python):
from itertools import accumulate


def solve(n, rev):
    def existence_right(rev_c):
        n2 = n * 2
        acc = [[0] * n2]
        row = [0] * n2
        for x in rev_c:
            row[n2 - x - 1] += 1
            acc.append(list(reversed(list(accumulate(row)))))
        return acc

    
    
    cost = list(map(existence_right, rev))

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for w, x in enumerate(rev[0]):
        dp[w + 1][0] = dp[w][0] + cost[0][w][x]
    for b, y in enumerate(rev[1]):
        dp[0][b + 1] = dp[0][b] + cost[1][b][y]
    for w, x in enumerate(rev[0]):
        dpw0, dpw1 = dp[w], dp[w + 1]
        cost_wx, cost_w1 = cost[0][w][x], cost[0][w + 1]
        for b, y in enumerate(rev[1]):
            dpw1[b + 1] = min(dpw0[b + 1] + cost_wx + cost[1][b + 1][x],
                              dpw1[b] + cost_w1[y] + cost[1][b][y])
    return dp[n][n]


n = int(input())

rev = [[0] * n, [0] * n]
for i in range(n * 2):
    c, a = input().split()
    a = int(a) - 1
    rev[int(c == 'B')][a] = i
print(solve(n, rev))

Solution (Python):
from itertools import accumulate

N = int(input())
balls = []


placeB = [0] * N
placeW = [0] * N


for i in range(2*N):
    c, a = input().split()
    a = int(a)
    balls.append([c, a])
    if c == "B":
        placeB[a-1] = i
    else:
        placeW[a-1] = i


costB = [[0]*(2*N+1) for i in range(N+1)]  
costW = [[0]*(2*N+1) for i in range(N+1)]  

for i in range(N):
    for j in range(2*N):
        if balls[j][1] > i:
            if balls[j][0] == "B":
                costB[i][j+1] = 1
            else:
                costW[i][j+1] = 1


costB = [list(accumulate(cB)) for cB in costB]
costW = [list(accumulate(cW)) for cW in costW]


dp = [[float('inf')]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for b in range(N+1):
    for w in range(N+1):
        if b > 0:
            dp[b][w] = min(dp[b][w], dp[b-1][w] + costB[b][placeB[b-1]] + costW[w][placeB[b-1]])
        if w > 0:
            dp[b][w] = min(dp[b][w], dp[b][w-1] + costW[w][placeW[w-1]] + costB[b][placeW[w-1]])

print(dp[N][N])

Solution (Python):
from itertools import accumulate

N = int(input())
balls = []


placeB = [0] * N
placeW = [0] * N


for i in range(2*N):
    c, a = input().split()
    a = int(a)
    balls.append([c, a])
    if c == "B":
        placeB[a-1] = i
    else:
        placeW[a-1] = i


costB = [[0]*(2*N+1) for i in range(N+1)]  
costW = [[0]*(2*N+1) for i in range(N+1)]  

for i in range(N):
    for j in range(2*N):
        if balls[j][1] > i:
            if balls[j][0] == "B":
                costB[i][j+1] = 1
            else:
                costW[i][j+1] = 1


costB = [list(accumulate(cB)) for cB in costB]
costW = [list(accumulate(cW)) for cW in costW]


dp = [[float('inf')]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for b in range(N+1):
    for w in range(N+1):
        if b > 0:
            dp[b][w] = min(dp[b][w], dp[b-1][w] + costB[b][placeB[b-1]] + costW[w][placeB[b-1]])
        if w > 0:
            dp[b][w] = min(dp[b][w], dp[b][w-1] + costW[w][placeW[w-1]] + costB[b][placeW[w-1]])

print(dp[N][N])

Solution (Python):
N = int(input())
balls = []
for i in range(2 * N):
    c, a = input().split()
    balls += [(c, int(a))]


numB = [[0] * (N + 1) for i in range(2 * N)]
numW = [[0] * (N + 1) for i in range(2 * N)]
for i in reversed(range(1, 2 * N)):
    c, a = balls[i]
    numB[i - 1] = list(numB[i])
    numW[i - 1] = list(numW[i])
    if c == 'B':
        for b in range(a, N + 1):
            numB[i - 1][b] += 1
    else:
        for w in range(a, N + 1):
            numW[i - 1][w] += 1


costB = [[0] * (N + 1) for i in range(N + 1)]
costW = [[0] * (N + 1) for i in range(N + 1)]
for i in reversed(range(2 * N)):
    c, a = balls[i]
    if c == 'B':
        cost = numB[i][a - 1]
        for w in range(N + 1):
            costB[a - 1][w] = cost + numW[i][w]
    else:
        cost = numW[i][a - 1]
        for b in range(N + 1):
            costW[b][a - 1] = cost + numB[i][b]

dp = [[float('inf')] * (N + 1) for i in range(N + 1)]
dp[0][0] = 0
for b in range(N + 1):
    for w in range(N + 1):
        if b > 0:
            dp[b][w] = min(dp[b][w], dp[b - 1][w] + costB[b - 1][w])
        if w > 0:
            dp[b][w] = min(dp[b][w], dp[b][w - 1] + costW[b][w - 1])

print(dp[N][N])

Solution (Python):
N = int(input())
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    c = "BW".index(c); a = int(a)
    if c:
        MW[a-1] = i
    else:
        MB[a-1] = i

P = [[0]*(N+1) for i in range(N+1)]
Q = [[0]*(N+1) for i in range(N+1)]

for p in range(N):
    cnt = MW[p] - sum(MW[p0] < MW[p] for p0 in range(p))

    P[p][0] = cnt
    for q in range(N):
        if MB[q] < MW[p]:
            cnt -= 1
        P[p][q+1] = cnt

for q in range(N):
    cnt = MB[q] - sum(MB[q0] < MB[q] for q0 in range(q))

    Q[q][0] = cnt
    for p in range(N):
        if MW[p] < MB[q]:
            cnt -= 1
        Q[q][p+1] = cnt

dp = [[10**9]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    dp[i+1][0] = dp[i][0] + P[i][0]
for i in range(N):
    dp[0][i+1] = dp[0][i] + Q[i][0]
for i in range(N):
    for j in range(N):
        dp[i+1][j+1] = min(dp[i][j+1] + P[i][j+1], dp[i+1][j] + Q[j][i+1])
print(dp[N][N])

Solution (Python):
from bisect import bisect
N = int(input())
B = []
BW = []; BB = []
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    c = "BW".index(c)
    B.append((c, a))
    if c:
        MW[a-1] = i
    else:
        MB[a-1] = i

P = [[0]*(N+1) for i in range(N+1)]
Q = [[0]*(N+1) for i in range(N+1)]

for p in range(N):
    cnt = MW[p] - sum(MW[p0] < MW[p] for p0 in range(p))

    P[p][0] = cnt
    for q in range(N):
        if MB[q] < MW[p]:
            cnt -= 1
        P[p][q+1] = cnt

for q in range(N):
    cnt = MB[q] - sum(MB[q0] < MB[q] for q0 in range(q))

    Q[q][0] = cnt
    for p in range(N):
        if MW[p] < MB[q]:
            cnt -= 1
        Q[q][p+1] = cnt

dist = [[10**9]*(N+1) for i in range(N+1)]
dist[0][0] = 0
que = [(0, 0, 0)]
for i in range(N):
    dist[i+1][0] = dist[i][0] + P[i][0]
for i in range(N):
    dist[0][i+1] = dist[0][i] + Q[i][0]
for i in range(N):
    for j in range(N):
        dist[i+1][j+1] = min(dist[i][j+1] + P[i][j+1], dist[i+1][j] + Q[j][i+1])
print(dist[N][N])