Appearance
question:def largest_special_clique(n: int, graph: List[List[int]], special: List[bool]) -> int: Returns the size of the largest fully connected subgraph that consists only of individuals with special status. :param n: An integer representing the number of individuals. :param graph: A 2D list of integers where graph[i][j] is 1 if there is an edge between individual i and individual j, and 0 otherwise. :param special: A list of booleans where special[i] is True if the i-th individual has special status, and False otherwise. :return: The size of the largest fully connected subgraph that consists only of individuals with special status. >>> largest_special_clique(5, [[0,1,1,0,0],[1,0,0,1,0],[1,0,0,0,1],[0,1,0,0,1],[0,0,1,1,0]], [True, False, True, False, True]) 2 >>> largest_special_clique(4, [[0,1,0,0],[1,0,1,0],[0,1,0,1],[0,0,1,0]], [False, False, False, False]) 0 pass
answer:def largest_special_clique(n, graph, special): Returns the size of the largest fully connected subgraph that consists only of individuals with special status. special_nodes = [i for i in range(n) if special[i]] size = len(special_nodes) max_clique = 0 def is_clique(nodes): for i in range(len(nodes)): for j in range(i + 1, len(nodes)): if graph[nodes[i]][nodes[j]] == 0: return False return True from itertools import combinations for k in range(size, 0, -1): for nodes in combinations(special_nodes, k): if is_clique(nodes): return k return 0
question:def four_sum(arr: List[int], target: int) -> List[List[int]]: Find all unique quadruples [a, b, c, d] in arr such that a + b + c + d = target. Each quadruple in the result must be sorted in ascending order. The function should return a list of all such quadruples without duplicates. >>> four_sum([1, 0, -1, 0, -2, 2], 0) [ [-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1] ] >>> four_sum([2, 2, 2, 2, 2], 8) [ [2, 2, 2, 2] ] from solution import four_sum def test_example_case_1(): result = four_sum([1, 0, -1, 0, -2, 2], 0) expected = [ [-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1] ] result_sorted = sorted([sorted(quad) for quad in result]) expected_sorted = sorted([sorted(quad) for quad in expected]) assert result_sorted == expected_sorted def test_example_case_2(): result = four_sum([2, 2, 2, 2, 2], 8) expected = [ [2, 2, 2, 2] ] result_sorted = sorted([sorted(quad) for quad in result]) expected_sorted = sorted([sorted(quad) for quad in expected]) assert result_sorted == expected_sorted def test_no_quadruples(): result = four_sum([1, 2, 3, 4], 100) expected = [] assert result == expected def test_quadruples_with_duplicates(): result = four_sum([1, 1, 1, 1, 1, 1], 4) expected = [ [1, 1, 1, 1] ] result_sorted = sorted([sorted(quad) for quad in result]) expected_sorted = sorted([sorted(quad) for quad in expected]) assert result_sorted == expected_sorted def test_multiple_solutions(): result = four_sum([-3, -1, 0, 2, 4, 5], 0) expected = [ [-3, -1, 0, 4] ] result_sorted = sorted([sorted(quad) for quad in result]) expected_sorted = sorted([sorted(quad) for quad in expected]) assert result_sorted == expected_sorted
answer:def four_sum(arr, target): from itertools import combinations arr.sort() quadruples = set() n = len(arr) for i in range(n - 3): for j in range(i + 1, n - 2): left, right = j + 1, n - 1 while left < right: s = arr[i] + arr[j] + arr[left] + arr[right] if s == target: quadruples.add((arr[i], arr[j], arr[left], arr[right])) left += 1 right -= 1 elif s < target: left += 1 else: right -= 1 return [list(quadruple) for quadruple in quadruples]
question:from typing import List, Tuple def find_pairs(array: List[int], k: int) -> List[Tuple[int, int]]: Find all pairs of indices (i, j) such that i < j and array[i] + array[j] == k. >>> find_pairs([1, 2, 3, 4, 5], 5) [(0, 3), (1, 2)] >>> find_pairs([1, 2, 3, 4, 5], 10) [] >>> find_pairs([-1, -2, 2, 1, 5], 0) [(0, 3), (1, 2)] >>> find_pairs([1, 1, 1, 1, 1], 2) [(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] >>> find_pairs([1], 2) [] >>> find_pairs([], 0) [] >>> find_pairs([10**5, -(10**5), 0, 10**5, -(10**5)], 0) [(0, 1), (0, 4), (1, 3), (3, 4)]
answer:from typing import List, Tuple def find_pairs(array: List[int], k: int) -> List[Tuple[int, int]]: Find all pairs of indices (i, j) such that i < j and array[i] + array[j] == k. pairs = [] n = len(array) for i in range(n): for j in range(i + 1, n): if array[i] + array[j] == k: pairs.append((i, j)) return pairs
question:def find_min_travel_cost(n: int, edges: List[Tuple[int, int, int]]) -> int: Calculate the minimum travel cost to traverse all edges in the forest at least once. Parameters: - n: an integer, the number of nodes in the forest. - edges: a list of tuples, where each tuple contains three integers u, v, and w representing an edge from node u to node v with a travel cost w. Returns: - an integer, representing the minimum cost required to traverse every edge in the forest at least once. >>> find_min_travel_cost(4, [(1, 2, 1), (2, 3, 2), (3, 4, 1)]) == 8 >>> find_min_travel_cost(1, []) == 0 >>> find_min_travel_cost(2, [(1, 2, 5)]) == 10 >>> find_min_travel_cost(5, [(1, 2, 3), (2, 3, 1), (3, 4, 4), (4, 5, 2)]) == 20 >>> find_min_travel_cost(3, [(1, 2, 1000000), (2, 3, 1000000)]) == 4000000
answer:def find_min_travel_cost(n, edges): Calculate the minimum travel cost to traverse all edges in the forest at least once. Parameters: - n: an integer, the number of nodes in the forest. - edges: a list of tuples, where each tuple contains three integers u, v, and w representing an edge from node u to node v with a travel cost w. Returns: - an integer, representing the minimum cost required to traverse every edge in the forest at least once. # Use Kruskal's algorithm to find the Minimum Spanning Tree (MST) parent = list(range(n + 1)) rank = [0] * (n + 1) def find(u): if parent[u] != u: parent[u] = find(parent[u]) return parent[u] def union(u, v): root_u = find(u) root_v = find(v) if root_u != root_v: if rank[root_u] > rank[root_v]: parent[root_v] = root_u elif rank[root_u] < rank[root_v]: parent[root_u] = root_v else: parent[root_v] = root_u rank[root_u] += 1 # Sort edges based on their weight edges.sort(key=lambda x: x[2]) mst_cost = 0 for u, v, w in edges: if find(u) != find(v): union(u, v) mst_cost += w # Each edge in the MST will be traversed twice in the optimal path return 2 * mst_cost # Example usage: n = 4 edges = [(1, 2, 1), (2, 3, 2), (3, 4, 1)] print(find_min_travel_cost(n, edges)) # Output: 8