Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Problem A:
Bit String Reordering

  You have to reorder a given bit string as specified. The only operation allowed is swapping adjacent bit pairs. Please write a program that calculates the minimum number of swaps required.

  The initial bit string is simply represented by a sequence of bits, while the target is specified by a run-length code. The run-length code of a bit string is a sequence of the lengths of maximal consecutive sequences of zeros or ones in the bit string. For example, the run-length code of "011100" is "1 3 2". Note that there are two different bit strings with the same run-length code, one starting with zero and the other starting with one. The target is either of these two.

  In Sample Input 1, bit string "100101" should be reordered so that its run-length code is "1 3 2", which means either "100011" or "011100". At least four swaps are required to obtain "011100". On the other hand, only one swap is required to make "100011". Thus, in this example, 1 is the answer.

Input

The input consists of a single test case. The test case is formatted as follows. 

$N$ $M$

$b_1$ $b_2$ . . . $b_N$

$p_1$ $p_2$ . . . $p_M$

The first line contains two integers $N$ ($1 \leq N \leq 15$) and $M$ ($1 \leq M \leq N$). The second line
specifies the initial bit string by $N$ integers. Each integer $b_i$ is either 0 or 1. The third line contains the run-length code, consisting of $M$ integers. Integers $p_1$ through $p_M$ represent the lengths of consecutive sequences of zeros or ones in the bit string, from left to right. Here, $1 \leq p_j$ for $1 \leq j \leq M$ and $\sum^{M}_{j=1} p_j = N$ hold. It is guaranteed that the initial bit string can be reordered into a bit string with its run-length code $p_1, . . . , p_M$.

Output

Output the minimum number of swaps required

Sample Input 1

6 3
1 0 0 1 0 1
1 3 2

Sample Output 1

1

Sample Input 2

7 2
1 1 1 0 0 0 0
4 3

Sample Output 2

12

Sample Input 3

15 14
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 2

Sample Output 3

7

Sample Input 4

1 1
0
1

Sample Output 4

0



Sample input:
6 3
1 0 0 1 0 1
1 3 2


Sample output:
1

Submission status: Wrong Answer

Solution code:
def read():
  return list(map(int,input().split()))

def calc(bs,ls,first):
  if sum(ls[0::2])!=bs.count(first) or sum(ls[1::2])!=bs.count(1-0):
    return float("inf")
  res=0
  i,j=0,0
  for k in range(0,len(ls),2):
    if k>0: i+=ls[k-1]
    for _ in range(ls[k]):
      j=bs.index(first,j)
      res+=abs(j-i)
      i+=1
      j+=1
  return res

while 1:
  try:
    n,m=read()
    bs=read()
    ls=read()
  except: break
  print(min(calc(bs,ls,i) for i in range(2)))

Submission status: Time Limit Exceeded

Solution code:
(N,M),B,P = [map(int,raw_input().split()) for i in xrange(3)]
C1 = []
for i in xrange(M): C1 += [1]*P[i] if i%2 else [0]*P[i]
C2 = [1-c for c in C1]

ans = 1e10
for C in [C1,C2]:
    if sum(B) == sum(C):
        tmp = 0
        i = j = 0
        while not i == j == N-1:
            if B[i] and C[j]:
                tmp += abs(i-j)
                i += 1; j += 1
            else:
                i += 1-B[i]; j += 1-C[i]
            i = min(N-1,i); j = min(N-1,j)
        ans = min(ans, tmp)
print ans

Submission status: Accepted

Solution code:
def read():
  return list(map(int,input().split()))

def calc(bs,ls,first):
  if sum(ls[0::2])!=bs.count(first) or sum(ls[1::2])!=bs.count(1-first):
    return float("inf")
  res=0
  i,j=0,0
  for k in range(0,len(ls),2):
    if k>0: i+=ls[k-1]
    for _ in range(ls[k]):
      j=bs.index(first,j)
      res+=abs(j-i)
      i+=1
      j+=1
  return res

while 1:
  try:
    n,m=read()
    bs=read()
    ls=read()
  except: break
  print(min(calc(bs,ls,i) for i in range(2)))

Submission status: Accepted

Solution code:
N,M = map(int,raw_input().split())
B = map(int,raw_input().split())
P = map(int,raw_input().split())
C1,C2 = [],[]
for i in xrange(M):
    C1 += [1]*P[i] if i%2 else [0]*P[i]
    C2 += [0]*P[i] if i%2 else [1]*P[i]

ans = 1e10
for C in [C1,C2]:
    if sum(B) == sum(C):
        tmp = 0
        i = j = 0
        while not i == j == N-1:
            if not B[i]: i = min(N-1, i+1)
            if not C[j]: j = min(N-1, j+1)
            if B[i] and C[j]:
                tmp += abs(i-j)
                i = min(N-1, i+1)
                j = min(N-1, j+1)
        ans = min(ans, tmp)
print ans

Submission status: Accepted

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

( n, m ) = map ( int, input ( ).split ( ) )
b = tuple ( map ( int, input ( ).split ( ) ) )
p = list ( map ( int, input ( ).split ( ) ) )

cs = 0
ss = { }
fs = [ ]
bs = [ b ]
while bs:
  ( fs, bs ) = ( bs, fs )
  while fs:
    b = fs.pop ( )
    if b not in ss:
      ss[ b ] = cs
      b = list ( b )
      for i in range ( n - 1 ):
        ( b[ i ], b[ i + 1 ] ) = ( b[ i + 1 ], b[ i ] )
        bs.append ( tuple ( b ) )
        ( b[ i + 1 ], b[ i ] ) = ( b[ i ], b[ i + 1 ] )
  cs = cs + 1

for ( k, v ) in ss.items ( ):
  res = [ ]
  co = 1
  for i in range ( 1, len ( k ) ):
    if k[ i - 1 ] == k[ i ]:
      co = co + 1
    else:
      res.append ( co )
      co = 1
  res.append ( co )
  if res == p and v < cs:
    cs = v

print ( cs )

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
*B, = map(int, input().split())
*P, = map(int, input().split())
def solve(v):
    C = B[:]
    D = []
    for i in range(M):
        D += [(i & 1) ^ v]*P[i]
    res = 0
    for i in range(N):
        if C[i] != D[i]:
            for j in range(i, N):
                if D[i] == C[j]:
                    C[i], C[j] = C[j], C[i]
                    res += j - i
                    break
            else:
                return 10**9
    return res
print(min(solve(0), solve(1)))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n,m = LI()
        b = LI()
        p = LI()
        r = inf
        t = []
        for i in range(m):
            t += [i % 2] * p[i]
        if sorted(collections.Counter(t).items()) == sorted(collections.Counter(b).items()):
            tr = 0
            pi = 0
            for i in range(n):
                if t[i] != 1:
                    continue
                while b[pi] != 1:
                    pi += 1
                tr += abs(i-pi)
                pi += 1
            r = tr

        t = []
        for i in range(m):
            t += [(i+1) % 2] * p[i]
        if sorted(collections.Counter(t).items()) == sorted(collections.Counter(b).items()):
            tr = 0
            pi = 0
            for i in range(n):
                if t[i] != 1:
                    continue
                while b[pi] != 1:
                    pi += 1
                tr += abs(i-pi)
                pi += 1
            if r > tr:
                r = tr
        rr.append(r)
        break

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
import copy

N,M = [int(i) for i in input().split()]

b = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

def solve(num):
  ret =  0
  c = copy.deepcopy(b)
  c_ = []
  for i in range(M):
    c_ += [(int(i%2 == num))] * p[i]
  #print(c,c_)
  for i in range(N):
    if c[i] != c_[i]:
      for j in range(i,N):
        if c_[i] == c[j]:
          ret += j-i
#          print(j-i)
          c[i],c[j]=c[j],c[i]
          break
      else:
        return 1000
  return ret


print(min(solve(0),solve(1)))