Appearance
question:def has_pair_with_difference(arr: List[int], k: int) -> str: Determines if there exists a pair of distinct indices (i, j) such that the absolute difference between the elements at those indices is equal to a given integer k. Parameters: arr (List[int]): List of integers. k (int): The target absolute difference. Returns: str: "YES" if such a pair exists, otherwise "NO". >>> has_pair_with_difference([1, 5, 3, 4, 2], 3) == "YES" >>> has_pair_with_difference([1, 2, 3, 4], 10) == "NO" >>> has_pair_with_difference([1, 1, 1, 1, 1, 1], 0) == "YES"
answer:def has_pair_with_difference(arr, k): Determines if there exists a pair of distinct indices (i, j) such that the absolute difference between the elements at those indices is equal to a given integer k. Parameters: arr (List[int]): List of integers. k (int): The target absolute difference. Returns: str: "YES" if such a pair exists, otherwise "NO". seen = set() for num in arr: if num + k in seen or num - k in seen: return "YES" seen.add(num) return "NO"
question:def knapsack(n: int, W: int, values: List[int], weights: List[int]) -> int: Determine the maximum total value of items that Anna can carry in her backpack without exceeding the weight limit. Args: n (int): The number of items. W (int): The weight limit of the backpack. values (List[int]): A list of integers representing the values of the items. weights (List[int]): A list of integers representing the weights of the items. Returns: int: The maximum total value of the items that can be carried without exceeding the weight limit. Example: >>> knapsack(4, 10, [60, 100, 120, 30], [2, 4, 6, 1]) 220 >>> knapsack(3, 50, [60, 100, 120], [10, 20, 30]) 220
answer:def knapsack(n, W, values, weights): # Initialize the dp array with zeros dp = [0] * (W + 1) # Iterate through all items for i in range(n): # Update the dp array from end to start for w in range(W, weights[i] - 1, -1): dp[w] = max(dp[w], dp[w - weights[i]] + values[i]) return dp[W]
question:def count_inversed_pairs(arr: list) -> int: Count the number of inversed pairs in an array of distinct positive integers where an inversed pair is defined as a pair of indices (i, j) such that i < j and arr[i] > arr[j]. Parameters: arr (list): List of distinct positive integers Returns: int: Number of inversed pairs Examples: >>> count_inversed_pairs([2, 4, 1, 3, 5]) 3 >>> count_inversed_pairs([1, 2, 3, 4, 5]) 0 >>> count_inversed_pairs([5, 4, 3, 2, 1]) 10 >>> count_inversed_pairs([1]) 0 >>> count_inversed_pairs([2, 1]) 1 >>> count_inversed_pairs([1, 2]) 0
answer:def count_inversed_pairs(arr): Count the number of inversed pairs in the array where an inversed pair is defined as a pair of indices (i, j) such that i < j and arr[i] > arr[j]. Parameters: arr (list): List of distinct positive integers. Returns: int: Number of inversed pairs. def merge_count_split_inv(arr, temp_arr, left, mid, right): i = left # Starting index for left subarray j = mid + 1 # Starting index for right subarray k = left # Starting index to be sorted inv_count = 0 while i <= mid and j <= right: if arr[i] <= arr[j]: temp_arr[k] = arr[i] i += 1 else: temp_arr[k] = arr[j] inv_count += (mid-i + 1) j += 1 k += 1 while i <= mid: temp_arr[k] = arr[i] i += 1 k += 1 while j <= right: temp_arr[k] = arr[j] j += 1 k += 1 for i in range(left, right + 1): arr[i] = temp_arr[i] return inv_count def merge_sort_and_count(arr, temp_arr, left, right): inv_count = 0 if left < right: mid = (left + right)//2 inv_count += merge_sort_and_count(arr, temp_arr, left, mid) inv_count += merge_sort_and_count(arr, temp_arr, mid + 1, right) inv_count += merge_count_split_inv(arr, temp_arr, left, mid, right) return inv_count n = len(arr) temp_arr = [0]*n return merge_sort_and_count(arr, temp_arr, 0, n-1)
question:def max_sum_trees(heights: List[int]) -> int: Calculate the maximum sum of heights of the remaining trees. The sum is maximized while ensuring that no two consecutive trees are kept. >>> max_sum_trees([3, 2, 5, 10, 7]) 15 >>> max_sum_trees([4, 1, 1, 9]) 13 from solution import max_sum_trees def test_max_sum_trees_basic(): assert max_sum_trees([3, 2, 5, 10, 7]) == 15 def test_max_sum_trees_single(): assert max_sum_trees([4]) == 4 def test_max_sum_trees_two(): assert max_sum_trees([4, 1]) == 4 def test_max_sum_trees_three(): assert max_sum_trees([3, 2, 7]) == 10 def test_max_sum_trees_alternating(): assert max_sum_trees([4, 1, 1, 9]) == 13 def test_max_sum_trees_all_equal(): assert max_sum_trees([4, 4, 4, 4, 4]) == 12 def test_max_sum_trees_decreasing(): assert max_sum_trees([5, 4, 3, 2, 1]) == 9 def test_max_sum_trees_increasing(): assert max_sum_trees([1, 2, 3, 4, 5]) == 9 def test_max_sum_trees_empty(): assert max_sum_trees([]) == 0
answer:def max_sum_trees(heights): Calculate the maximum sum of heights of the remaining trees. The sum is maximized while ensuring that no two consecutive trees are kept. n = len(heights) if n == 0: return 0 elif n == 1: return heights[0] # Initialize the maximum sums for the first two elements dp = [0] * n dp[0] = heights[0] dp[1] = max(heights[0], heights[1]) # Fill the dp array for the rest of the elements for i in range(2, n): dp[i] = max(dp[i-1], dp[i-2] + heights[i]) return dp[n-1] # Example usage heights_input = [3, 2, 5, 10, 7] print(max_sum_trees(heights_input)) # Output: 15