Bracelet Crossings

USACO 2021 December Contest, Gold - Problem 3

Algorithm

Conditions to check:

The stack is valid (parenthesis matching problem)
Each color is in a contiguous interval
Ordering of colors is constant (if a appears before b in one x, it appears before b in all x)
If a is contained within b in one x, it is contained within b in all x

Python

def solve(n, case):
    active = [0]*(n+1)
    # 0 => not seen, 1 => seen, 2 ==> previously seen
    orders = []
    contain = [-1]*(n+1)
    for sweep in case:
        stack = []
        seen = [0]*(n+1)
        curr_order = []
        for color in sweep:
            if seen[color]:
                if stack[-1] == color:
                    stack.pop()
                else:
                    #print("stack fail")
                    return False # Invalid stack
            else:
                if contain[color] != -1:
                    if contain[color] == 0:
                        if len(stack) != 0:
                            #print("contain fail")
                            return False # Invalid containment
                    elif len(stack) == 0 or stack[-1] != contain[color]:
                        #print("contain fail")
                        return False # Invalid containment
                if len(stack):
                    contain[color] = stack[-1]
                else:
                    contain[color] = 0                
                stack.append(color)
                curr_order.append(color)
            seen[color] = 1
            if active[color] == 0:
                active[color] = 1
            elif active[color] == 2:
                #print("continuity fail",active)
                return False # Not contiguous
        for i in range(n+1):
            if active[i] == 1:
                if seen[i] == 0:
                    active[i] = 2
        # Test ordering
        for order in orders:
            if len(order) == 0:
                continue
            j = 0
            for color in order:
                if color in curr_order:
                    k = curr_order.index(color)
                    if k < j:
                        #print("order fail")
                        return False
                    j = k
        orders.append(curr_order)

    return True

t = int(input())
res = []
for i in range(t):
    input()
    n, m = map(int,input().split())
    case = []
    for _ in range(m):
        case.append(list(map(int,input().split()))[1:])
    res.append(["NO","YES"][solve(n, case)])
for i in res:print(i)