Biweekly Contest 172

def minOperations(nums):
  n = len(nums)
  ops = 0

  while True:
    start = 3 * ops
    if start >= n:
      return ops

    remaining = nums[start:]
    if len(remaining) == len(set(remaining)):
      return ops

    ops += 1

def maxSumDivisibleByThree(nums):
  # Group by remainder
  groups = [[], [], []]
  for x in nums:
    groups[x % 3].append(x)

  # Sort each group descending
  for g in groups:
    g.sort(reverse=True)

  result = 0

  # Helper to get top k elements from a group
  def top_k(g, k):
    return g[:k] if len(g) >= k else None

  # Case 1: Three from r0
  if len(groups[0]) >= 3:
    result = max(result, sum(groups[0][:3]))

  # Case 2: Three from r1
  if len(groups[1]) >= 3:
    result = max(result, sum(groups[1][:3]))

  # Case 3: Three from r2
  if len(groups[2]) >= 3:
    result = max(result, sum(groups[2][:3]))

  # Case 4: One from each group
  if groups[0] and groups[1] and groups[2]:
    result = max(result, groups[0][0] + groups[1][0] + groups[2][0])

  return result

def maxScore(nums, s):
  n = len(nums)
  ones_positions = [i for i in range(n) if s[i] == '1']
  k = len(ones_positions)

  if k == 0:
    return 0

  # Each '1' at position p can reach any position <= p
  # We want to select k positions for k '1's to maximize score

  # The rightmost '1' can go to any position 0 to ones_positions[-1]
  # The second rightmost can go to any position 0 to ones_positions[-2]
  # etc.

  # Greedy: assign largest nums[i] to '1's that can reach them
  # Process from right to left: for each '1', pick best available position

  available = list(range(n))  # All positions
  selected_values = []

  # Sort ones_positions in descending order (process rightmost first)
  ones_positions.sort(reverse=True)

  for one_pos in ones_positions:
    # This '1' can reach positions 0 to one_pos
    # Find the position with max nums value in [0, one_pos] that's still available
    best_val = -1
    best_idx = -1
    for i, pos in enumerate(available):
      if pos <= one_pos and nums[pos] > best_val:
        best_val = nums[pos]
        best_idx = i
    if best_idx != -1:
      selected_values.append(best_val)
      available.pop(best_idx)

  return sum(selected_values)

def maxScore(nums, s):
  n = len(nums)
  k = s.count('1')
  if k == 0:
    return 0

  # Find rightmost position of each '1'
  one_positions = [i for i in range(n) if s[i] == '1']

  # For optimal assignment: pair largest reachable nums with '1's
  # Sort (nums[i], i) and greedily assign

  indexed = [(nums[i], i) for i in range(n)]
  indexed.sort(reverse=True)

  # one_positions sorted ascending, need k positions
  # one_positions[j] means j-th '1' can reach positions 0..one_positions[j]

  result = 0
  used = 0
  one_idx = k - 1  # Start from rightmost '1'

  for val, pos in indexed:
    if used == k:
      break
    # Check if any remaining '1' can reach this position
    # A '1' at one_positions[j] can reach pos if pos <= one_positions[j]
    if one_idx >= 0 and pos <= one_positions[one_idx]:
      result += val
      used += 1
      one_idx -= 1

  return result

def lastRemaining(n):
  left = 1
  step = 1
  count = n
  from_left = True

  while count > 1:
    if from_left:
      # Delete from left: leftmost always removed
      left += step
    else:
      # Delete from right: leftmost removed only if count is odd
      if count % 2 == 1:
        left += step

    count //= 2
    step *= 2
    from_left = not from_left

  return left