Appearance
question:def count_paths(maze: List[List[int]]) -> int: You are given a rectangular maze of size NxM where some cells may be blocked, and you can't step onto them. You start at the top-left corner of the maze and want to reach the bottom-right corner. You can move up, down, left, or right but cannot move diagonally. Write a function that returns the number of distinct paths from start to end without stepping on any blocked cell. If it is impossible to reach the end, return 0. Examples: >>> count_paths([[0, 0, 0], [0, 1, 0], [0, 0, 0]]) 2 >>> count_paths([[1, 0, 0], [0, 0, 0], [0, 0, 0]]) 0 from solution import count_paths def test_path_no_blocks(): maze = [ [0, 0, 0], [0, 0, 0], [0, 0, 0] ] assert count_paths(maze) == 6 def test_path_with_blocks(): maze = [ [0, 0, 0], [0, 1, 0], [0, 0, 0] ] assert count_paths(maze) == 2 def test_path_start_blocked(): maze = [ [1, 0, 0], [0, 0, 0], [0, 0, 0] ] assert count_paths(maze) == 0 def test_path_end_blocked(): maze = [ [0, 0, 0], [0, 0, 0], [0, 0, 1] ] assert count_paths(maze) == 0 def test_no_possible_way(): maze = [ [0, 1, 0], [1, 1, 0], [0, 0, 0] ] assert count_paths(maze) == 0 def test_single_cell(): maze = [ [0] ] assert count_paths(maze) == 1 def test_large_maze(): maze = [ [0 for _ in range(100)] for _ in range(100) ] assert count_paths(maze) > 0 # Just ensure it returns a positive number (count of paths)
answer:def count_paths(maze): N = len(maze) M = len(maze[0]) # If the start or end is blocked, return 0 as there's no way possible if maze[0][0] == 1 or maze[N-1][M-1] == 1: return 0 # Create a DP table to store the number of ways to reach each cell dp = [[0] * M for _ in range(N)] # Initialize the starting point dp[0][0] = 1 # Fill the DP table for i in range(N): for j in range(M): if maze[i][j] == 1: dp[i][j] = 0 else: if i > 0: dp[i][j] += dp[i-1][j] if j > 0: dp[i][j] += dp[i][j-1] return dp[N-1][M-1]
question:def longest_divisible_subsequence(arr: List[int]) -> int: Find the length of the longest subsequence where each integer is divisible by its predecessor. >>> longest_divisible_subsequence([1, 2, 3, 8, 4, 6]) 4 >>> longest_divisible_subsequence([10]) 1 >>> longest_divisible_subsequence([1, 2, 4, 8, 16]) 5 >>> longest_divisible_subsequence([7, 9, 11, 13]) 1 >>> longest_divisible_subsequence([1, 3, 9, 18, 2, 4, 8]) 4 >>> longest_divisible_subsequence([1000000, 100000, 10000, 1000, 100, 10, 1]) 7
answer:def longest_divisible_subsequence(arr): n = len(arr) arr.sort() dp = [1] * n for i in range(n): for j in range(i): if arr[i] % arr[j] == 0: dp[i] = max(dp[i], dp[j] + 1) return max(dp)
question:from collections import defaultdict, deque def longest_path_and_min_height(n, edges): Compute the longest path in the tree (tree diameter) and the minimum height of the binary tree when restructured by selecting any node as the root. Args: n (int): The number of nodes in the tree. edges (List[Tuple[int, int]]): List of edges representing the tree. Returns: Tuple[int, int]: The length of the longest path and the minimum height of the binary tree optimally restructured. def test_example(): assert longest_path_and_min_height(5, [(1, 2), (1, 3), (3, 4), (3, 5)]) == (3, 2) def test_single_node(): assert longest_path_and_min_height(1, []) == (0, 0) def test_chain(): assert longest_path_and_min_height(4, [(1, 2), (2, 3), (3, 4)]) == (3, 2) def test_star(): assert longest_path_and_min_height(4, [(1, 2), (1, 3), (1, 4)]) == (2, 1) def test_balanced_binary_tree(): assert longest_path_and_min_height(7, [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)]) == (4, 2)
answer:from collections import deque, defaultdict def longestPathAndMinHeight(n, edges): if n == 1: return (0, 0) graph = defaultdict(list) for u, v in edges: graph[u].append(v) graph[v].append(u) def bfs(start): visited = [-1] * (n + 1) q = deque([start]) visited[start] = 0 farthestNode = start maxDistance = 0 while q: node = q.popleft() for neighbor in graph[node]: if visited[neighbor] == -1: q.append(neighbor) visited[neighbor] = visited[node] + 1 if visited[neighbor] > maxDistance: maxDistance = visited[neighbor] farthestNode = neighbor return (farthestNode, maxDistance) # Find one of the farthest nodes from an arbitrary node (say node 1) farthestNode, _ = bfs(1) # Use the farthest node to find the actual longest path in the tree (diameter) otherEndNode, diameter = bfs(farthestNode) # The minimum height of the binary tree rooted optimally midpointDistance = diameter // 2 min_height = (diameter + 1) // 2 return (diameter, min_height) # Define the function to receive input and format the output accordingly def solve(): import sys input = sys.stdin.read data = input().split() n = int(data[0]) edges = [] for i in range(1, len(data), 2): u = int(data[i]) v = int(data[i+1]) edges.append((u, v)) diameter, min_height = longestPathAndMinHeight(n, edges) print(diameter) print(min_height)
question:def longest_subarray_with_sum(arr, n, S): Returns the length of the longest subarray where the sum of its elements is equal to S. If there is no such subarray, returns -1. >>> longest_subarray_with_sum([1, 2, 3, 4, 5], 5, 10) 4 >>> longest_subarray_with_sum([1, 2, 3], 3, 7) -1 >>> longest_subarray_with_sum([1, 2, 3, 4, 5], 5, 15) 5 >>> longest_subarray_with_sum([1, 1, 1, 1, 1], 5, 3) 3 >>> longest_subarray_with_sum([1, 2, 1, 2, 1], 5, 3) 2 >>> longest_subarray_with_sum([1, 2, 3, 0, 0, 0, 4], 7, 6) 6
answer:def longest_subarray_with_sum(arr, n, S): Returns the length of the longest subarray where the sum of its elements is equal to S. If there is no such subarray, returns -1. sum_map = {} current_sum = 0 max_length = -1 for i in range(n): current_sum += arr[i] if current_sum == S: max_length = i + 1 if current_sum - S in sum_map: max_length = max(max_length, i - sum_map[current_sum - S]) if current_sum not in sum_map: sum_map[current_sum] = i return max_length