Problem:


Score : 800 points

Problem Statement

You are given a string S consisting of lowercase English letters.
Determine whether we can turn S into a palindrome by repeating the operation of swapping two adjacent characters. If it is possible, find the minimum required number of operations.

Constraints

1 \leq |S| \leq 2 × 10^5

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S

Output

If we cannot turn S into a palindrome, print -1. Otherwise, print the minimum required number of operations.

Sample Input 1

eel

Sample Output 1

1

We can turn S into a palindrome by the following operation:

Swap the 2-nd and 3-rd characters. S is now ele.

Sample Input 2

ataatmma

Sample Output 2

4

We can turn S into a palindrome by the following operation:

Swap the 5-th and 6-th characters. S is now ataamtma.

Swap the 4-th and 5-th characters. S is now atamatma.

Swap the 3-rd and 4-th characters. S is now atmaatma.

Swap the 2-nd and 3-rd characters. S is now amtaatma.

Sample Input 3

snuke

Sample Output 3

-1

We cannot turn S into a palindrome.



Sample input:
eel


Sample output:
1

Submission status: Accepted

Solution code:
from collections import deque
import copy
class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node
 
    def add(self, index, add_val):
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index
 
    def sum(self, index):
        res = 0
        while index > 0:
            res += self.bit[index]
            index -= index & -index
        return res
 
s = input()
n = len(s)
a = [ord(i) - ord("a") for i in s]
x = [0]*26
for i in a:
  x[i] += 1
flag = 1
ki = -1
for i in x:
  if i%2 == 1:
    if flag:
      flag = 0
    else:
      print(-1)
      exit()
c = []
x2 = [0]*26
for i in a:
  x2[i] += 1
  if x[i]//2 >= x2[i]:
    c.append(i)
for i in range(26):
  if x[i]%2 == 1:
    b = copy.deepcopy(c)
    c.append(i)
    b = b[::-1]
    c.extend(b)
    break
else:
  b = copy.deepcopy(c)
  b = b[::-1]
  c.extend(b) 
d = {}
for i in range(26):
  d[i] = deque([])
for i in range(n):
  d[c[i]].append(i+1)
for i in range(n):
  x = d[a[i]].popleft()
  a[i] = x
b = []
for i in range(n):
  b.append([a[i],i+1])
b.sort()
b = b[::-1]
bit = BIT(n)
ans = 0
for i,j in b:
  bit.add(j,1)
  ans += bit.sum(j-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        return self.search(j)-self.search(i-1)
#from collections import defaultdict
S=input()
N = len(S)
L = 26
a = ord('a')
d = [[] for i in range(L)]
for i in range(N):
    s=ord(S[i])-a
    d[s].append(i)
flag=0
for i in range(L):
    if len(d[i])%2==1:
        flag+=1
if flag>1:
    print(-1)
    sys.exit()
Suc=[-1]*N
pairs=[]
for i in range(L):
    T=len(d[i])
    for s in range((T//2)):
        li,ri=d[i][s],d[i][-s-1]
        pairs.append((li,ri))
    if T%2==1:
        Suc[d[i][T//2]]=(N//2)+1
pairs.sort()
for i, (li,ri) in enumerate(pairs):
    Suc[li]=i+1
    Suc[ri]=N-i
Tree=BIT(N+3)
ans=0
for i,m in enumerate(Suc):
    ans+=i-Tree.search(m)
    Tree.add(m,1)
#ans+=Tree.search(N+1)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq,string

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7


def solve(f):
    s = f.read_str()
    n = len(s)
    d = [collections.deque() for _ in xrange(26)]
    p = [-1] * n

    for i, si in enumerate(s):
        d[ord(si)-ord('a')].append(i+1)

    odd = None
    for i in xrange(26):
        if len(d[i])%2 == 1:
            if odd is not None: return -1
            odd = i

    if odd is not None: p[n/2] = d[odd][len(d[odd])/2]

    for i in xrange(1,n/2+1):
        mi = float('inf')
        si = None
        for j in xrange(26):
            if len(d[j]) < 2: continue
            if d[j][0] < mi:
                mi = d[j][0]
                si = j

        p[i-1] = d[si].popleft()
        p[n-i] = d[si].pop()

    return count_inversion(p)


class BinaryIndexedTree(object):
    """Binary Indexed Tree (1-indexed)"""
    def __init__(self, size, default=0):
        self.bit = [default for _ in xrange(size + 1)]
        self.size = size

    def sum(self, i):
        """sum 1 to i"""
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """add x to bit[i]"""
        while i <= self.size:
            self.bit[i] += x
            i += i & -i


def count_inversion(a):
    n = len(a)
    ans = 0
    bit = BinaryIndexedTree(n)
    for i in xrange(n):
        ans += i - bit.sum(a[i])
        bit.add(a[i], 1)
    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

Solution code:
*S, = map(ord, input())
N = len(S)
L = 26
ca = ord('a')
d = [[] for i in range(L)]
for i, c in enumerate(S):
    d[c-ca].append(i)

odd = 0
for v in d:
    if len(v) % 2:
        odd += 1
if not odd <= N%2:
    print(-1)
    exit(0)

data = [0]*(N+1)
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s

M = [None]*N
for v in d:
    vl = len(v)
    for i in range(vl):
        if not i <= vl-1-i:
            break
        p = v[i]; q = v[-i-1]
        M[p] = q
        M[q] = p
cnt = 0
B = [0]*N
for i in range(N-1, -1, -1):
    if M[i] <= i:
        B[i] = B[M[i]] = cnt
        cnt += 1

cur = -1
ans = 0
for i in range(N-1, -1, -1):
    if cur < B[i]:
        cur = B[i]
        if M[i] == i:
            ans += N//2 - cur
        else:
            ans += M[i] - get(M[i]+1)
        add(M[i]+1, 1)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
s = input()
N = len(s)
sc = Counter(s)
odds = [1 for x in sc if sc[x] % 2 == 1]
if len(odds) > 1:
    print(-1)
    sys.exit(0)

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size+1)
    def add(self, index, elem):
        index += 1
        while index < len(self.bit):
            self.bit[index] += elem
            index += index & -index
    def get(self, index):
        index += 1
        ret = 0
        while 0 < index:
            ret += self.bit[index]
            index -= index & -index
        return ret

indices = [-1] * N
tb = {c: [None] * (sc[c]//2) for c in sc}
lens = {c: 0 for c in sc}
p = 0
for i in range(N):
    c = s[i]
    l = lens[c]
    if 2 * (l+1) <= sc[c]:
        indices[p] = i
        tb[c][l] = p
        lens[c] += 1
        p += 1
    elif 2 * (l+1) == sc[c] + 1:
        indices[N//2] = i
        lens[c] += 1
    else:
        indices[N-1-tb[c][sc[c]-l-1]] = i
        lens[c] += 1

ans = 0
bit = BIT(N)
for i in indices:
    bit.add(i, 1)
    ans += bit.get(N-1) - bit.get(i)
print(ans)

Submission status: Accepted

Solution code:
from string import ascii_lowercase


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def solve(s):
    indices = {c: [] for c in ascii_lowercase}
    for i, c in enumerate(s):
        indices[c].append(i)

    n = len(s)
    center = n // 2
    bubbles = [-1] * n
    odd_flag = False
    pairs = []
    for c, ids in indices.items():
        cnt = len(ids)
        if cnt & 1:
            if odd_flag:
                return -1
            odd_flag = True
            bubbles[ids[cnt // 2]] = center + 1
        for i in range(cnt // 2):
            li, ri = ids[i], ids[-i - 1]
            pairs.append((li, ri))
    pairs.sort()
    for i, (li, ri) in enumerate(pairs):
        bubbles[li] = i + 1
        bubbles[ri] = n - i

    ans = 0
    bit = Bit(n)
    for i, m in enumerate(bubbles):
        ans += i - bit.sum(m)
        bit.add(m, 1)
    return ans


print(solve(input()))

Submission status: Accepted

Solution code:
from string import ascii_lowercase


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def solve(s):
    indices = {c: [] for c in ascii_lowercase}
    for i, c in enumerate(s):
        indices[c].append(i)

    n = len(s)
    center = n // 2
    bubbles = [-1] * n
    odd_flag = False
    lefts, rights = [], []
    for c, ids in indices.items():
        cnt = len(ids)
        if cnt & 1:
            if odd_flag:
                return -1
            odd_flag = True
            bubbles[ids[cnt // 2]] = center + 1
        for i in range(cnt // 2):
            li, ri = ids[i], ids[-i - 1]
            if li < center:
                lefts.append((li, ri))
            else:
                rights.append((li, ri))
    lefts.sort()
    rights.sort()
    r_itr = iter(rights)
    for i, (li, ri) in enumerate(lefts):
        bubbles[li] = i + 1
        bubbles[ri] = n - i
    for i in range(len(lefts), center):
        li, ri = next(r_itr)
        bubbles[li] = i + 1
        bubbles[ri] = n - i

    ans = 0
    bit = Bit(n)
    for i, m in enumerate(bubbles):
        ans += i - bit.sum(m)
        bit.add(m, 1)
    return ans


print(solve(input()))

Submission status: Accepted

Solution code:
from string import ascii_lowercase


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def solve(s):
    indices = {c: [] for c in ascii_lowercase}
    for i, c in enumerate(s):
        indices[c].append(i)

    n = len(s)
    center = n // 2
    bubbles = [-1] * n
    odd_flag = False
    lefts, rights = [], []
    used = [False] * n
    for c, ids in indices.items():
        cnt = len(ids)
        if cnt & 1:
            if odd_flag:
                return -1
            odd_flag = True
            bubbles[ids[cnt // 2]] = center + 1
            used[center] = True
        for i in range(cnt // 2):
            li, ri = ids[i], ids[-i - 1]
            if li < center:
                lefts.append((li, ri))
                used[n - li - 1] = True
            else:
                rights.append((li, ri))
    lefts.sort()
    rights.sort()
    r_itr = iter(rights)
    # print(lefts)
    # print(rights)
    for i, (li, ri) in enumerate(lefts):
        bubbles[li] = i + 1
        bubbles[ri] = n - i
    for i in range(len(lefts), center):
        li, ri = next(r_itr)
        bubbles[li] = i + 1
        bubbles[ri] = n - i
    # print(bubbles)

    ans = 0
    bit = Bit(n)
    for i, m in enumerate(bubbles):
        ans += i - bit.sum(m)
        bit.add(m, 1)
    return ans


print(solve(input()))

Submission status: Accepted

Solution code:
def count_inversions(L):
  def helper(A,B):
    lA,lB = len(A),len(B)
    if lA == 0:
      return B,0
    elif lB == 0:
      return A,0
    
    A,c1 = helper(A[:lA//2],A[lA//2:])
    B,c2 = helper(B[:lB//2],B[lB//2:])
    cnt = c1+c2
    i = 0
    j = 0

    C = [None]*(lA+lB)
    while i < lA and j < lB:
      if A[i] > B[j]:
        cnt += lA-i
        C[i+j] = B[j]
        j += 1
      else:
        C[i+j] = A[i]
        i += 1

    if i < lA:
      C[i+j:] = A[i:]
    else:
      C[i+j:] = B[j:]

    return C,cnt

  return helper(L[:len(L)//2],L[len(L)//2:])[1]

from collections import deque

ALPHABETS = 26

indices = [deque() for _ in range(26)]
S = list(map(lambda c: ord(c)-ord('a'),input()))
for i,c in enumerate(S):
  indices[c] += [i]

odd = None
for c,l in enumerate(indices):
  if len(l)%2 == 1:
    if odd is None:
      odd = c
    else:
      odd = -1
      break

if odd == -1:
  print(-1)
  exit()

target = [None]*len(S)
assigned = [False]*len(S)
if odd is not None:
  l = list(indices[odd])
  i = l[len(l)//2]
  target[len(target)//2] = i
  assigned[i] = True
  l = deque(l[:len(l)//2] + l[len(l)//2+1:])

j = 0
for i in range(len(S)//2):
  while assigned[j]:
    j += 1

  l = indices[S[j]]
  a = l.popleft()
  b = l.pop()
  assert a == j
  target[i] = a
  target[len(S)-i-1] = b
  assigned[a] = True
  assigned[b] = True
  
print(count_inversions(target))

Submission status: Runtime Error

Solution code:
def main():
    X, Y = [int(i) for i in input().split()]
    
    ans = 1
    pre = X

    while True:
        pre *= 2
        if pre <= Y:
            ans += 1
        else:
            break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
S = input()

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def update(self, i, v):
        while i <= self.n:
            self.bit[i] += v
            i += i & -i
            
    def query(self, i):
        ret = 0
        while i > 0:
            ret += self.bit[i]
            i -= i & -i
            
        return ret

d = defaultdict(list)
for i, v in enumerate(S):
    d[v].append(i + 1)

if sum(len(l) % 2 != 0 for l in d.values()) > 1:
    print(-1)
    exit()

N = len(S)
ctr = []
key_map = [-1] * (N + 1)

for k, v in d.items():
    t = len(v)
    if t % 2  == 1:
        key_map[v[t % 2]] = N // 2 + 1

    for j in range(t // 2):
        ctr.append((v[j], v[-j - 1]))
        
ctr.sort()

for i, (l, r) in enumerate(ctr):
    key_map[l] = i + 1
    key_map[r] = N - i

tree = BIT(N)
ans = 0
for i, v in enumerate(key_map[1:]):
    ans += i - tree.query(v)
    tree.update(v, 1)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict
S = input()

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def update(self, i, v):
        while i <= self.n:
            self.bit[i] += v
            i += i & -i
            
    def query(self, i):
        ret = 0
        while i > 0:
            ret += self.bit[i]
            i -= i & -i
            
        return ret

ctr = Counter(S)
if sum(c % 2 != 0 for c in ctr.values()) > 1:
    print(-1)
    
ctr = {k: v / 2 for k, v in ctr.items()}
A = []
C = []
ans = 0
MAX_LEN = len(S)
for i, v in enumerate(S):
    if ctr[v] >= 1:
        A.append(v)
        ctr[v] -= 1
        ans += max(0, i + 1 - MAX_LEN // 2)
    elif ctr[v] > 0:
        ans += abs(i - MAX_LEN // 2)
    else:
        C.append(v)

d = defaultdict(list)
for i, v in enumerate(C[::-1]):
    d[v].append(i + 1)
    
tree = BIT(len(A))
for i, a in enumerate(A):
    ans += i - tree.query(d[a][0])
    tree.update(d[a][0], 1)
    d[a] = d[a][1:]

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * n

    def sum(self, i):
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1)) - 1
        return s

    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i |= i + 1

a = ord('a')

def make_index(s):

    index = [[] for _ in range(26)]
    for i, ch in enumerate(s):
        index[ord(ch) - a].append(i)

    return index

def solve(s):

    n = len(s)
    index = make_index(s)

    odd = None
    for code, char_pos in enumerate(index):
        if len(char_pos) % 2 == 1:
            if odd is not None:
                return -1
            odd = code

    if odd is not None:
        if index[odd][len(index[odd]) // 2] < n // 2:
            s = s.reverse()
            index = make_index(s)

    bit = Bit(n)

    ans = 0
    cnt = 0
    for i in range(n):
        if bit.sum(i + 1) - bit.sum(i) == 1:
            continue
        cnt += 1
        code = ord(s[i]) - a
        j = index[code].pop()
        ans += n - cnt - (j - bit.sum(j))
        bit.add(j, 1)
        if (n - 1) // 2 <= cnt:
            break

    return ans


def main():
    s = input()

    print(solve(s))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * n

    def sum(self, i):
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1)) - 1
        return s

    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i |= i + 1

a = ord('a')

def make_index(s):

    index = [[] for _ in range(26)]
    for i, ch in enumerate(s):
        index[ord(ch) - a].append(i)

    return index

def solve(s):

    n = len(s)
    index = make_index(s)

    odd = None
    for code, char_pos in enumerate(index):
        if len(char_pos) % 2 == 1:
            if odd is not None:
                return -1
            odd = code

    if odd is not None:
        if index[odd][len(index[odd]) // 2] < n // 2:
            s = s.reverse()
            index = make_index(s)

    bit = Bit(n)

    ans = 0
    cnt = 0
    for i in range(n):
        if bit.sum(i + 1) - bit.sum(i) == 1:
            continue
        cnt += 1
        code = ord(s[i]) - a
        j = index[code].pop()
        ans += n - cnt - (j - bit.sum(j))
        if (n - 1) // 2 <= cnt:
            break

    return ans


def main():
    s = input()

    print(solve(s))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
import copy
class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node

    def add(self, index, add_val):
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index

    def sum(self, index):
        res = 0
        while index > 0:
            res += self.bit[index]
            index -= index & -index
        return res

s = input()
n = len(s)
a = [ord(i) - ord("a") for i in s]
x = [0]*26
for i in a:
  x[i] += 1
flag = 1
ki = -1
for i in x:
  if i%2 == 1:
    if flag:
      flag = 0
    else:
      print(-1)
      exit()
c = []
x2 = [0]*26
for i in a:
  x2[i] += 1
  if x[i]//2 >= x2[i]:
    c.append(i)
for i in range(n):
  if x[i]%2 == 1:
    b = copy.deepcopy(c)
    c.append(i)
    b = b[::-1]
    c.extend(b)
    break
else:
  b = copy.deepcopy(c)
  b = b[::-1]
  c.extend(b) 
d = {}
for i in range(26):
  d[i] = deque([])
for i in range(n):
  d[c[i]].append(i+1)
for i in range(n):
  x = d[a[i]].popleft()
  a[i] = x
b = []
for i in range(n):
  b.append([a[i],i+1])
b.sort()
b = b[::-1]
bit = BIT(n)
ans = 0
for i,j in b:
  bit.add(j,1)
  ans += bit.sum(j-1)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq,string

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7


def solve(f):
    s = f.read_str()
    n = len(s)
    d = [collections.deque() for _ in xrange(26)]
    p = [-1] * n

    for i, si in enumerate(s):
        d[ord(si)-ord('a')].append(i+1)

    odd = None
    for i in xrange(26):
        if len(d[i])%2 == 1:
            if odd: return -1
            odd = i

    if odd: p[n/2] = d[odd][len(d[odd])/2]

    for i in xrange(1,n/2+1):
        mi = float('inf')
        si = None
        for j in xrange(26):
            if len(d[j]) < 2: continue
            diff = abs(d[j][0]-i) + abs(d[j][-1]-(n-i))
            if diff < mi:
                mi = diff
                si = j

        p[i-1] = d[si].popleft()
        p[n-i] = d[si].pop()

    return count_inversion(p)


class BinaryIndexedTree(object):
    """Binary Indexed Tree (1-indexed)"""
    def __init__(self, size, default=0):
        self.bit = [default for _ in xrange(size + 1)]
        self.size = size

    def sum(self, i):
        """sum 1 to i"""
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """add x to bit[i]"""
        while i <= self.size:
            self.bit[i] += x
            i += i & -i


def count_inversion(a):
    n = len(a)
    ans = 0
    bit = BinaryIndexedTree(n)
    for i in xrange(n):
        ans += i - bit.sum(a[i])
        bit.add(a[i], 1)
    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Runtime Error

Solution code:
from collections import Counter
import sys
s = input()
N = len(s)
sc = Counter(s)
odds = [1 for x in sc if sc[x] % 2 == 1]
if len(odds) > 1:
    print(-1)
    sys.exit(0)

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size+1)
    def add(self, index, elem):
        index += 1
        while index < len(self.bit):
            self.bit[index] += elem
            index += index & -index
    def get(self, index):
        index += 1
        ret = 0
        while 0 < index:
            ret += self.bit[index]
            index -= index & -index
        return ret

indices = [-1] * N
tb = {c: [None] * (sc[c]//2) for c in sc}
lens = {c: 0 for c in sc}
p = 0
for i in range(N):
    c = s[i]
    l = lens[c]
    if 2 * l < sc[c]:
        indices[p] = i
        tb[c][l] = p
        lens[c] += 1
        p += 1
    elif 2 * l == sc[c] + 1:
        indices[N//2] = i
    else:
        indices[N-1-tb[c][sc[c]-l-1]] = i
        lens[c] += 1

ans = 0
bit = BIT(N)
for i in indices:
    bit.add(i, 1)
    ans += bit.get(N-1) - bit.get(i)
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-


N = int(input())
As = list(map(int, input().split()))

sum1 = 0
sum2 = sum(As)

min_diff = float('inf')

for a in As[0:len(As)-1]:
    sum1 += a
    sum2 -= a
    #print(abs(sum1 - sum2))
    min_diff = min(min_diff, abs(sum1 - sum2))
print(min_diff)

Submission status: Runtime Error

Solution code:
from collections import Counter

text = input()
count = Counter()

def change_count(text):
    N = len(text)
    origin = 0
#    print(text)
    if N <= 2:
        return 0
    elif text[0] == text[N-1]:
        return change_count(text[1:N-1])
    else:
        if count[text[0]] % 2 == 1:
            origin = N-1
        start = 1
#        print(origin)

        while text[origin] != text[start]:
            start = start + 1
        end = N-2
        while text[origin] != text[end]:
            end = end - 1

        count[text[origin]] = count[text[origin]]-2
#        print("start:"+ str(start) + " end:"+str(end))
        if origin == 0:
            if start >= end :
                return (N-1)-start + change_count(text[1:start]+text[start+1:])
            else:
                return (N-1)-end + change_count(text[1:end]+text[end+1:])
        else:
            if start < end :
                return start + change_count(text[0:start]+text[start+1:N-1])
            else:
                return end + change_count(text[0:end]+text[end+1:N-1])


for c in text:
    count[c] = count[c] + 1

odd = 0
for k, c in count.items():
    if c % 2 == 1:
        odd = odd + 1

if odd >= 2:
    print(-1)
else:
    print(change_count(text))

"""
init: abbaccb
1. babaccb
2. babcacb
3. bacbacb
4. bcabacb


3回

init: abbabbc

init: abbaccb
1. abbcacb
2. abbccab
3. abbccba
4. abcbcba

6-1-
012345
taatmm
1. taamtm
2. taammt
3. tamamt
4. tmaamt

今端っこにあるのは??

ataatmma


init: bababbc

baabbcb: 4
babbcab: 3
babcbab: 1

bababcb: 1
babbcab: 2




"""

Submission status: Runtime Error

Solution code:
from collections import Counter

text = input()
count = Counter()

def change_count(text):
    N = len(text)
    origin = 0
    if N <= 2:
        return 0
    elif text[0] == text[N-1]:
        return change_count(text[1:N-1])
    else:
        if count[0] % 2 == 1:
            origin = N-1
        start = 1
        while text[origin] != text[start]:
            start = start + 1
        end = N-2
        while text[origin] != text[end]:
            end = end - 1

        if origin == 0:
            if start >= end :
                return (N-1)-start + change_count(text[1:start]+text[start+1:])
            else:
                return (N-1)-end + change_count(text[1:end]+text[end+1:])
        else:
            if start < end :
                return start + change_count(text[0:start]+text[start+1:N-1])
            else:
                return end + change_count(text[0:end]+text[end+1:N-1])


for c in text:
    count[c] = count[c] + 1

odd = 0
for k, c in count.items():
    if c % 2 == 1:
        odd = odd + 1

if odd >= 2:
    print(-1)
else:
    print(change_count(text))

Submission status: Runtime Error

Solution code:
S=input()
S_lst=list(S)
counter=Counter(S_lst)

margin=len(S)%2
for k, v in counter.items():
    if v%2==1:
        margin -= 1
if not(margin == 0):
    print(-1)
    exit()
    
num_lst=[] # number notation of S
num_ddct=defaultdict(lambda: []) # remember number for palindrome
first_dct={}
thres_dct={}
for k,_ in counter.items():
    first_dct[k]=True
    thres_dct[k]=math.floor(counter[k]/2)

pos=0
for s in S_lst:
    if first_dct[s]: # so far first part
        if len(num_ddct[s]) < thres_dct[s]: # still in first part
            num_lst.append(pos)
            num_ddct[s].append(pos)
            pos += 1
        else: # first time to reach reverse part
            first_dct[s]=False # its not first anymore
            if counter[s]%2==0:  # usual case
                num_lst.append(len(S_lst) - num_ddct[s][-1] - 1)
                num_ddct[s].pop()
            else: # if center
                num_lst.append( int((len(S_lst) - 1) / 2 ) )
    else: # already in second part
        num_lst.append(len(S_lst) - num_ddct[s][-1] - 1)
        num_ddct[s].pop()
print(-1)

Submission status: Runtime Error

Solution code:
import string
def main():
    l = list(input())
    N = len(l)
    count=0
    flag = True
    middle_letter = None
    i = 0
    dic = {i:l.count(i) for i in string.ascii_lowercase}
    while i <= N>>1:
        if l[i]!=l[N-i-1]:
            if dic[l[i]]%2 and N%2:
                if flag:
                    middle_letter = l[i]
                    tar_index = N>>1
                    f_index = i
                    count+=tar_index-f_index
                    l[f_index:tar_index] = l[f_index+1:tar_index+1]
                    l[tar_index] = middle_letter
                    flag = False
                elif not flag and l[i]==middle_letter:
                    pos = list(reversed(l)).index(l[i], i, N - i)
                    temp = l[i]
                    tar_index = N - 1 - i
                    f_index = N - pos - 1
                    count += tar_index - f_index
                    l[f_index:tar_index] = l[f_index + 1:tar_index + 1]
                    l[tar_index] = temp
                    i += 1
                else:
                    print(-1)
                    exit()
            else:
                pos = list(reversed(l)).index(l[i],i,N-i)
                temp = l[i]
                tar_index = N-1-i
                f_index = N-pos-1
                count += tar_index-f_index
                l[f_index:tar_index] = l[f_index+1:tar_index+1]
                l[tar_index] = temp
                i+=1
        else:
            i+=1
    print(count)


if __name__=="__main__":
    main()