chat

🔍

question:You are given an array of integers nums where nums[i] is guaranteed to be within the range [0, n) and n is the number of elements in the array. Your task is to transform the array into a permutation of the numbers from 0 to n-1 by applying the minimum number of operations. In each operation, you can choose any two indices i and j (i ≠ j) and swap the values of nums[i] and nums[j]. Input The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. The first line of each test case contains a single integer n (1 ≤ n ≤ 100) — the number of elements in the array. The second line of each test case contains n distinct integers from 0 to n-1 — the given array nums. Output For each test case, output a single integer — the minimum number of swap operations needed to transform the array into a permutation of the numbers from 0 to n-1. Example Input 3 4 1 0 3 2 5 4 2 0 3 1 3 2 1 0 Output 2 3 1 Explanation In the first test case, you can swap nums[0] with nums[1] to get [0, 1, 3, 2], and then swap nums[2] with nums[3] to get [0, 1, 2, 3], so the answer is 2. In the second test case, you can swap nums[0] with nums[4] to get [1, 2, 0, 3, 4], swap nums[0] with nums[2] to get [0, 2, 1, 3, 4], and swap nums[1] with nums[2] to get [0, 1, 2, 3, 4], so the answer is 3. In the third test case, you can swap nums[0] with nums[2] to get [0, 1, 2], so the answer is 1.

answer:def min_swaps_to_permutation(nums): Returns the minimum number of swap operations needed to transform the array into a permutation of the numbers from 0 to n-1. n = len(nums) positions = { value: idx for idx, value in enumerate(nums) } swaps = 0 for i in range(n): while nums[i] != i: swap_with_index = positions[i] nums[i], nums[swap_with_index] = nums[swap_with_index], nums[i] positions[nums[swap_with_index]] = swap_with_index swaps += 1 return swaps def solve(test_cases): results = [] for nums in test_cases: results.append(min_swaps_to_permutation(nums)) return results

question:You are given a tree with n nodes and n-1 edges. Each node has an initial value assigned to it. In one operation, you can choose any node and increase its value by 1. The cost of this operation is equal to the sum of the current values of its direct children. If the node has no children, the cost is zero. Your task is to find the minimum cost required to make the leaf nodes have at least value k. Input - The first line contains two integers n and k (2 ≤ n ≤ 3 ⋅ 10^5, 1 ≤ k ≤ 10^9). - The second line contains n integers, where the i-th integer is the initial value of the i-th node. - Each of the next n-1 lines contains two integers u and v (1 ≤ u, v ≤ n) representing an edge between nodes u and v. Output Output a single integer — the minimum cost required to make all the leaf nodes have at least value k. Example Input ``` 5 5 1 2 3 4 5 1 2 1 3 3 4 3 5 ``` Output ``` 5 ``` Note In the example: - Initially, the leaf nodes are 2, 4, and 5 with values 2, 4, and 5 respectively. - To make node 2 have at least value 5, the cost is 0 since it has no children. - Node 4 needs to be increased from 4 to 5 with a cost of 0. - Node 5 already has the value 5, so no cost is needed. Thus, the total cost is 5.

answer:def min_cost_to_leaf_values(n, k, values, edges): from collections import defaultdict, deque tree = defaultdict(list) for u, v in edges: tree[u].append(v) tree[v].append(u) degrees = {i: len(adj) for i, adj in tree.items()} leaf_nodes = [i for i, d in degrees.items() if d == 1] current_values = dict(enumerate(values, 1)) total_cost = 0 visited = [False] * (n + 1) for leaf in leaf_nodes: queue = deque([leaf]) while queue: node = queue.popleft() if visited[node]: continue visited[node] = True needed_increases = max(0, k - current_values[node]) total_cost += needed_increases for neighbor in tree[node]: current_values[neighbor] += needed_increases if not visited[neighbor]: queue.append(neighbor) return total_cost # Helper function for the ease of test def process_tree_cost(n, k, values, edges): return min_cost_to_leaf_values(n, k, values, edges)

question:You are given a series of events, where each event is represented by a character `'A'`, `'B'`, or `'C'`. Each character represents a different type of event. You need to find the length of the shortest contiguous subarray which contains at least one `'A'`, one `'B'`, and one `'C'`. If no such subarray exists, return `-1`. Input The first line of the input contains an integer n (1 ≤ n ≤ 2 × 10^5) — the length of the series of events. The second line of the input contains a string s of length n which consists of characters `'A'`, `'B'`, and `'C'`. Output Output a single integer — the length of the shortest contiguous subarray containing at least one `'A'`, one `'B'`, and one `'C'`, or `-1` if no such subarray exists. Examples Input 7 CABCA Output 3 Input 6 BCAAAA Output 3 Input 5 AAAAA Output -1 Note In the first example, the shortest contiguous subarray containing at least one of each character is "CAB". In the second example, the shortest contiguous subarray containing at least one of each character is "BCA". In the third example, there is no subarray that contains all characters 'A', 'B', and 'C'.

answer:def shortest_subarray_with_all_events(s): n = len(s) if n < 3: return -1 min_length = float('inf') left = 0 count = {'A': 0, 'B': 0, 'C': 0} for right in range(n): if s[right] in count: count[s[right]] += 1 while all(count[char] > 0 for char in 'ABC'): min_length = min(min_length, right - left + 1) count[s[left]] -= 1 left += 1 return min_length if min_length != float('inf') else -1

question:A tech company is planning to deploy a new software system across its branches worldwide. Each branch is identified by a unique code consisting of uppercase letters. They have a master deployment plan that outlines the deployment sequence in pairs of branch codes, such as "XXX->YYY", where "XXX" is the source branch and "YYY" is the target branch. Unfortunately, the deployment plan may have dependencies resulting in some branches being deployed before others can start. Your task is to determine the sequence of branches that must be deployed based on the given dependencies. If it's not possible to resolve the sequence due to circular dependencies, indicate that deployment is not possible. Input The first line contains a single integer n (1 ≤ n ≤ 100), the number of deployment dependencies. Each of the next n lines contains a dependency in the format "XXX->YYY". Output If a valid deployment sequence exists, output the sequence of branch codes in the order they should be deployed, each code on a new line. If no valid sequence exists due to circular dependencies, output "impossible". Examples Input 3 NYC->LON LON->BER NYC->BER Output NYC LON BER Input 2 A->B B->A Output impossible Note In the first example, the deployment must start from NYC, then proceed to LON, and finally to BER. Each branch is deployed in a sequence that respects the given dependencies. In the second example, there is a circular dependency between branch A and branch B, making it impossible to determine a valid deployment sequence. Therefore, the output is "impossible".

answer:from collections import defaultdict, deque def find_deployment_sequence(n, dependencies): # Build the graph graph = defaultdict(list) indegree = defaultdict(int) branches = set() for dep in dependencies: src, tgt = dep.split("->") graph[src].append(tgt) indegree[tgt] += 1 branches.add(src) branches.add(tgt) # Find all the branches with no incoming dependencies queue = deque() for branch in branches: if indegree[branch] == 0: queue.append(branch) # Topological sort sort_result = [] while queue: current = queue.popleft() sort_result.append(current) for neighbor in graph[current]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) # Check for cycles in the graph if len(sort_result) == len(branches): return sort_result else: return "impossible"