Biweekly Contest 168

def lexicographicallySmallestString(s):
  n = len(s)
  result = s  # k=1 gives original string

  # Try reversing first k characters
  for k in range(1, n + 1):
    candidate = s[:k][::-1] + s[k:]
    if candidate < result:
      result = candidate

  # Try reversing last k characters
  for k in range(1, n + 1):
    candidate = s[:-k] + s[-k:][::-1] if k < n else s[::-1]
    if candidate < result:
      result = candidate

  return result

def lexicographicallySmallestString(s):
  n = len(s)
  candidates = []

  for k in range(1, n + 1):
    candidates.append(s[:k][::-1] + s[k:])  # Reverse first k
    candidates.append(s[:n-k] + s[n-k:][::-1])  # Reverse last k

  return min(candidates)

def maxSumOfSquares(num, sum_val):
  # Check feasibility
  # First digit must be >= 1, remaining can be 0-9
  if sum_val < 1 or sum_val > 9 * num:
    return ""

  result = []
  remaining_sum = sum_val
  remaining_pos = num

  for i in range(num):
    remaining_pos -= 1
    # Min digit at this position: ensures remaining can reach remaining_sum
    min_digit = 0 if i > 0 else 1  # First digit can't be 0
    # Max sum achievable with remaining positions
    max_remaining = 9 * remaining_pos

    # Find the largest digit we can place
    for d in range(9, min_digit - 1, -1):
      if d <= remaining_sum and remaining_sum - d <= max_remaining:
        # Also ensure first digit is not 0
        if i == 0 and d == 0:
          continue
        result.append(str(d))
        remaining_sum -= d
        break
    else:
      return ""

  return ''.join(result)

def maxSumOfSquares(num, sum_val):
  if sum_val < 1 or sum_val > 9 * num:
    return ""

  digits = []
  remaining = sum_val

  for i in range(num):
    # Positions left after this one
    left = num - i - 1
    # Try placing largest possible digit
    for d in range(9, -1, -1):
      # First digit can't be 0
      if i == 0 and d == 0:
        continue
      new_remaining = remaining - d
      # Check if remaining positions can achieve new_remaining
      if 0 <= new_remaining <= 9 * left:
        digits.append(str(d))
        remaining = new_remaining
        break

  return ''.join(digits) if remaining == 0 else ""

def minOperations(nums1, nums2):
  n = len(nums1)
  # nums2 has n+1 elements

  # Try each position in nums1 as the one to duplicate
  min_cost = float('inf')

  for dup_idx in range(n):
    # We'll use nums1[dup_idx] for two positions in nums2
    # Greedy matching: sort both and match
    # Actually, optimal is to match sorted arrays

    # Cost for matching nums1[i] to nums2[i] for i in [0, n)
    # and nums1[dup_idx] to nums2[n]
    # But positions matter!

    pass

  # Better approach: DP or observe structure
  # Actually, the positions correspond directly!
  # nums1[i] -> nums2[i], and one nums1[j] -> nums2[n] via append

  # Cost = sum(|nums1[i] - nums2[i]|) + |nums1[j] - nums2[n]|
  # where j is chosen optimally

  base_cost = sum(abs(nums1[i] - nums2[i]) for i in range(n))

  # Find best j to duplicate for position n
  min_total = float('inf')
  for j in range(n):
    cost = base_cost + abs(nums1[j] - nums2[n])
    min_total = min(min_total, cost)

  return min_total

def minOperations(nums1, nums2):
  n = len(nums1)

  # Base cost: match nums1[i] to nums2[i] directly
  base_cost = sum(abs(nums1[i] - nums2[i]) for i in range(n))

  # Additional cost: duplicate one nums1[j] for nums2[n]
  min_extra = min(abs(nums1[j] - nums2[n]) for j in range(n))

  return base_cost + min_extra

def countWays(mat):
  from math import gcd
  from collections import defaultdict

  MOD = 10**9 + 7
  m, n = len(mat), len(mat[0])

  # dp[g] = number of ways to achieve gcd = g
  dp = defaultdict(int)

  # Initialize with first row
  for val in mat[0]:
    dp[val] = (dp[val] + 1) % MOD

  # Process remaining rows
  for row_idx in range(1, m):
    new_dp = defaultdict(int)
    for prev_gcd, count in dp.items():
      for val in mat[row_idx]:
        new_gcd = gcd(prev_gcd, val)
        new_dp[new_gcd] = (new_dp[new_gcd] + count) % MOD
    dp = new_dp

  return dp[1]

def countWays(mat):
  from math import gcd

  MOD = 10**9 + 7
  m, n = len(mat), len(mat[0])
  MAX_VAL = 151

  # dp[g] = number of ways to achieve gcd = g
  dp = [0] * MAX_VAL

  # Initialize with first row
  for val in mat[0]:
    dp[val] = (dp[val] + 1) % MOD

  # Process remaining rows
  for row_idx in range(1, m):
    new_dp = [0] * MAX_VAL
    for prev_gcd in range(1, MAX_VAL):
      if dp[prev_gcd] == 0:
        continue
      for val in mat[row_idx]:
        new_gcd = gcd(prev_gcd, val)
        new_dp[new_gcd] = (new_dp[new_gcd] + dp[prev_gcd]) % MOD
    dp = new_dp

  return dp[1]