Biweekly Contest 170

Key Insight: We need to make the binary string equal to its reverse. Compare s[i] with s[n-1-i] and count mismatches.

Hint 1: Convert n to binary and compare with its reverse. Hint 2: The minimum flips equals the number of positions where the original and reversed strings differ. Hint 3: This is simply counting the Hamming distance between s and reversed(s).

Approach:

1. Convert n to its binary representation (without leading zeros)
2. Reverse the binary string
3. Count positions where the two strings differ
4. Return the count

def minFlips(n):
  s = bin(n)[2:]  # Binary without '0b' prefix
  rev = s[::-1]

  flips = 0
  for i in range(len(s)):
    if s[i] != rev[i]:
      flips += 1

  return flips

Time Complexity: O(log n) for the number of bits Space Complexity: O(log n) for storing the binary string

Key Insight: With small constraints (up to 10^5), we can iterate through each number and compute its waviness directly.

Hint 1: For each number, convert to string and check each middle digit. Hint 2: A digit at position i (not first or last) is a peak if digits[i-1] < digits[i] > digits[i+1]. Hint 3: A digit at position i is a valley if digits[i-1] > digits[i] < digits[i+1].

Approach:

1. Iterate through each number in [num1, num2]
2. For each number, convert to string of digits
3. For each middle position, check if it’s a peak or valley
4. Sum all waviness values

def totalWaviness(num1, num2):
  def waviness(n):
    s = str(n)
    if len(s) < 3:
      return 0
    count = 0
    for i in range(1, len(s) - 1):
      prev, curr, next_ = int(s[i-1]), int(s[i]), int(s[i+1])
      # Peak: strictly greater than both neighbors
      if curr > prev and curr > next_:
        count += 1
      # Valley: strictly less than both neighbors
      elif curr < prev and curr < next_:
        count += 1
    return count

  total = 0
  for num in range(num1, num2 + 1):
    total += waviness(num)
  return total

Time Complexity: O((num2 - num1) * d) where d is the max number of digits Space Complexity: O(d) for the string conversion

Key Insight: The sum of 1+2+…+n = n(n+1)/2. If we negate some numbers, the sum changes by -2*x for each negated number x. So we need to find which numbers to negate.

Hint 1: Total sum S = n(n+1)/2. If we negate a subset with sum X, new sum = S - 2X. So target = S - 2X, meaning X = (S - target)/2. Hint 2: Check if (S - target) is even and non-negative, and X <= S. Hint 3: Greedily pick largest numbers first for negation (to make lexicographically smallest result), then assign remaining numbers.

Approach:

1. Calculate S = n(n+1)/2
2. Check if (S - target)/2 is a valid sum we can form (X must be between 0 and S, and (S-target) must be even)
3. Use greedy: to get lexicographically smallest, we want negative numbers first (smaller values are better at the front)
4. Find which numbers to negate such that their sum equals X

def lexicographicallySmallestPermutation(n, target):
  S = n * (n + 1) // 2

  # target = S - 2X, so X = (S - target) / 2
  diff = S - target
  if diff < 0 or diff % 2 != 0:
    return []

  X = diff // 2
  if X > S:
    return []

  # Find which numbers to negate (their sum should be X)
  # Greedy: pick from largest to smallest
  to_negate = set()
  remaining = X
  for i in range(n, 0, -1):
    if i <= remaining:
      to_negate.add(i)
      remaining -= i

  if remaining != 0:
    return []

  # Build result: for lexicographically smallest,
  # place negative numbers (sorted) first, then positive numbers (sorted)
  negatives = sorted([-x for x in to_negate])
  positives = sorted([x for x in range(1, n + 1) if x not in to_negate])

  return negatives + positives

Time Complexity: O(n) Space Complexity: O(n)

Key Insight: With range up to 10^15, we cannot iterate through each number. Use digit DP to count waviness efficiently.

Hint 1: Use digit DP with states: current position, previous digit, second previous digit, tight constraint, and whether we’ve started. Hint 2: Track both count of numbers and sum of waviness. A digit contributes to waviness if it forms a peak or valley. Hint 3: Compute totalWaviness(num2) - totalWaviness(num1 - 1) to get the answer for the range.

Approach:

1. Implement digit DP that tracks: position, prev digit, prev-prev digit, tight bound, leading zeros
2. At each position, check if prev digit forms a peak/valley (needs prev-prev and current digit)
3. Track both count of valid numbers and sum of waviness contributions
4. Use inclusion-exclusion: answer = f(num2) - f(num1-1)

def totalWaviness(num1, num2):
  from functools import lru_cache

  def solve(num):
    if num < 100:
      return 0
    digits = [int(d) for d in str(num)]
    n = len(digits)

    @lru_cache(maxsize=None)
    def dp(pos, prev2, prev1, tight, started):
      # Returns (count, waviness_sum)
      if pos == n:
        return (1, 0) if started else (0, 0)

      limit = digits[pos] if tight else 9
      total_count, total_waviness = 0, 0

      for d in range(0, limit + 1):
        new_tight = tight and (d == limit)
        new_started = started or (d > 0)

        if not new_started:
          cnt, wav = dp(pos + 1, -1, -1, new_tight, False)
        elif not started and d > 0:
          cnt, wav = dp(pos + 1, -1, d, new_tight, True)
        elif prev1 == -1:
          cnt, wav = dp(pos + 1, -1, d, new_tight, True)
        else:
          cnt, wav = dp(pos + 1, prev1, d, new_tight, True)
          # Check if prev1 is a peak or valley
          if prev2 != -1:
            if prev2 < prev1 > d or prev2 > prev1 < d:
              wav += cnt

        total_count += cnt
        total_waviness += wav

      return (total_count, total_waviness)

    _, result = dp(0, -1, -1, True, False)
    return result

  return solve(num2) - solve(num1 - 1)

Time Complexity: O(d * 10^3) where d is number of digits (up to 16) Space Complexity: O(d * 10^2) for memoization