Determine whether you can reach bitstring B from bitstring A using specific operations

Question

The question is, given two bitstrings A and B, determine whether you can reach B from A using the following operation:

Choose two indices i,j such that the values at both indices are the same, and the number of 1's and 0's in between i and j are greater than the number of 1's and 0's outside the interval, respectively. Then, flip the bit at both indices.

An example of an operation: 0001010001

0001010001 number of zeroes between: 3 > num zeroes outside = 2

number of ones between: 2 > num ones outside = 1

thus, 0101010101 is a valid change.

I tried iterating right to left by keeping track of the number of ones and zeroes on each side, and if the number of ones and zeroes on the right side is less than the left side, I performed an operation to try and shift all the 1's to the right side (I was trying to transform each bitstring into its lexicographically minimum reduced version, then compare to see whether they are the same) but this fails hidden test cases. (or I implemented it incorrectly, I'm not sure if the algorithm idea is correct).

Not posting the code because it's irrelevant. I just want algorithm help, not coding help.

It's a private codeforces gym problem so I can't send the link.

Answer 1

Recently I stumbled across this post again. I think I did not understand the problem correctly the first time, because I thought that only players wo want to switch teams are allowed to actually switch.

If you are still interested please check if this code passes the tests.

def main():
    t = int(input())
    for _ in range(t):
        read_input_and_solve()


def read_input_and_solve():
    n = int(input())
    p = input()
    q = input()

    if solve(n, p, q): 
        print('yes')
    else:
        print('no')


def solve(n, p, q):
    try:       
        check_middle(n, p, q)
        r = find_index_right_min(n, p, q)
        l = find_index_left_max(n, p, q)
        
        if r:
            validate_switchable_1_j(p, r)
        if l:
            validate_switchable_i_n(p, l)

        check_balance(n, p, q)
        return True
    except NotSolvableException as e:
        return False


def check_balance(n, p, q):
    balanced = \
    sum(1 for i in range(0, n//2-1) if p[i-1] == 1 and q[i] == 0)  \
    - sum(1 for i in range(0, n//2-1) if p[i] == 0 and q[i] == 1) \
    == \
    sum(1 for i in range(n//2+1, n) if p[i] == 1 and q[i] == 0)  \
    - sum(1 for i in range(n//2+1, n) if p[i] == 0 and q[i] == 1)

    if not balanced:
        raise NotSolvableException('not balanced')  
  

def check_middle(n, p, q):
    middle_indices = [n//2-1, n//2]
    if any(map(lambda i: p[i] != q[i], middle_indices)):
        raise NotSolvableException(f'indices {n//2}, {n//2 + 1} cannot switch')  
        

def find_index_right_min(n, p, q):
    for j in range(n//2-1, n):
        if p[j] != q[j]:
            return j
    else: return None
        

def find_index_left_max(n, p, q):
    for i in range(n//2-2, -1, -1):
        if p[i] != q[i]:
            return i
    else: return None


def validate_switchable_i_n(p, i):
    n = len(p)

    inner_vote_A = sum(1 for k in range(i+1, n) if p[k] == 'A')
    outer_vote_A = sum(1 for k in range(i) if p[k] == 'A')

    if p[i] == 'A' and p[n-1] == 'B':
        outer_vote_A += 1
    if p[i] == 'B' and p[n-1] == 'A':
        outer_vote_A -= 1        

    if inner_vote_A <= outer_vote_A:
        raise NotSolvableException('transfer rejected')  

    inner_vote_B = sum(1 for k in range(i+1, n) if p[k] == 'B')
    outer_vote_B = sum(1 for k in range(i) if p[k] == 'B')

    if p[i] == 'A' and p[n-1] == 'B':
        outer_vote_B -= 1
    if p[i] == 'B' and p[n-1] == 'A':
        outer_vote_B += 1   

    if inner_vote_B <= outer_vote_B:
        raise NotSolvableException('transfer rejected') 
    
    
def validate_switchable_1_j(p, j):
    n = len(p)
    inner_vote_A = sum(1 for k in range(1, j) if p[k] == 'A')
    outer_vote_A = sum(1 for k in range(j+1, n) if p[k] == 'A')

    if p[j] == 'A' and p[0] == 'B':
        outer_vote_A += 1
    if p[j] == 'B' and p[0] == 'A':
        outer_vote_A -= 1        

    if inner_vote_A <= outer_vote_A:
        raise NotSolvableException('transfer rejected')  

    inner_vote_B = sum(1 for k in range(1, j) if p[k] == 'B')
    outer_vote_B = sum(1 for k in range(j+1, n) if p[k] == 'B')

    if p[j] == 'A' and p[0] == 'B':
        outer_vote_B -= 1
    if p[j] == 'B' and p[0] == 'A':
        outer_vote_B += 1   

    if inner_vote_B <= outer_vote_B:
        raise NotSolvableException('transfer rejected')     


def get_votes(prefix_sum_team, i, j):
    votes_no = prefix_sum_team[-1] - prefix_sum_team[j] 
    if i-1 >= 0:
        votes_no += prefix_sum_team[i-1]
    votes_yes = prefix_sum_team[j-1] - prefix_sum_team[i]
    return votes_yes, votes_no


class NotSolvableException(RuntimeError):
    pass


if __name__ == '__main__': main()