Appearance
question:from typing import List, Tuple def calculate_enjoyments(n: int, q: int, beauty_scores: List[int], roads: List[Tuple[int, int]], queries: List[Tuple[int, int]]) -> List[int]: Calculate the total enjoyment Chef can get by traveling from city A to city B. Parameters: n (int): The number of cities q (int): The number of queries beauty_scores (List[int]): The beauty scores for each of the cities roads (List[Tuple[int, int]]): The roads connecting the cities queries (List[Tuple[int, int]]): The queries specifying two cities between which the enjoyment is to be calculated Returns: List[int]: A list of integers representing the total enjoyment for each query Example: >>> n = 5 >>> q = 3 >>> beauty_scores = [2, 3, 1, 4, 6] >>> roads = [(1, 2), (2, 3), (3, 4), (4, 5)] >>> queries = [(1, 5), (3, 5), (2, 4)] >>> calculate_enjoyments(n, q, beauty_scores, roads, queries) [16, 11, 8]
answer:from collections import defaultdict, deque def calculate_enjoyments(n, q, beauty_scores, roads, queries): # Create adjacency list for the given roads graph = defaultdict(list) for u, v in roads: graph[u].append(v) graph[v].append(u) # Prepare a parents and depths array to help find LCA parents = [0] * (n + 1) depth = [0] * (n + 1) subtree_sum = [0] * (n + 1) def bfs(start): queue = deque([start]) visited = {start} parents[start] = -1 depth[start] = 0 subtree_sum[start] = beauty_scores[start - 1] while queue: node = queue.popleft() for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) parents[neighbor] = node depth[neighbor] = depth[node] + 1 subtree_sum[neighbor] = subtree_sum[node] + beauty_scores[neighbor - 1] # Perform BFS from node 1 bfs(1) def lca(a, b): if depth[a] < depth[b]: a, b = b, a while depth[a] > depth[b]: a = parents[a] while a != b: a = parents[a] b = parents[b] return a results = [] for a, b in queries: common_ancestor = lca(a, b) enjoyment = subtree_sum[a] + subtree_sum[b] - 2 * subtree_sum[common_ancestor] + beauty_scores[common_ancestor - 1] results.append(enjoyment) return results
question:from typing import List def max_consecutive_safe_houses(test_cases: List[str]) -> List[int]: Given a list of hiking routes, compute the maximum number of consecutive safe houses ('S') that can be visited starting from any point on the route. Args: test_cases: A list of strings representing different hiking routes. Returns: A list of integers representing the maximum number of consecutive safe houses for each route. Example: >>> max_consecutive_safe_houses(["SSSDSS", "DSSDSDSSS", "SSSSD"]) [3, 3, 4] >>> max_consecutive_safe_houses(["SSSS", "DDDD", "SDSDSDSD"]) [4, 0, 1]
answer:def max_consecutive_safe_houses(test_cases): results = [] for route in test_cases: max_safe = 0 current_safe = 0 for char in route: if char == 'S': current_safe += 1 if current_safe > max_safe: max_safe = current_safe else: current_safe = 0 results.append(max_safe) return results
question:def max_water_trapped(n: int, heights: List[int]) -> int: Calculate the maximum amount of water that can be trapped after raining on a given elevation map. :param n: Integer, length of the list `heights` :param heights: List of non-negative integers representing the elevation map. :return: Integer, maximum water trapped. def process_input(t: int, test_cases: List[Tuple[int, List[int]]]) -> List[int]: Process multiple test cases to determine the maximum amount of water trapped for each case. :param t: Integer, the number of test cases. :param test_cases: List of tuples where each tuple contains (n, heights) for each test case. :return: List of integers representing the result for each test case. from solution import max_water_trapped, process_input def test_max_water_trapped(): assert max_water_trapped(12, [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6 assert max_water_trapped(6, [4, 2, 0, 3, 2, 5]) == 9 assert max_water_trapped(0, []) == 0 assert max_water_trapped(1, [3]) == 0 assert max_water_trapped(2, [3, 3]) == 0 assert max_water_trapped(3, [3, 0, 3]) == 3 def test_process_input(): test_cases = [ (12, [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]), (6, [4, 2, 0, 3, 2, 5]) ] assert process_input(2, test_cases) == [6, 9] test_cases = [ (0, []), (1, [3]), (3, [3, 0, 3]) ] assert process_input(3, test_cases) == [0, 0, 3] def test_edge_cases(): assert max_water_trapped(4, [1, 1, 1, 1]) == 0 assert max_water_trapped(5, [5, 4, 3, 2, 1]) == 0
answer:def max_water_trapped(n, heights): Calculate the maximum amount of water that can be trapped after raining on a given elevation map. :param n: Integer, length of the list `heights` :param heights: List of non-negative integers representing the elevation map. :return: Integer, maximum water trapped. if n == 0: return 0 left = [0] * n right = [0] * n water_trapped = 0 # Fill left array left[0] = heights[0] for i in range(1, n): left[i] = max(left[i - 1], heights[i]) # Fill right array right[n - 1] = heights[n - 1] for i in range(n - 2, -1, -1): right[i] = max(right[i + 1], heights[i]) # Calculate the trapped water for i in range(0, n): water_trapped += min(left[i], right[i]) - heights[i] return water_trapped def process_input(t, test_cases): Process multiple test cases to determine the maximum amount of water trapped for each case. :param t: Integer, the number of test cases. :param test_cases: List of tuples where each tuple contains (n, heights) for each test case. :return: List of integers representing the result for each test case. results = [] for i in range(t): n, heights = test_cases[i] result = max_water_trapped(n, heights) results.append(result) return results
question:def maxAverage(arr: List[int], k: int) -> float: Returns the maximum average sum of any contiguous subarray of length k. >>> maxAverage([1,12,-5,-6,50,3], 4) 12.75 >>> maxAverage([1,2,3,4,5], 2) 4.5 >>> maxAverage([-1,-2,-3,-4,-5], 2) -1.5 >>> maxAverage([1], 1) 1.0 >>> maxAverage([5,5,5,5], 2) 5.0
answer:def maxAverage(arr, k): Returns the maximum average sum of any contiguous subarray of length k. n = len(arr) if k > n: return 0 max_sum = curr_sum = sum(arr[:k]) for i in range(k, n): curr_sum += arr[i] - arr[i - k] max_sum = max(max_sum, curr_sum) return max_sum / k