Weekly Contest 483

def largestEvenNumber(s):
  # Find rightmost '2'
  last_2 = s.rfind('2')
  if last_2 == -1:
    return ""
  return s[:last_2 + 1]

def wordSquares(words):
  from collections import defaultdict

  # Index words by character at each position
  by_pos = defaultdict(lambda: defaultdict(list))
  for word in words:
    for i, c in enumerate(word):
      by_pos[i][c].append(word)

  results = []

  for top in words:
    # left[0] == top[0]
    for left in by_pos[0][top[0]]:
      if left == top:
        continue
      # right[0] == top[3]
      for right in by_pos[0][top[3]]:
        if right in (top, left):
          continue
        # bottom[0] == left[3], bottom[3] == right[3]
        for bottom in by_pos[0][left[3]]:
          if bottom in (top, left, right):
            continue
          if bottom[3] == right[3]:
            results.append([top, left, right, bottom])

  # Sort by (top, left, right, bottom)
  results.sort()
  return results

def minCost(s, t, flipCost, swapCost, crossCost):
  type_a = 0  # s[i]='0', t[i]='1'
  type_b = 0  # s[i]='1', t[i]='0'

  for i in range(len(s)):
    if s[i] != t[i]:
      if s[i] == '0':
        type_a += 1
      else:
        type_b += 1

  # Pair same types: each pair costs min(2*flipCost, X)
  # Pair different types: each costs min(2*flipCost, 2*crossCost)

  # Cost to fix a pair of same type (e.g., two type-A)
  same_pair_cost = min(2 * flipCost, 2 * crossCost)

  # Cost to fix one type-A and one type-B together
  diff_pair_cost = min(2 * flipCost, 2 * crossCost)

  # Single mismatch cost
  single_cost = flipCost

  total = 0

  # Pair as many same types as possible
  pairs_a = type_a // 2
  pairs_b = type_b // 2
  total += pairs_a * same_pair_cost
  total += pairs_b * same_pair_cost

  remaining_a = type_a % 2
  remaining_b = type_b % 2

  # If both have one remaining, pair them
  if remaining_a == 1 and remaining_b == 1:
    total += diff_pair_cost
  elif remaining_a == 1:
    total += single_cost
  elif remaining_b == 1:
    total += single_cost

  return total

def minMergeCost(lists):
  n = len(lists)
  INF = float('inf')

  # Precompute sorted merged list for each mask
  from functools import lru_cache

  @lru_cache(maxsize=None)
  def merged_list(mask):
    result = []
    for i in range(n):
      if mask & (1 << i):
        result.extend(lists[i])
    result.sort()
    return tuple(result)

  def median(arr):
    m = len(arr)
    return arr[(m - 1) // 2]

  def merge_cost(arr1, arr2):
    return len(arr1) + len(arr2) + abs(median(arr1) - median(arr2))

  # dp[mask] = min cost to merge all lists in mask
  dp = [INF] * (1 << n)

  # Base case: single list costs 0
  for i in range(n):
    dp[1 << i] = 0

  for mask in range(1, 1 << n):
    if bin(mask).count('1') <= 1:
      continue

    # Try all ways to split mask into two non-empty parts
    submask = mask
    while submask > 0:
      other = mask ^ submask
      if other > 0 and submask < other:  # Avoid counting twice
        cost = dp[submask] + dp[other]
        cost += merge_cost(merged_list(submask), merged_list(other))
        dp[mask] = min(dp[mask], cost)
      submask = (submask - 1) & mask

  return dp[(1 << n) - 1]