Rosalind Algorithmic Heights 문제풀이

Python

Rosalind

Bioinformatics

Tip

Author

Taeyoon Kim

Published

September 28, 2024

Modified

November 12, 2024

Dasgupta, Papadimitriou, Vazirani 의 책 “알고리즘” 에 포함된 연습문제의 모음입니다.

Rosalind 는 프로젝트 오일러, 구글 코드 잼 에서 영감을 얻었습니다. 이 프로젝트의 이름은 DNA 이중나선을 발견하는 데 기여한 로잘린드 프랭클린 에서 따왔습니다. Rosalind 는 프로그래밍 실력을 키우고자 하는 생물학자와 분자생물학의 계산 문제를 접해본 적이 없는 프로그래머들에게 도움이 될 것입니다.

1 Fibonacci Numbers

1.1 Problem

The Fibonacci numbers $0,1,1,2,3,5,8,13,21,34,…$ are generated by the simple rule.

Given: A positive integer $n≤25$.

Return: The value of Fn.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

1.2 Sample Dataset

1.3 Sample Output

1.4 Solution

def fibonacci(n: int) -> int:
    fib: list[int] = [0] * (n + 1)
    fib[1] = 1
    
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    
    return fib[n]

n: int = 6
print(f"피보나치 수열의 {n}번째 항: {fibonacci(n)}")

아주 큰수의 피보나치 수열을 계산하는 경우에는 다음 코드.

import gmpy2
from gmpy2 import mpz

def fibonacci_gmpy2(n: int) -> mpz:
    a: mpz = gmpy2.mpz(0)
    b: mpz = gmpy2.mpz(1)
    
    for _ in range(n):
        a, b = b, a + b
    
    return a

# 예제 사용
n: int = 60000
result: mpz = fibonacci_gmpy2(n)

print(f"피보나치 수열의 {n}번째 항:")
print(result)
print(f"자릿수: {len(str(result))}")

2 Binary Search

Binary search is the ultimate divide-and-conquer algorithm. To find a key k in a large file containing keys A[1..n] in sorted order, we first compare k with A[n/2], and depending on the result we recurse either on the first half of the file, A[1..n/2], or on the second half, A[n/2+1..n]. The recurrence now is $T(n)=T(n/2)+O(1)$. Plugging into the master theorem with $(a=1,b=2,d=0)$ we get the familiar solution: a running time of just $O(logn)$.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

The problem is to find a given set of keys in a given array.

Given: Two positive integers $n≤10^5$ and $m≤10^5$, a sorted array A[1..n] of integers from $−10^5$ to $10^5$ and a list of mm integers $−10^5≤k1,k2,…,km≤10^5$.

Return: For each $k_i$, output an index $1≤j≤n$ s.t. $A[j]=k_i$ or”-1”if there is no such index.

2.1 Sample Dataset

5
6
10 20 30 40 50
40 10 35 15 40 20

2.2 Sample Output

4 1 -1 -1 4 2

2.3 Solution

from typing import List, Tuple

def binary_search(arr: List[int], target: int) -> int:
    low, high = 0, len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid + 1  # Adding 1 to convert from 0-based to 1-based indexing
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1  # Target not found

def parse_input(input_str: str) -> Tuple[int, int, List[int], List[int]]:
    lines = input_str.strip().split("\n")
    n = int(lines[0])
    m = int(lines[1])
    array = list(map(int, lines[2].split()))
    items = list(map(int, lines[3].split()))
    
    return n, m, array, items

sample_input = """
5
6
10 20 30 40 50
40 10 35 15 40 20
"""

n, m, array, items = parse_input(sample_input)

results: List[str] = [str(binary_search(array, item)) for item in items]
print(' '.join(results))

3 Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as “Quick Sort”, “Heap Sort”, or “Merge Sort”. However, insertion sort provides several advantages: simple implementation, efficient for (quite) small data sets, O(1)O(1) extra space.

When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort.

Source: Wikipedia

Although it is one of the elementary sorting algorithms with $O(n^2)$ worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as “Merge Sort” or “Quick Sort”.

Insertion sort is a simple algorithm with quadratic running time that builds the final sorted array one item at a time.

Given: A positive integer $n≤10^3$ and an array A[1..n] of integers.

Return: The number of swaps performed by insertion sort algorithm on A[1..n].

3.1 Sample Dataset

6
6 10 4 5 1 2

3.2 Sample Output

3.3 Solution

from typing import List

def parse_input(input_str: str) -> List[int]:
    lines = input_str.strip().split("\n")
    n = int(lines[0])  # Get the number of elements
    array = list(map(int, lines[1].split()))
    return array

def insertion_sort(array: List[int]) -> int:
    swaps = 0
    for i in range(1, len(array)):
        key = array[i]
        j = i - 1
        while j >= 0 and array[j] > key:
            array[j + 1] = array[j]
            swaps += 1
            j -= 1
        array[j + 1] = key
    return swaps

# Sample input
sample_input = """
6
6 10 4 5 1 2
"""

array: List[int] = parse_input(sample_input)
swap_count: int = insertion_sort(array)
print(f"{swap_count}")

4 Degree Array

In an undirected graph, the degree $d(u)$ of a vertex u is the number of neighbors u has, or equivalently, the number of edges incident upon it.

Given: A simple graph with $n≤10^3$ vertices in the edge list format.

Return: An array $D[1..n]$ where $D[i]$ is the degree of vertex i.

4.1 Sample Dataset

4.2 Sample Output

2 4 2 2 2 2

4.3 Solution

from typing import List, Tuple

def parse_input(input_str: str) -> Tuple[int, List[int]]:
    lines = input_str.strip().split("\n")
    nodes, edges = map(int, lines[0].split())
    edge_list: List[int] = []
    for line in lines[1:]:
        edge_list.extend(map(int, line.split()))
    return nodes, edge_list

def calculate_degrees(nodes: int, edge_list: List[int]) -> List[int]:
    degrees: List[int] = [0] * nodes
    for node in edge_list:
        degrees[node - 1] += 1
    return degrees

# Sample input
sample_input = """
6 7
1 2
2 3
6 3
5 6
2 5
2 4
4 1
"""

nodes: int
edge_list: List[int]
nodes, edge_list = parse_input(sample_input)
degrees: List[int] = calculate_degrees(nodes, edge_list)
print(" ".join(map(str, degrees)))

5 Double-Degree Array

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

Given: A simple graph with $n≤10^3$ vertices in the edge list format.

Return: An array D[1..n] where D[i] is the sum of the degrees of $i$’s neighbors.

5.1 Sample Dataset

5.2 Sample Output

3 5 5 5 0

5.3 Solution

from typing import List, Tuple, Dict

def parse_input(input_str: str) -> Tuple[int, List[List[int]]]:
    lines = input_str.strip().split("\n")
    nodes, edges = map(int, lines[0].split())
    edge_list: List[List[int]] = []
    for line in lines[1:]:
        edge_list.append(list(map(int, line.split())))
    return nodes, edge_list

sample_input = """
5 4
1 2
2 3
4 3
2 4
"""

nodes: int
edges_list: List[List[int]]
nodes, edges_list = parse_input(sample_input)

# Create an adjacency list
nodes_neighbours: Dict[str, List[str]] = {str(i+1): [] for i in range(nodes)}
for edge in edges_list:
    nodes_neighbours[str(edge[0])].append(str(edge[1]))
    nodes_neighbours[str(edge[1])].append(str(edge[0]))

# Calculate and print the sum of neighbors' degrees
for i in range(1, nodes + 1):
    sum_of_neighbors_degrees: int = sum(len(nodes_neighbours[str(neighbor)]) for neighbor in nodes_neighbours[str(i)])
    print(sum_of_neighbors_degrees, end=" ")

6 Majority Element

An array A[1..n] is said to have a majority element if more than half of its entries are the same.

Given: A positive integer k≤20, a positive integer $n≤10^4$, and k arrays of size $n$ containing positive integers not exceeding $10^5$.

Return: For each array, output an element of this array occurring strictly more than $\frac{n}{2}$ times if such element exists, and”-1”otherwise.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

6.1 Sample Dataset

4 8
5 5 5 5 5 5 5 5
8 7 7 7 1 7 3 7
7 1 6 5 10 100 1000 1
5 1 6 7 1 1 10 1

6.2 Sample Output

5 7 -1 -1

6.3 Solution

from typing import List

def string_to_int_list(string: str) -> List[int]:
    return list(map(int, string.split()))

def find_possible_majority(numbers: List[int]) -> int:
    leader_index = 0
    leader_count = 1
    for i in range(len(numbers)):
        if numbers[leader_index] == numbers[i]:
            leader_count += 1
        else:
            leader_count -= 1
        if leader_count == 0:
            leader_index = i
            leader_count = 1
    return numbers[leader_index]

def is_majority(numbers: List[int], candidate: int) -> bool:
    count = sum(1 for num in numbers if num == candidate)
    return count > len(numbers) / 2

# Using Moore's voting algorithm
def find_majority(numbers: List[int]) -> int:
    candidate = find_possible_majority(numbers)
    return candidate if is_majority(numbers, candidate) else -1

sample_input = """
4 8
5 5 5 5 5 5 5 5
8 7 7 7 1 7 3 7
7 1 6 5 10 100 1000 1
5 1 6 7 1 1 10 1
"""

_, *number_lists = sample_input.strip().split("\n")
number_lists: List[List[int]] = [string_to_int_list(line) for line in number_lists]
print(*[find_majority(numbers) for numbers in number_lists])

7 Merge Two Sorted Arrays

The merging procedure is an essential part of Merge Sort (which is considered in one of the next problems).

Given: A positive integer $n≤10^5$ and a sorted array A[1..n] of integers from $−10^5$ to $10^5$, a positive integer $m≤10^5$ and a sorted array $B[1..m]$ of integers from $−10^5$ to $10^5$.

Return: A sorted array $C[1..n+m]$ containing all the elements of A and B.

7.1 Sample Dataset

7.2 Sample Output

-5 2 4 10 11 12 18

7.3 Solution

from typing import List

def parse_ints(x: str) -> List[int]:
    return [int(num) for num in x.split()]

def merge_sorted_lists(list1: List[int], list2: List[int]) -> List[int]:
    merged = []
    i, j = 0, 0
    
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            merged.append(list1[i])
            i += 1
        else:
            merged.append(list2[j])
            j += 1
    
    merged.extend(list1[i:])
    merged.extend(list2[j:])
    
    return merged

sample_input = """
4
2 4 10 18
3
-5 11 12
"""

_, list1_str, _, list2_str = sample_input.strip().split("\n")

list1 = parse_ints(list1_str)
list2 = parse_ints(list2_str)

result = merge_sorted_lists(list1, list2)
print(*result)

8 2SUM

Given: A positive integer k≤20, a positive integer $n≤10^4$, and k arrays of size n containing integers from $−10^5$ to $10^5$.

Return: For each array $A[1..n]$, output two different indices $1≤p<q≤n$ such that $A[p]=−A[q]$ if exist, and “-1” otherwise.

8.1 Sample Dataset

4 5
2 -3 4 10 5
8 2 4 -2 -8
-5 2 3 2 -4
5 4 -5 6 8

8.2 Sample Output

8.3 Solution

from typing import List, Tuple, Optional

def parse_ints(x: str) -> List[int]:
    return [int(num) for num in x.split()]

def two_sum(target: int, numbers: List[int]) -> Optional[Tuple[int, int]]:
    complement_indices = {}
    for i, num in enumerate(numbers, start=1):
        if num in complement_indices:
            return complement_indices[num], i
        complement_indices[target - num] = i
    return None

def process_input(input_str: str) -> Tuple[int, int, List[List[int]]]:
    lines = input_str.strip().split("\n")
    k, n = parse_ints(lines[0])
    arrays = [parse_ints(line) for line in lines[1:]]
    return k, n, arrays

sample_input = """
4 5
2 -3 4 10 5
8 2 4 -2 -8
-5 2 3 2 -4
5 4 -5 6 8
"""

k, n, arrays = process_input(sample_input)

for arr in arrays:
    result = two_sum(0, arr)
    if result:
        print(*result)
    else:
        print(-1)

9 3SUM

Given: A positive integer $k≤20$, a positive integer $n≤10^4$, and $k$ arrays of size $n$ containing integers from $−10^5$ to $10^5$.

Return: For each array $A[1..n]$, output three different indices $1≤p<q<r≤n$ such that $A[p]+A[q]+A[r]=0$ if exist, and”-1”otherwise.

9.1 Sample Dataset

4 5
2 -3 4 10 5
8 -6 4 -2 -8
-5 2 3 2 -4
2 4 -5 6 8

9.2 Sample Output

9.3 Solution

from typing import List, Tuple, Optional

def parse_ints(x: str) -> List[int]:
    return [int(num) for num in x.split()]

def process_input(input_str: str) -> Tuple[int, int, List[List[int]]]:
    lines = input_str.strip().split("\n")
    k, n = parse_ints(lines[0])
    arrays = [parse_ints(line) for line in lines[1:]]
    return k, n, arrays

def three_sum(n: int, a: List[int]) -> List[int]:
    h = {}
    for i in range(n):
        for j in range(i + 1, n):
            s = a[i] + a[j]
            if s in h:
                return [h[s] + 1, i + 1, j + 1]
        h[-a[i]] = i
    return [-1]

sample_input = """
4 5
2 -3 4 10 5
8 -6 4 -2 -8
-5 2 3 2 -4
2 4 -5 6 8
"""

k, n, arrays = process_input(sample_input)

for arr in arrays:
    print(*three_sum(n, arr))

10 Breadth-First Search

The task is to use breadth-first search to compute single-source shortest distances in an unweighted directed graph.

Given: A simple directed graph with $n≤10^3$ vertices in the edge list format.

Return: An array D[1..n] where D[i] is the length of a shortest path from the vertex 1 to the vertex $i$ (D[1]=0). If i is not reachable from 1 set D[i] to −1.

10.1 Sample Dataset

10.2 Sample Output

0 -1 2 1 3 2

10.3 Solution

from io import StringIO
from typing import List, Dict, Union, Iterator
from collections import deque

def parse_ints(line: str) -> List[int]:
    return [int(num) for num in line.split()]

def read_non_empty_line(handle: Iterator[str]) -> str:
    line = next(handle).strip()
    while not line:
        line = next(handle).strip()
    return line

def parse_graph(handle: Iterator[str], directed: bool = False, weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]:
    nodes, n_edges = parse_ints(read_non_empty_line(handle))
    
    graph = {n: [] for n in range(1, nodes + 1)}
    
    for _ in range(n_edges):
        edge = parse_ints(read_non_empty_line(handle))
        if weighted:
            f, t, w = edge
            graph[f].append({"n": t, "w": w})
            if not directed:
                graph[t].append({"n": f, "w": w})
        else:
            f, t = edge
            graph[f].append(t)
            if not directed:
                graph[t].append(f)

    return graph

def bfs(graph: Dict[int, List[int]], start: int = 1) -> List[int]:
    n = max(graph.keys())
    distances = [-1] * (n + 1)
    distances[start] = 0
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if distances[neighbor] == -1:
                queue.append(neighbor)
                distances[neighbor] = distances[node] + 1
    
    return distances[1:]

# Sample input
sample_input = """
6 6
4 6
6 5
4 3
3 5
2 1
1 4
"""

graph = parse_graph(StringIO(sample_input), directed=True)
print(*bfs(graph))

11 Connected Components

The task is to use depth-first search to compute the number of connected components in a given undirected graph.

Given: A simple graph with $n≤10^3$ vertices in the edge list format.

Return: The number of connected components in the graph.

11.1 Sample Dataset

11.2 Sample Output

11.3 Solution

from typing import List, Dict, Set, Union

def parse_integers(input_string: str) -> List[int]:
    return list(map(int, input_string.split()))
    
def parse_graph(input_lines: List[str], is_directed: bool = False, is_weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]:
    graph_info = input_lines[0]
    if graph_info == "":
        graph_info = input_lines[1]
    num_nodes, num_edges = parse_integers(graph_info)
    edge_list = input_lines[1:num_edges+1]
    adjacency_list: Dict[int, List[Union[int, Dict[str, int]]]] = {}

    for node in range(1, num_nodes + 1):
        adjacency_list[node] = list()

    for edge in edge_list:
        if is_weighted:
            from_node, to_node, weight = parse_integers(edge)
            adjacency_list[from_node].append({"node": to_node, "weight": weight})
            if not is_directed:
                adjacency_list[to_node].append({"node": from_node, "weight": weight})
        else:
            from_node, to_node = parse_integers(edge)
            adjacency_list[from_node].append(to_node)
            if not is_directed:
                adjacency_list[to_node].append(from_node)

    return adjacency_list

def find_connected_component(start_node: int, graph: Dict[int, List[int]]) -> Set[int]:
    def depth_first_search(current_node: int, visited_nodes: Set[int]) -> Set[int]:
        visited_nodes.add(current_node)
        for neighbor in graph[current_node]:
            if neighbor not in visited_nodes:
                depth_first_search(neighbor, visited_nodes)
        return visited_nodes

    return depth_first_search(start_node, set())

def find_all_components(graph: Dict[int, List[int]]) -> List[Set[int]]:
    unvisited_nodes = set(graph.keys())
    all_components: List[Set[int]] = list()
    while unvisited_nodes:
        component = find_connected_component(next(iter(unvisited_nodes)), graph)
        unvisited_nodes -= component
        all_components.append(component)
    return all_components

sample_input = """
12 13
1 2
1 5
5 9
5 10
9 10
3 4
3 7
3 8
4 8
7 11
8 11
11 12
8 12
"""

graph: Dict[int, List[int]] = parse_graph(sample_input.strip().split("\n"))
print(len(find_all_components(graph)))

12 Building a Heap

A binary heap is a binary tree based data structure that is often used to implement priority queues. Binary heaps, in turn, can be easily implemented using an array if the underlying tree is a complete binary tree. The tree nodes have a natural ordering: row by row, starting at the root and moving left to right within each row. If there are nn nodes, this ordering specifies their positions 1,2,…,n within the array. Moving up and down the tree is easily simulated on the array, using the fact that node number j has parent $⌈j/2⌉$ and children 2j and 2j+1.

The goal of this problem is to build a heap from the given array. For this, go from the end to the beginning of a given array and let each element”bubble up”.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

Given: A positive integer $n≤10^5$ and array A[1..n] of integers from $−10^5$ to $10^5$.

Return: A permuted array A satisfying the binary max heap property: for any $2≤i≤n$, $A[⌊i/2⌋]≥A[i]$.

12.1 Sample Dataset

5
1 3 5 7 2

12.2 Sample Output

7 5 1 3 2

13 Merge Sort

The problem of sorting a list of numbers lends itself immediately to a divide-and-conquer strategy: split the list into two halves, recursively sort each half, and then merge the two sorted sublists (recall the problem “Merge Two Sorted Arrays”).

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

Given: A positive integer $n≤10^5$ and an array $A[1..n]$ of integers from $−10^5$ to $10^5$.

Return: A sorted array $A[1..n]$.

13.1 Sample Dataset

10
20 19 35 -18 17 -20 20 1 4 4

13.2 Sample Output

-20 -18 1 4 4 17 19 20 20 35

13.3 Solution

from typing import List

def parse_integers(line: str) -> List[int]:
    return [int(num) for num in line.split()]

def merge(left: List[int], right: List[int]) -> List[int]:
    merged = []
    left_index, right_index = 0, 0
    
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1
            
    # Append any remaining elements from both halves
    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    
    return merged

def merge_sort(array: List[int]) -> List[int]:
    if len(array) > 1:
        mid_index = len(array) // 2
        left_half = merge_sort(array[:mid_index])
        right_half = merge_sort(array[mid_index:])
        return merge(left_half, right_half)
    else:
        return array

sample_input = """
10
20 19 35 -18 17 -20 20 1 4 4
"""

_, numbers = sample_input.strip().split("\n")
print(*merge_sort(parse_integers(numbers)))

14 2-Way Partition

A partition procedure is an essential part of the Quick Sort algorithm, the subject of one of the following problems. Its main goal is to put the first element of a given array to its proper place in a sorted array. It can be implemented in linear time, by a single scan of a given array. Moreover, it is not hard to come up with an in-place algorithm.

Given: A positive integer $n≤10^5$ and an array $A[1..n]$ of integers from $−10^5$ to $10^5$.

Return: A permuted array $B[1..n]$ such that it is a permutation of A and there is an index $1≤q≤n$ such that $B[i]≤A[1]$ for all $1≤i≤q−1$, $B[q]=A[1]$, and $B[i]>A[1]$ for all $q+1≤i≤n$.

14.1 Sample Dataset

9
7 2 5 6 1 3 9 4 8

14.2 Sample Output

4 2 5 6 1 3 7 9 8

14.3 Solution

from typing import List

def parse_integers(line: str) -> List[int]:
    return [int(number) for number in line.split()]

def partition(array: List[int]) -> List[int]:
    if len(array) <= 1:
        return array
    
    pivot = array[0]
    swap_index = 0
    
    for current_index in range(1, len(array)):
        if array[current_index] <= pivot:
            swap_index += 1
            array[current_index], array[swap_index] = array[swap_index], array[current_index]
    
    array[0], array[swap_index] = array[swap_index], array[0]
    return array

sample_input = """
9
7 2 5 6 1 3 9 4 8
"""

_, input_numbers = sample_input.strip().split("\n")
result = partition(parse_integers(input_numbers))
print(*result)

15 3-Way Partition

This problem is very similar to “2-Way Partition”, but now the goal is to partition an input array more carefully.

Given: A positive integer $n≤10^5$ and an array $A[1..n]$ of integers from $−10^5$ to $10^5$.

Return: An array B[1..n] such that it is a permutation of A and there are indices $1≤q≤r≤n$ such that $B[i]<A[1]$ for all $1≤i≤q−1$, $B[i]=A[1]$ for all $q≤i≤r$, and $B[i]>A[1]$ for all $r+1≤i≤n$.

15.1 Sample Dataset

9
4 5 6 4 1 2 5 7 4

15.2 Sample Output

2 1 4 4 4 5 7 6 5

15.3 Solution

from typing import List, Tuple

def parse_integers(line: str) -> List[int]:
    return [int(number) for number in line.split()]

def three_way_partition(array: List[int], start: int = None, end: int = None) -> Tuple[int, int]:
    if start is None:
        start = 0
    if end is None:
        end = len(array) - 1
    
    pivot = array[start]
    low = start
    current = start
    high = end

    while current <= high:
        if array[current] < pivot:
            array[current], array[low] = array[low], array[current]
            current += 1
            low += 1
        elif array[current] > pivot:
            array[current], array[high] = array[high], array[current]
            high -= 1
        else:
            current += 1

    return low, high

sample_input = """
9
4 5 6 4 1 2 5 7 4
"""

_, input_line = sample_input.strip().split("\n")
numbers = parse_integers(input_line)
three_way_partition(numbers)
print(*numbers)

16 Square in a Graph

Given: A positive integer k≤20 and k simple undirected graphs with $n≤400$ vertices in the edge list format.

Return: For each graph, output”1”if it contains a simple cycle (that is, a cycle which doesn’t intersect itself) of length $4$ and”-1”otherwise.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

16.1 Sample Dataset

16.2 Sample Output

1 -1

16.3 Solution

from typing import List, Dict, Union, Iterator

def parse_integers(line: str) -> List[int]:
    return [int(num) for num in line.split()]

def read_non_empty_line(input_iterator: Iterator[str]) -> str:
    line = next(input_iterator).strip()
    while not line:
        line = next(input_iterator).strip()
    return line

def create_graph(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]:
    num_nodes, num_edges = parse_integers(read_non_empty_line(input_iterator))
    
    graph = {node: [] for node in range(1, num_nodes + 1)}
    
    for _ in range(num_edges):
        edge_data = parse_integers(read_non_empty_line(input_iterator))
        if is_weighted:
            from_node, to_node, weight = edge_data
            graph[from_node].append({"node": to_node, "weight": weight})
            if not is_directed:
                graph[to_node].append({"node": from_node, "weight": weight})
        else:
            from_node, to_node = edge_data
            graph[from_node].append(to_node)
            if not is_directed:
                graph[to_node].append(from_node)

    return graph

def depth_first_search(graph: Dict[int, List[Union[int, Dict[str, int]]]], start: int, max_depth: int):
    def dfs_recursive(current_node: int, current_depth: int, visited: set):
        if current_depth == max_depth:
            yield current_node
        if current_depth < max_depth:
            for neighbor in graph[current_node]:
                neighbor_node = neighbor if isinstance(neighbor, int) else neighbor['node']
                if neighbor_node not in visited:
                    yield from dfs_recursive(neighbor_node, current_depth + 1, visited | {current_node})

    return dfs_recursive(start, 0, set())

def has_square_cycle(graph: Dict[int, List[Union[int, Dict[str, int]]]], cycle_length: int) -> int:
    for start_node in graph:
        for end_node in depth_first_search(graph, start_node, cycle_length - 1):
            if end_node in graph[start_node]:
                return 1
    return -1

def parse_multiple_graphs(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> List[Dict[int, List[Union[int, Dict[str, int]]]]]:
    num_graphs = int(read_non_empty_line(input_iterator))
    return [create_graph(input_iterator, is_directed, is_weighted) for _ in range(num_graphs)]

# Sample input
sample_input = """
2

4 5
3 4
4 2
3 2
3 1
1 2

4 4
1 2
3 4
2 4
4 1
""".strip().split("\n")

# Process the input and print results
graphs = parse_multiple_graphs(iter(sample_input), is_directed=False)
results = [has_square_cycle(graph, 4) for graph in graphs]
print(*results)

17 Testing Bipartiteness

A bipartite graph is a graph $G=(V,E)$ whose vertices can be partitioned into two sets ($V=V_1∪V_2$ and $V_1∩V_2=∅$) such that there are no edges between vertices in the same set (for instance, if $u,v∈V1$, then there is no edge between u and v).

There are many other ways to formulate this property. For instance, an undirected graph is bipartite if and only if it can be colored with just two colors. Another one: an undirected graph is bipartite if and only if it contains no cycles of odd length.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

Given: A positive integer k≤20 and k simple graphs in the edge list format with at most $10^3$ vertices each.

Return: For each graph, output”1”if it is bipartite and”-1”otherwise.

17.1 Sample Dataset

17.2 Sample Output

-1 1

17.3 Solution

from typing import List, Dict, Union, Iterator

def parse_integers(line: str) -> List[int]:
    return [int(num) for num in line.split()]

def read_non_empty_line(input_iterator: Iterator[str]) -> str:
    line = next(input_iterator).strip()
    while not line:
        line = next(input_iterator).strip()
    return line

def parse_graph(input_iterator: Iterator[str], directed: bool = False, weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]:
    num_nodes, num_edges = parse_integers(read_non_empty_line(input_iterator))
    
    graph = {node: [] for node in range(1, num_nodes + 1)}
    
    for _ in range(num_edges):
        edge = parse_integers(read_non_empty_line(input_iterator))
        if weighted:
            from_node, to_node, weight = edge
            graph[from_node].append({"node": to_node, "weight": weight})
            if not directed:
                graph[to_node].append({"node": from_node, "weight": weight})
        else:
            from_node, to_node = edge
            graph[from_node].append(to_node)
            if not directed:
                graph[to_node].append(from_node)

    return graph
    
def is_bipartite(graph: Dict[int, List[int]]) -> int:
    color = {1: 0}
    queue = [1]
    while queue:
        current_node = queue.pop(0)
        for neighbor in graph[current_node]:
            neighbor_color = (color[current_node] + 1) % 2
            if neighbor not in color:
                queue.append(neighbor)
                color[neighbor] = neighbor_color
            elif color[neighbor] != neighbor_color:
                return -1
    return 1

def process_multiple_graphs(input_iterator: Iterator[str]) -> List[int]:
    num_cases = int(read_non_empty_line(input_iterator))
    results = []
    for _ in range(num_cases):
        graph = parse_graph(input_iterator)
        results.append(is_bipartite(graph))
    return results

sample_input = """
2

3 3
1 2
3 2
3 1

4 3
1 4
3 1
1 2
""".strip().split("\n")

# Convert the list to an iterator
sample_input_iterator = iter(sample_input)

# Process multiple graphs
results = process_multiple_graphs(sample_input_iterator)
print(*results)

18 Testing Acyclicity

Given: A positive integer $k≤20$ and k simple directed graphs in the edge list format with at most $10^3$ vertices and $3⋅10^3$ edges each.

Return: For each graph, output”1”if the graph is acyclic and”-1”otherwise.

18.1 Sample Dataset

18.2 Sample Output

1 -1 1

18.3 Solution

from typing import List, Dict, Union, Iterator

def parse_integers(line: str) -> List[int]:
    return [int(num) for num in line.split()]

def read_non_empty_line(input_iter: Iterator[str]) -> str:
    line = next(input_iter).strip()
    while not line:
        line = next(input_iter).strip()
    return line

def parse_graph(input_iter: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]:
    node_count, edge_count = parse_integers(read_non_empty_line(input_iter))
    
    graph = {node: [] for node in range(1, node_count + 1)}
    
    for _ in range(edge_count):
        edge = parse_integers(read_non_empty_line(input_iter))
        if is_weighted:
            source, target, weight = edge
            graph[source].append({"node": target, "weight": weight})
            if not is_directed:
                graph[target].append({"node": source, "weight": weight})
        else:
            source, target = edge
            graph[source].append(target)
            if not is_directed:
                graph[target].append(source)

    return graph

def graph_nodes(graph):
    nodes = set()
    for node, neighbors in graph.items():
        nodes.add(node)
        nodes = nodes.union(neighbors)
    return nodes

def remove_leaves(graph):
    nodes = graph_nodes(graph)
    leaves = nodes - graph.keys()
    return {n: set(v) - leaves for n, v in graph.items() if len(set(v) - leaves)}

def is_dag(graph):
    while graph:
        new_graph = remove_leaves(graph)
        if len(graph) == len(new_graph):
            return -1
        graph = new_graph
    return 1

def parse_multiple_graphs(input_iter: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> List[Dict[int, List[Union[int, Dict[str, int]]]]]:
    case_count = int(read_non_empty_line(input_iter))
    graphs = []
    for _ in range(case_count):
        graphs.append(parse_graph(input_iter, is_directed, is_weighted))
    return graphs

sample_input = """
3

2 1
1 2

4 4
4 1
1 2
2 3
3 1

4 3
4 3
3 2
2 1
""".strip().split("\n")

# Convert the list to an iterator
input_iterator = iter(sample_input)

# Parse multiple graphs
graphs = parse_multiple_graphs(input_iterator, is_directed=True)

# Process each graph
results = [is_dag(graph) for graph in graphs]
print(*results)

19 Dijkstra’s Algorithm

The task is to use Dijkstra’s algorithm to compute single-source shortest distances in a directed graph with positive edge weights.

Given: A simple directed graph with positive edge weights from 1 to $10^3$ and $n≤10^3$ vertices in the edge list format.

Return: An array $D[1..n]$ where $D[i]$ is the length of a shortest path from the vertex 1 to the vertex i ($D[1]=0$). If ii is not reachable from 1 set D[i] to −1.

19.1 Sample Dataset

19.2 Sample Output

0 3 2 5 6 -1

19.3 Solution

from math import inf
from heapq import heappush, heappop
from typing import List, Dict, Union, Iterator

def parse_integers(line: str) -> List[int]:
    return [int(num) for num in line.split()]

def read_non_empty_line(input_iter: Iterator[str]) -> str:
    line = next(input_iter).strip()
    while not line:
        line = next(input_iter).strip()
    return line

def parse_graph(input_iter: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]:
    vertex_count, edge_count = parse_integers(read_non_empty_line(input_iter))
    
    adjacency_list = {vertex: [] for vertex in range(1, vertex_count + 1)}
    
    for _ in range(edge_count):
        edge = parse_integers(read_non_empty_line(input_iter))
        if is_weighted:
            source, destination, weight = edge
            adjacency_list[source].append({"vertex": destination, "weight": weight})
            if not is_directed:
                adjacency_list[destination].append({"vertex": source, "weight": weight})
        else:
            source, destination = edge
            adjacency_list[source].append(destination)
            if not is_directed:
                adjacency_list[destination].append(source)

    return adjacency_list

def dijkstra(graph, start_vertex=1):
    distances = [inf for _ in range(len(graph) + 1)]
    distances[start_vertex] = 0
    priority_queue = []
    heappush(priority_queue, (0, start_vertex))
    visited = set()

    while priority_queue:
        current_vertex = heappop(priority_queue)[1]
        visited.add(current_vertex)
        for neighbor in graph[current_vertex]:
            if isinstance(neighbor, dict):
                next_vertex = neighbor["vertex"]
                edge_weight = neighbor["weight"]
            else:
                next_vertex = neighbor
                edge_weight = 1  # Assume unit weight for unweighted graphs
            
            if next_vertex not in visited:
                new_distance = distances[current_vertex] + edge_weight
                if new_distance < distances[next_vertex]:
                    distances[next_vertex] = new_distance
                    heappush(priority_queue, (distances[next_vertex], next_vertex))

    return [-1 if distance == inf else distance for distance in distances[1:]]

sample_input = """
6 10
3 4 4
1 2 4
1 3 2
2 3 3
6 3 2
3 5 5
5 4 1
3 2 1
2 4 2
2 5 3
""".strip().split("\n")

# Convert the list to an iterator
input_iterator = iter(sample_input)

graph = parse_graph(input_iterator, is_directed=True, is_weighted=True)
print(*dijkstra(graph))

20 Heap Sort

The heap sort algorithm first transforms a given array into a max heap (recall the problem “Building a Heap”). It then repeats the following two simple steps $n−1$ times:

Swap the last element of the heap with its root and decrease the size of the heap by 1.
“Sift-down”the new root element to its proper place.

Given: A positive integer $n≤10^5$ and an array A[1..n] of integers from $−10^5$ to $10^5$.

Return: A sorted array A.

20.1 Sample Dataset

9
2 6 7 1 3 5 4 8 9

20.2 Sample Output

1 2 3 4 5 6 7 8 9

20.3 Solution

from typing import List, Any

def parse_integers(line: str) -> List[int]:
    return [int(num) for num in line.split()]

def bubble_up(heap: List[int], index: int) -> None:
    if index == 0:
        return
    parent_index: int = (index - 1) // 2
    current_index: int = index
    if heap[parent_index] > heap[current_index]:
        bubble_up(heap, parent_index)
    else:
        heap[parent_index], heap[current_index] = heap[current_index], heap[parent_index]
        bubble_up(heap, parent_index)

def build_heap(array: List[int]) -> List[int]:
    heap: List[int] = []
    for i, element in enumerate(array):
        heap.append(element)
        bubble_up(heap, i)
    return heap

def sift_down(heap: List[int], start_index: int, end_index: int) -> None:
    root_index: int = start_index
    while root_index * 2 + 1 <= end_index:
        left_child_index: int = root_index * 2 + 1
        right_child_index: int = left_child_index + 1
        swap_index: int = root_index
        if heap[swap_index] < heap[left_child_index]:
            swap_index = left_child_index
        if right_child_index <= end_index and heap[swap_index] < heap[right_child_index]:
            swap_index = right_child_index
        if swap_index != root_index:
            heap[root_index], heap[swap_index] = heap[swap_index], heap[root_index]
            root_index = swap_index
        else:
            return

def heap_sort(array: List[int]) -> List[int]:
    heap: List[int] = build_heap(array)
    last_index: int = len(heap) - 1
    while last_index > 0:
        heap[0], heap[last_index] = heap[last_index], heap[0]
        last_index -= 1
        sift_down(heap, 0, last_index)
    return heap

sample_input: str = """
9
2 6 7 1 3 5 4 8 9
"""

_, input_array_str = sample_input.strip().split("\n")
input_array: List[int] = parse_integers(input_array_str)
sorted_array: List[int] = heap_sort(input_array)
print(*sorted_array)

21 Counting Inversions

An inversion of an array A[1..n] is a pair of indices $(i,j)$ such that $1≤i<j≤n$ and A[i]>A[j]. The number of inversions shows how far the array is from being sorted: if it is already sorted then there are no inversions, whereas if it is sorted in reverse order then the number of inversions is maximal.

Given: A positive integer $n≤10^5$ and an array $A[1..n]$ of integers from $−10^5$ to $10^5$.

Return: The number of inversions in A.

21.1 Sample Dataset

5
-6 1 15 8 10

21.2 Sample Output

21.3 Solution

from typing import List, Tuple

def parse_integers(line: str) -> List[int]:
    return [int(num) for num in line.split()]

def merge_and_count_inversions(left: List[int], right: List[int]) -> Tuple[List[int], int]:
    merged: List[int] = []
    inversion_count: int = 0
    left_length: int = len(left)
    left_index: int = 0

    while left and right:
        if left[0] <= right[0]:
            left_index += 1
            merged.append(left.pop(0))
        else:
            inversion_count += left_length - left_index
            merged.append(right.pop(0))

    merged.extend(left)
    merged.extend(right)
    return merged, inversion_count

def merge_sort_and_count_inversions(arr: List[int]) -> Tuple[List[int], int]:
    if len(arr) > 1:
        mid: int = len(arr) // 2
        left_half, left_inversions = merge_sort_and_count_inversions(arr[:mid])
        right_half, right_inversions = merge_sort_and_count_inversions(arr[mid:])
        merged, merge_inversions = merge_and_count_inversions(left_half, right_half)
        total_inversions: int = left_inversions + right_inversions + merge_inversions
        return merged, total_inversions
    else:
        return arr, 0

sample_input: str = """
5
-6 1 15 8 10
"""

_, input_array_str = sample_input.strip().split("\n")
input_array: List[int] = parse_integers(input_array_str)
_, inversion_count = merge_sort_and_count_inversions(input_array)
print(inversion_count)

22 Bellman-Ford Algorithm

The task is to use Bellman-Ford algorithm to compute single-source shortest distances in a directed graph with possibly negative edge weights (but without negative cycles).

Given: A simple directed graph with integer edge weights from $−10^3$ to $10^3$ and $n≤10^3$ vertices in the edge list format.

Return: An array D[1..n] where D[i] is the length of a shortest path from the vertex 1 to the vertex ii (D[1]=0). If ii is not reachable from 1 set D[i] to x.

22.1 Sample Dataset

22.2 Sample Output

0 5 5 6 9 7 9 8 x

22.3 Solution

from math import inf, isinf
from typing import List, Dict, Union, Iterator, Set, Tuple

def parse_integers(line: str) -> List[int]:
    return [int(num) for num in line.split()]

def read_non_empty_line(input_iterator: Iterator[str]) -> str:
    line = next(input_iterator).strip()
    while not line:
        line = next(input_iterator).strip()
    return line

EdgeInfo = Dict[str, int]
Graph = Dict[int, List[Union[int, EdgeInfo]]]

def parse_graph(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Graph:
    vertex_count, edge_count = parse_integers(read_non_empty_line(input_iterator))
    
    adjacency_list: Graph = {vertex: [] for vertex in range(1, vertex_count + 1)}
    
    for _ in range(edge_count):
        edge_data = parse_integers(read_non_empty_line(input_iterator))
        if is_weighted:
            source_vertex, target_vertex, edge_weight = edge_data
            adjacency_list[source_vertex].append({"node": target_vertex, "weight": edge_weight})
            if not is_directed:
                adjacency_list[target_vertex].append({"node": source_vertex, "weight": edge_weight})
        else:
            source_vertex, target_vertex = edge_data
            adjacency_list[source_vertex].append(target_vertex)
            if not is_directed:
                adjacency_list[target_vertex].append(source_vertex)

    return adjacency_list

def count_edges(graph: Graph) -> int:
    return sum(len(neighbors) for neighbors in graph.values())

def get_all_vertices(graph: Graph) -> Set[int]:
    all_vertices: Set[int] = set(graph.keys())
    for neighbors in graph.values():
        for neighbor in neighbors:
            if isinstance(neighbor, dict):
                all_vertices.add(neighbor["node"])
            else:
                all_vertices.add(neighbor)
    return all_vertices

def bellman_ford(graph: Graph, start_vertex: int = 1) -> List[Union[int, str]]:
    distances: Dict[int, float] = {vertex: inf for vertex in get_all_vertices(graph)}
    distances[start_vertex] = 0
    for _ in range(count_edges(graph) - 1):
        for current_vertex, neighbors in graph.items():
            for neighbor in neighbors:
                if isinstance(neighbor, dict):
                    target_vertex = neighbor["node"]
                    edge_weight = neighbor["weight"]
                    if distances[current_vertex] + edge_weight < distances[target_vertex]:
                        distances[target_vertex] = distances[current_vertex] + edge_weight
    return ["x" if isinf(distance) else distance for distance in distances.values()]

sample_input: str = """
9 13
1 2 10
3 2 1
3 4 1
4 5 3
5 6 -1
7 6 -1
8 7 1
1 8 8
7 2 -4
2 6 2
6 3 -2
9 5 -10
9 4 7
""".strip().split("\n")

# Convert the list to an iterator
input_iterator = iter(sample_input)

# Parse the graph with correct parameters
graph = parse_graph(input_iterator, is_directed=True, is_weighted=True)

# Run Bellman-Ford algorithm
result = bellman_ford(graph)
print(*result)

23 Shortest Cycle Through a Given Edge

Given: A positive integer $k≤20$ and k simple directed graphs with positive integer edge weights and at most $10^3$ vertices in the edge list format.

Return: For each graph, output the length of a shortest cycle going through the first specified edge if there is a cycle and”-1”otherwise.

23.1 Sample Dataset

23.2 Sample Output

-1 10

23.3 Solution

from typing import List, Dict, Union, Iterator, Tuple
from math import inf
from heapq import heappush, heappop
from io import StringIO

GraphNode = Union[int, Dict[str, int]]
Graph = Dict[int, List[GraphNode]]

def parse_integers(line: str) -> List[int]:
    return [int(num) for num in line.split()]

def read_non_empty_line(input_iter: Iterator[str]) -> str:
    line = next(input_iter).strip()
    while not line:
        line = next(input_iter).strip()
    return line

def parse_graph(input_iter: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Graph:
    vertex_count, edge_count = parse_integers(read_non_empty_line(input_iter))
    
    adj_list: Graph = {vertex: [] for vertex in range(1, vertex_count + 1)}
    
    for _ in range(edge_count):
        edge_data = parse_integers(read_non_empty_line(input_iter))
        if is_weighted:
            src, dest, weight = edge_data
            adj_list[src].append({"node": dest, "weight": weight})
            if not is_directed:
                adj_list[dest].append({"node": src, "weight": weight})
        else:
            src, dest = edge_data
            adj_list[src].append(dest)
            if not is_directed:
                adj_list[dest].append(src)

    return adj_list

def dijkstra(graph: Graph, start: int = 1) -> List[int]:
    distances = [inf for _ in range(len(graph) + 1)]
    distances[start] = 0
    priority_queue = []
    heappush(priority_queue, (0, start))
    visited = set()

    while priority_queue:
        _, current_node = heappop(priority_queue)
        if current_node in visited:
            continue
        visited.add(current_node)
        for neighbor in graph[current_node]:
            if isinstance(neighbor, dict):
                neighbor_node, edge_weight = neighbor["node"], neighbor["weight"]
            else:
                neighbor_node, edge_weight = neighbor, 1
            if neighbor_node not in visited:
                new_distance = distances[current_node] + edge_weight
                if new_distance < distances[neighbor_node]:
                    distances[neighbor_node] = new_distance
                    heappush(priority_queue, (new_distance, neighbor_node))

    return [-1 if d == inf else d for d in distances[1:]]

def extract_first_edges(input_handle: StringIO) -> List[List[int]]:
    lines = input_handle.read().splitlines()
    graph_count = int(lines[0])
    current_line = 1
    first_edges = []
    for _ in range(graph_count):
        while not lines[current_line]:
            current_line += 1
        _, edge_count = map(int, lines[current_line].split())
        first_edges.append(list(map(int, lines[current_line + 1].split())))
        current_line += int(edge_count) + 1
    return first_edges

def calculate_cycle_length(graph: Graph, edge: List[int]) -> int:
    distance = dijkstra(graph, start=edge[1])[edge[0] - 1]
    return distance if distance == -1 else distance + edge[2]

def parse_multiple_graphs(input_str: str, directed: bool = False, weighted: bool = True) -> List[Graph]:
    input_iter = iter(input_str.splitlines())
    graph_count = int(next(input_iter))
    graphs = []
    for _ in range(graph_count):
        graphs.append(parse_graph(input_iter, is_directed=directed, is_weighted=weighted))
    return graphs

# Sample input
sample_input = """
2

4 5
2 4 2
3 2 1
1 4 3
2 1 10
1 3 4

4 5
3 2 1
2 4 2
4 1 3
2 1 10
1 3 4
"""

# Main execution
input_handle = StringIO(sample_input.strip())
first_edges = extract_first_edges(input_handle)
input_handle.seek(0)  # Reset the StringIO object to the beginning
graphs = parse_multiple_graphs(input_handle.read(), directed=True, weighted=True)
results = [calculate_cycle_length(graphs[i], first_edges[i]) for i in range(len(graphs))]
print(*results)

24 Median

The task is to implement a linear time randomized algorithm for the selection problem.

Given: A positive integer n≤105n≤105 and an array $A[1..n]$ of integers from $−10^5$ to $10^5$, a positive number $k≤n$.

Return: The k-th smallest element of A.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

24.1 Sample Dataset

11
2 36 5 21 8 13 11 20 5 4 1
8

24.2 Sample Output

24.3 Solution

from typing import List, Tuple
from io import StringIO

def parse_integers(line: str) -> List[int]:
    """Parse a line of space-separated integers into a list of integers."""
    return [int(num) for num in line.split()]

def three_way_partition(arr: List[int], low: int = 0, high: int = None) -> Tuple[int, int]:
    """Partition the array into three parts based on a pivot."""
    if high is None:
        high = len(arr) - 1
    
    pivot = arr[low]
    mid = low

    while mid <= high:
        if arr[mid] < pivot:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] > pivot:
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
        else:
            mid += 1

    return low, high

def find_kth_element(arr: List[int], k: int) -> int:
    """Find the k-th element in the array using a three-way partitioning method."""
    def find_kth_recursive(arr: List[int], k: int, low: int, high: int) -> int:
        left, right = three_way_partition(arr, low, high)
        
        if k < left:
            return find_kth_recursive(arr, k, low, left - 1)
        elif k > right:
            return find_kth_recursive(arr, k, right + 1, high)
        else:
            return arr[k]

    return find_kth_recursive(arr, k, 0, len(arr) - 1)

def process_input(input_str: str) -> Tuple[List[int], int]:
    """Process the input string and return the list of integers and the index k."""
    lines = input_str.strip().split('\n')
    arr = parse_integers(lines[1])
    k = int(lines[2])
    return arr, k

sample_input = """
11
2 36 5 21 8 13 11 20 5 4 1
8
"""

arr, k = process_input(sample_input)
result = find_kth_element(arr, k - 1)
print(result)

25 Partial Sort

Given: A positive integer $n≤10^5$ and an array A[1..n] of integers from $−10^5$ to $10^5$, a positive integer k≤1000.

Return: The k smallest elements of a sorted array A.

25.1 Sample Dataset

10
4 -6 7 8 -9 100 12 13 56 17
3

25.2 Sample Output

-9 -6 4

25.3 Solution

from typing import List

def parse_integers(line: str) -> List[int]:
    """Parse a line of space-separated integers into a list of integers."""
    return [int(num) for num in line.split()]

def heapify_up(heap: List[int], i: int) -> None:
    """Maintain heap property by moving an element up the heap."""
    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] < heap[i]:
            heap[parent], heap[i] = heap[i], heap[parent]
            i = parent
        else:
            break

def build_max_heap(arr: List[int]) -> List[int]:
    """Build a max heap from an array."""
    heap = []
    for x in arr:
        heap.append(x)
        heapify_up(heap, len(heap) - 1)
    return heap

def sift_down(heap: List[int], start: int, end: int) -> None:
    """Maintain heap property by moving an element down the heap."""
    root = start
    while root * 2 + 1 <= end:
        left = root * 2 + 1
        right = left + 1
        swap = root
        if heap[swap] < heap[left]:
            swap = left
        if right <= end and heap[swap] < heap[right]:
            swap = right
        if swap != root:
            heap[root], heap[swap] = heap[swap], heap[root]
            root = swap
        else:
            return

def heap_sort(arr: List[int]) -> List[int]:
    """Sort an array using heap sort algorithm."""
    heap = build_max_heap(arr)
    for i in range(len(heap) - 1, 0, -1):
        heap[0], heap[i] = heap[i], heap[0]
        sift_down(heap, 0, i - 1)
    return heap

def partial_sort(arr: List[int], k: int) -> List[int]:
    """Find and sort the k smallest elements in the array."""
    heap = build_max_heap(arr[:k])
    for x in arr[k:]:
        if x < heap[0]:
            heap[0] = x
            sift_down(heap, 0, k - 1)
    return heap_sort(heap)

# Sample input processing
sample_input = """
10
4 -6 7 8 -9 100 12 13 56 17
3
"""

_, arr_str, k_str = sample_input.strip().split("\n")
arr = parse_integers(arr_str)
k = int(k_str)

# Perform partial sort and print result
result = partial_sort(arr, k)
print(*result)

26 Topological Sorting

Given: A simple directed acyclic graph with $n≤10^3$ vertices in the edge list format.

Return: A topological sorting (i.e., a permutation of vertices) of the graph.

26.1 Sample Dataset

26.2 Sample Output

4 3 1 2

26.3 Solution

from typing import List, Iterator, Dict, Union, Set
from collections import defaultdict
from io import StringIO

GraphNode = Union[int, Dict[str, int]]
Graph = Dict[int, List[GraphNode]]

def parse_integers(line: str) -> List[int]:
    return [int(num) for num in line.split()]

def read_non_empty_line(input_iterator: Iterator[str]) -> str:
    line = next(input_iterator).strip()
    while not line:
        line = next(input_iterator).strip()
    return line

def parse_graph(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Graph:
    vertex_count, edge_count = parse_integers(read_non_empty_line(input_iterator))
    
    adjacency_list: Graph = {vertex: [] for vertex in range(1, vertex_count + 1)}
    
    for _ in range(edge_count):
        edge_data = parse_integers(read_non_empty_line(input_iterator))
        if is_weighted:
            source, destination, weight = edge_data
            adjacency_list[source].append({"node": destination, "weight": weight})
            if not is_directed:
                adjacency_list[destination].append({"node": source, "weight": weight})
        else:
            source, destination = edge_data
            adjacency_list[source].append(destination)
            if not is_directed:
                adjacency_list[destination].append(source)

    return adjacency_list

def get_all_graph_nodes(graph: Graph) -> Set[int]:
    nodes = set()
    for node, neighbors in graph.items():
        nodes.add(node)
        for neighbor in neighbors:
            if isinstance(neighbor, dict):
                nodes.add(neighbor["node"])
            else:
                nodes.add(neighbor)
    return nodes

def topological_sort(graph: Graph) -> List[int]:
    def dfs_topological(vertex: int, visited: Dict[int, bool], stack: List[int]):
        visited[vertex] = True
        for neighbor in graph[vertex]:
            neighbor_node = neighbor["node"] if isinstance(neighbor, dict) else neighbor
            if not visited[neighbor_node]:
                dfs_topological(neighbor_node, visited, stack)
        stack.append(vertex)

    visited = defaultdict(bool)
    stack = []
    for node in get_all_graph_nodes(graph):
        if not visited[node]:
            dfs_topological(node, visited, stack)

    return stack[::-1]

# Sample input processing
sample_input = """
4 5
1 2
3 1
3 2
4 3
4 2
"""

input_iterator = iter(StringIO(sample_input.strip()).readlines())
graph = parse_graph(input_iterator, is_directed=True)
sorted_nodes = topological_sort(graph)
print(*sorted_nodes)

27 Hamiltonian Path in DAG

A Hamiltonian path is a path in a graph that visits each vertex exactly once. Checking whether a graph contains a Hamiltonian path is a well-known hard problem. At the same time it is easy to perform such a check if a given graph is a DAG.

Given: A positive integer k≤20 and k simple directed acyclic graphs in the edge list format with at most $10^3$ vertices each.

Return: For each graph, if it contains a Hamiltonian path output”1”followed by a Hamiltonian path (i.e., a list of vertices), otherwise output”-1”.

27.1 Sample Dataset

27.2 Sample Output

1 1 2 3
-1

27.3 Solution

from typing import List, Iterator, Dict, Set
from collections import defaultdict
from io import StringIO

Graph = Dict[int, List[int]]

def parse_integers(line: str) -> List[int]:
    return list(map(int, line.split()))

def read_non_empty_line(input_iterator: Iterator[str]) -> str:
    return next(line for line in input_iterator if line.strip())

def parse_graph(input_iterator: Iterator[str], is_directed: bool = False) -> Graph:
    vertex_count, edge_count = parse_integers(read_non_empty_line(input_iterator))
    
    adjacency_list: Graph = defaultdict(list)
    
    for _ in range(edge_count):
        source, destination = parse_integers(read_non_empty_line(input_iterator))
        adjacency_list[source].append(destination)
        if not is_directed:
            adjacency_list[destination].append(source)

    return adjacency_list

def parse_multiple_graphs(input_iterator: Iterator[str], is_directed: bool = False) -> List[Graph]:
    num_cases = int(read_non_empty_line(input_iterator))
    return [parse_graph(input_iterator, is_directed) for _ in range(num_cases)]

def graph_nodes(graph: Graph) -> Set[int]:
    return set(graph.keys()) | set.union(*(set(val) for val in graph.values()))

def topological_sort(graph: Graph) -> List[int]:
    def dfs(node: int, visited: Set[int], stack: List[int]):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor, visited, stack)
        stack.append(node)

    visited: Set[int] = set()
    stack: List[int] = []
    for node in graph_nodes(graph):
        if node not in visited:
            dfs(node, visited, stack)

    return stack[::-1]

def hdag(graph: Graph) -> List[int]:
    sorted_nodes = topological_sort(graph)
    for a, b in zip(sorted_nodes, sorted_nodes[1:]):
        if b not in graph[a]:
            return [-1]
    return [1] + sorted_nodes

sample_input = """
2

3 3
1 2
2 3
1 3

4 3
4 3
3 2
4 1
"""

input_iterator = iter(StringIO(sample_input.strip()).readlines())
graphs = parse_multiple_graphs(input_iterator, is_directed=True)
for graph in graphs:
    print(*hdag(graph))

28 Negative Weight Cycle

The task is to use Bellman-Ford algorithm to check whether a given graph contains a cycle of negative weight.

Given: A positive integer k≤20 and k simple directed graphs with integer edge weights from $−10^3$ to $10^3$ and $n≤10^3$ vertices in the edge list format.

Return: For each graph, output”1”if it contains a negative weight cycle and”-1”otherwise.

28.1 Sample Dataset

28.2 Sample Output

-1 1

28.3 Solution

from io import StringIO
from typing import List, Dict, Union, Iterator
from collections import deque

def parse_integers(line: str) -> List[int]:
    return [int(num) for num in line.split()]

def read_non_empty_line(input_iterator: Iterator[str]) -> str:
    line = next(input_iterator).strip()
    while not line:
        line = next(input_iterator).strip()
    return line

def parse_graph(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]:
    node_count, edge_count = parse_integers(read_non_empty_line(input_iterator))
    
    adjacency_list = {node: [] for node in range(1, node_count + 1)}
    
    for _ in range(edge_count):
        edge_data = parse_integers(read_non_empty_line(input_iterator))
        if is_weighted:
            source, target, weight = edge_data
            adjacency_list[source].append({"node": target, "weight": weight})
            if not is_directed:
                adjacency_list[target].append({"node": source, "weight": weight})
        else:
            source, target = edge_data
            adjacency_list[source].append(target)
            if not is_directed:
                adjacency_list[target].append(source)

    return adjacency_list

def parse_multiple_graphs(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> List[Dict[int, List[Union[int, Dict[str, int]]]]]:
    test_case_count = int(read_non_empty_line(input_iterator))
    return [parse_graph(input_iterator, is_directed, is_weighted) for _ in range(test_case_count)]

def count_edges(graph):
    edge_count = 0
    for _, neighbors in graph.items():
        for _ in neighbors:
            edge_count += 1
    return edge_count

def get_all_nodes(graph):
    source_nodes = list(graph.keys())
    target_nodes = [neighbor["node"] for neighbors in graph.values() for neighbor in neighbors]
    return set(source_nodes) | set(target_nodes)

def detect_negative_weight_cycle(graph):
    distances = {node: 10**20 for node in get_all_nodes(graph)}
    distances[1] = 0
    for _ in range(count_edges(graph) - 1):
        for source, neighbors in graph.items():
            for neighbor in neighbors:
                distances[neighbor["node"]] = min(distances[source] + neighbor["weight"], distances[neighbor["node"]])
    for source, neighbors in graph.items():
        for neighbor in neighbors:
            if distances[source] + neighbor["weight"] < distances[neighbor["node"]]:
                return 1
    return -1

sample_input = """
2

4 5
1 4 4
4 2 3
2 3 1
3 1 6
2 1 -7

3 4
1 2 -8
2 3 20
3 1 -1
3 2 -30
"""

input_iterator = iter(StringIO(sample_input.strip()).readlines())
graphs = parse_multiple_graphs(input_iterator, is_directed=True, is_weighted=True)
print(*[detect_negative_weight_cycle(graph) for graph in graphs])

29 Quick Sort

Comparing the algorithms for sorting and “Median” finding we notice that, beyond the common divide-and-conquer philosophy and structure, they are exact opposites. “Merge Sort” splits the array in two in the most convenient way (first half, second half), without any regard to the magnitudes of the elements in each half; but then it works hard to put the sorted subarrays together. In contrast, the median algorithm is careful about its splitting (smaller numbers first, then the larger ones), but its work ends with the recursive call.

Quick sort is a sorting algorithm that splits the array in exactly the same way as the median algorithm; and once the subarrays are sorted, by two recursive calls, there is nothing more to do. Its worst-case performance is $Θ(n2)$, like that of median-finding. But it can be proved that its average case is $O(n \log ⁡n)$; furthermore, empirically it outperforms other sorting algorithms. This has made quicksort a favorite in many applications— for instance, it is the basis of the code by which really enormous files are sorted.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

Given: A positive integer $n≤10^5$ and an array A[1..n] of integers from $−10^5$ to $10^5$.

Return: A sorted array A[1..n].

29.1 Sample Dataset

7
5 -2 4 7 8 -10 11

29.2 Sample Output

-10 -2 4 5 7 8 11

29.3 Solution

from typing import List

def parse_integers(input_line: str) -> List[int]:
    return [int(number) for number in input_line.split()]

def three_way_partition(array: List[int], start: int = None, end: int = None) -> tuple:
    if start is None:
        start = 0
    if end is None:
        end = len(array) - 1
    pivot = array[start]
    current = start
    while current <= end:
        if array[current] < pivot:
            array[current], array[start] = array[start], array[current]
            current += 1
            start += 1
        elif array[current] > pivot:
            array[current], array[end] = array[end], array[current]
            end -= 1
        else:
            current += 1
    return start, end

def quick_sort(array: List[int]):
    def quick_sort_recursive(array: List[int], start: int, end: int):
        if start < end:
            partition_start, partition_end = three_way_partition(array, start, end)
            if start < partition_start:
                quick_sort_recursive(array, start, partition_start - 1)
            if end > partition_end:
                quick_sort_recursive(array, partition_end + 1, end)

    quick_sort_recursive(array, 0, len(array) - 1)

sample_input = """
7
5 -2 4 7 8 -10 11
"""

_, input_numbers = sample_input.strip().split("\n")
numbers = parse_integers(input_numbers)  # Convert the input string to a list of integers
quick_sort(numbers)
print(*numbers)

30 Strongly Connected Components

Given: A simple directed graph with $n≤10^3$ vertices in the edge list format.

Return: The number of strongly connected components in the graph.

30.1 Sample Dataset

30.2 Sample Output

30.3 Solution

from collections import defaultdict
from typing import List, Dict, Set, Union, Iterator
from io import StringIO

Graph = Dict[int, List[Union[int, Dict[str, int]]]]

def parse_integers(line: str) -> List[int]:
    return [int(num) for num in line.split()]

def read_non_empty_line(input_iterator: Iterator[str]) -> str:
    return next(line.strip() for line in input_iterator if line.strip())

def parse_graph(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Graph:
    node_count, edge_count = parse_integers(read_non_empty_line(input_iterator))
    
    graph = {n: [] for n in range(1, node_count + 1)}
    
    for _ in range(edge_count):
        edge = parse_integers(read_non_empty_line(input_iterator))
        if is_weighted:
            source, target, weight = edge
            graph[source].append({"n": target, "w": weight})
            if not is_directed:
                graph[target].append({"n": source, "w": weight})
        else:
            source, target = edge
            graph[source].append(target)
            if not is_directed:
                graph[target].append(source)

    return graph

def get_graph_nodes(graph: Graph) -> Set[int]:
    return set(graph.keys())

def topological_sort(graph: Graph) -> List[int]:
    def dfs(node: int, visited: Set[int], stack: List[int]):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor, visited, stack)
        stack.append(node)

    visited: Set[int] = set()
    stack: List[int] = []
    for node in get_graph_nodes(graph):
        if node not in visited:
            dfs(node, visited, stack)

    return stack[::-1]

def find_component(start_node: int, graph: Graph) -> Set[int]:
    def visit(node: int, visited: Set[int]) -> Set[int]:
        visited.add(node)
        for neighbor in set(graph[node]) - visited:
            visit(neighbor, visited)
        return visited

    return visit(start_node, set())

def reverse_graph(graph: Graph) -> Graph:
    reversed_graph = defaultdict(list)
    for node in graph:
        for child in graph[node]:
            reversed_graph[child].append(node)
    return reversed_graph

def strongly_connected_components(graph: Graph) -> Iterator[Set[int]]:
    order = topological_sort(graph)
    reversed_graph = reverse_graph(graph)
    while order:
        node = order.pop(0)
        component = find_component(node, reversed_graph)
        order = [x for x in order if x not in component]
        for key in reversed_graph.keys():
            reversed_graph[key] = [n for n in reversed_graph[key] if n not in component]
        yield component

sample_input = """
6 7
4 1
1 2
2 4
5 6
3 2
5 3
3 5
"""

input_iterator = iter(StringIO(sample_input.strip()).readlines())
graph = parse_graph(input_iterator, is_directed=True)
print(len(list(strongly_connected_components(graph))))

31 2-Satisfiability

In the 2SAT problem, you are given a set of clauses, where each clause is the dis-junction (OR) of two literals (a literal is a Boolean variable or the negation of a Boolean variable). You are looking for a way to assign a value true or false to each of the variables so that all clauses are satisfied — that is, there is at least one true literal in each clause. For example, here’s an instance of 2SAT:

\[(x1 \lor \bar x2 \land (\bar x1 \lor \bar x3) \land (x1 \lor x2) \land (\bar x3 \lor x4)\land(\bar x1 \lor x4).\]

This instance has a satisfying assignment: set x1, x2, x3, and x4 to true, false, false, and true, respectively.

Are there other satisfying truth assignments of this 2SAT formula? If so, find them all.
Give an instance of 2SAT with four variables, and with no satisfying assignment.

The purpose of this problem is to lead you to a way of solving 2SAT efficiently by reducing it to the problem of finding the strongly connected components of a directed graph. Given an instance I of 2SAT with nn variables and mm clauses, construct a directed graph $GI=(V,E)$ as follows.

$GI$ has $2n$ nodes, one for each variable and its negation.
$GI$ has $2m$ edges: for each clause ($α∨β)$ of I (where $α,β$ are literals), $GI$ has an edge from the negation of $α$ to $β$, and one from the negation of $β$ to $α$.

Note that the clause $(α∨β)$ is equivalent to either of the implications $\bar α⇒β$ or $\bar β⇒α$. In this sense, $GI$ records all implications in I.

Carry out this construction for the instance of 2SAT given above, and for the instance you constructed in 2.
Show that if $GI$ has a strongly connected component containing both $x$ and $\bar x$ for some variable $x$, then I has no satisfying assignment.
Now show the converse of 4: namely, that if none of $GI$’s strongly connected components contain both a literal and its negation, then the instance I must be satisfiable. (Hint: Assign values to the variables as follows: repeatedly pick a sink strongly connected component of $GI$. Assign value true to all literals in the sink, assign false to their negations, and delete all of these. Show that this ends up discovering a satisfying assignment.)
Conclude that there is a linear-time algorithm for solving 2SAT.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

Given: A positive integer $k≤20$ and k 2SAT formulas represented as follows. The first line gives the number of variables $n≤10^3$ and the number of clauses $m≤10^4$, each of the following mm lines gives a clause of length 2 by specifying two different literals: e.g., a clause $(x3 ∨ \bar x5)$ is given by 3 -5.

Return: For each formula, output 0 if it cannot be satisfied or 11 followed by a satisfying assignment otherwise.

31.1 Sample Dataset

31.2 Sample Output

0
1 1 -2 3

31.3 Solution

import sys
from collections import defaultdict
from io import StringIO

def parse_integers(line):
    return list(map(int, line.split()))

class RecursionLimitManager:
    def __init__(self, new_limit):
        self.new_limit = new_limit

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.new_limit)

    def __exit__(self, exc_type, exc_value, traceback):
        sys.setrecursionlimit(self.old_limit)

def reverse_graph(original_graph):
    reversed_graph = defaultdict(list)
    for node in original_graph:
        for neighbor in original_graph[node]:
            reversed_graph[neighbor].append(node)
    return reversed_graph
    
def find_strongly_connected_components(graph):
    node_order = topological_sort(graph)
    reversed_graph = reverse_graph(graph)
    while node_order:
        start_node = node_order.pop(0)
        component = find_component(start_node, reversed_graph)
        node_order = [node for node in node_order if node not in component]
        for key in reversed_graph.keys():
            reversed_graph[key] = [node for node in reversed_graph[key] if node not in component]
        yield component

def find_component_index(node, components):
    for index, component in enumerate(components):
        if node in component:
            return index
            
def condense_graph(original_graph, components):
    condensed_graph = {}
    for index, component in enumerate(components):
        condensed_graph[index] = set(
            [
                find_component_index(neighbor, components)
                for node in component
                for neighbor in original_graph[node]
                if neighbor not in component
            ]
        )
    return condensed_graph

def topological_sort(graph):
    def depth_first_search(node, visited_nodes, node_stack):
        visited_nodes[node] = True
        for neighbor in graph[node]:
            if not visited_nodes[neighbor]:
                depth_first_search(neighbor, visited_nodes, node_stack)
        node_stack.append(node)

    visited_nodes = defaultdict(bool)
    node_stack = []
    for node in get_graph_nodes(graph):
        if not visited_nodes[node]:
            depth_first_search(node, visited_nodes, node_stack)

    return node_stack[::-1]

def parse_2sat_instances(input_handle):
    instance_count = int(next(input_handle))
    for _ in range(instance_count):
        yield parse_2sat_instance(input_handle)

def parse_2sat_instance(input_handle):
    info = next(input_handle)
    if info == "\n":
        info = next(input_handle)
    variable_count, clause_count = parse_integers(info)
    clauses = [next(input_handle) for _ in range(clause_count)]
    implication_graph = {}

    for variable in range(1, variable_count + 1):
        implication_graph[variable] = list()
        implication_graph[-variable] = list()

    for clause in clauses:
        literal1, literal2 = parse_integers(clause)
        implication_graph[-literal1].append(literal2)
        implication_graph[-literal2].append(literal1)

    return implication_graph

def solve_2sat(implication_graph):
    components = list(find_strongly_connected_components(implication_graph))
    condensed_graph = condense_graph(implication_graph, components)

    for component_index in topological_sort(condensed_graph):
        for literal in components[component_index]:
            if -literal in components[component_index]:
                return 0, []

    assignment = []
    for component_index in reversed(topological_sort(condensed_graph)):
        for literal in components[component_index]:
            if literal not in assignment and -literal not in assignment:
                assignment.append(literal)

    return 1, sorted(assignment, key=lambda x: abs(x))

sample_input = """
2

2 4
1 2
-1 2
1 -2
-1 -2

3 4
1 2
2 3
-1 -2
-2 -3
"""

with RecursionLimitManager(5000):
    input_iterator = iter(StringIO(sample_input.strip()).readlines())
    implication_graphs = parse_2sat_instances(input_iterator)
    for implication_graph in implication_graphs:
        is_satisfiable, satisfying_assignment = solve_2sat(implication_graph)
        print(is_satisfiable, *satisfying_assignment)

32 General Sink

Given: A positive integer k≤20 and k simple directed graphs with at most $10^3$ vertices and $2⋅10^3$ edges each in the edge list format.

Return: For each graph, output a vertex from which all other vertices are reachable (if such a vertex exists) and”-1”otherwise.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

32.1 Sample Dataset

32.2 Sample Output

3 -1

32.3 Solution

from collections import defaultdict
from typing import List, Dict, Union, Iterator
from io import StringIO

Graph = Dict[int, List[Union[int, Dict[str, int]]]]

def parse_integers(line: str) -> List[int]:
    return [int(num) for num in line.split()]

def read_non_empty_line(input_iterator: Iterator[str]) -> str:
    return next(line.strip() for line in input_iterator if line.strip())

def parse_graph(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Graph:
    node_count, edge_count = parse_integers(read_non_empty_line(input_iterator))
    
    graph = {node: [] for node in range(1, node_count + 1)}
    
    for _ in range(edge_count):
        edge = parse_integers(read_non_empty_line(input_iterator))
        if is_weighted:
            source, target, weight = edge
            graph[source].append({"n": target, "w": weight})
            if not is_directed:
                graph[target].append({"n": source, "w": weight})
        else:
            source, target = edge
            graph[source].append(target)
            if not is_directed:
                graph[target].append(source)

    return graph

def parse_multiple_graphs(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> List[Graph]:
    test_case_count = int(read_non_empty_line(input_iterator))
    return [parse_graph(input_iterator, is_directed, is_weighted) for _ in range(test_case_count)]

def bfs(graph: Graph, start_node=1) -> List[int]:
    node_count = len(graph)
    distances = [-1 for _ in range(node_count + 1)]
    distances[start_node] = 0
    queue = [start_node]
    
    while queue:
        current_node = queue.pop(0)
        for neighbor in graph[current_node]:
            if distances[neighbor] == -1:
                queue.append(neighbor)
                distances[neighbor] = distances[current_node] + 1
    return distances[1:]

def find_good_start_node(graph: Graph) -> int:
    for node in graph:
        distances = bfs(graph, node)
        all_nodes_reachable = [distance >= 0 for distance in distances]
        if all(all_nodes_reachable):
            return node
    return -1

sample_input = """
2

3 2
3 2
2 1

3 2
3 2
1 2
"""

input_iterator = iter(StringIO(sample_input.strip()).readlines())

graphs = parse_multiple_graphs(input_iterator, is_directed=True)
print(*[find_good_start_node(g) for g in graphs])

33 Semi-Connected Graph

A directed graph is semi-connected if for all pairs of vertices i,j there is either a path from i to j or a path from j to i.

Given: A positive integer k≤20 and k simple directed graphs with at most $10^3$ vertices each in the edge list format.

Return: For each graph, output”1”if the graph is semi-connected and”-1”otherwise.

33.1 Sample Dataset

33.2 Sample Output

1 -1

33.3 Solution

import sys
from collections import defaultdict

def parse_integers(string):
    return list(map(int, string.split()))

def create_graph(input_stream, is_directed=False, is_weighted=False):
    while True:
        try:
            graph_info = next(input_stream).strip()
            if graph_info:
                break
        except StopIteration:
            return None

    try:
        vertex_count, edge_count = parse_integers(graph_info)
    except ValueError:
        return None

    edge_list = []
    for _ in range(edge_count):
        try:
            edge = next(input_stream).strip()
            if edge:
                edge_list.append(edge)
        except StopIteration:
            break

    adjacency_list = {v: [] for v in range(1, vertex_count + 1)}

    for edge in edge_list:
        if is_weighted:
            source, target, weight = parse_integers(edge)
            adjacency_list[source].append({"vertex": target, "weight": weight})
            if not is_directed:
                adjacency_list[target].append({"vertex": source, "weight": weight})
        else:
            source, target = parse_integers(edge)
            adjacency_list[source].append(target)
            if not is_directed:
                adjacency_list[target].append(source)

    return adjacency_list

def parse_multiple_graphs(input_stream, is_directed=False, is_weighted=False):
    try:
        graph_count = int(next(input_stream).strip())
    except (StopIteration, ValueError):
        return []

    graph_list = []
    for _ in range(graph_count):
        graph = create_graph(input_stream, is_directed=is_directed, is_weighted=is_weighted)
        if graph is not None:
            graph_list.append(graph)
        else:
            break
    return graph_list

def reverse_graph(graph):
    reversed_graph = defaultdict(list)
    for vertex in graph:
        for neighbor in graph[vertex]:
            reversed_graph[neighbor].append(vertex)
    return reversed_graph

def get_all_vertices(graph):
    vertex_set = set()
    for vertex, neighbors in graph.items():
        vertex_set.add(vertex)
        vertex_set.update(neighbors)
    return vertex_set

def topological_sort(graph):
    def dfs(vertex, visited, stack):
        visited[vertex] = True
        for neighbor in graph[vertex]:
            if not visited[neighbor]:
                dfs(neighbor, visited, stack)
        stack.append(vertex)

    visited = defaultdict(bool)
    stack = []
    for vertex in get_all_vertices(graph):
        if not visited[vertex]:
            dfs(vertex, visited, stack)

    return stack[::-1]

def find_connected_component(start_vertex, graph):
    def dfs(vertex, visited):
        visited.add(vertex)
        for neighbor in set(graph[vertex]) - visited:
            dfs(neighbor, visited)
        return visited

    return dfs(start_vertex, set())

def strongly_connected_components(graph):
    vertex_order = topological_sort(graph)
    reversed_graph = reverse_graph(graph)
    while vertex_order:
        start_vertex = vertex_order.pop(0)
        component = find_connected_component(start_vertex, reversed_graph)
        vertex_order = [v for v in vertex_order if v not in component]
        for vertex in reversed_graph.keys():
            reversed_graph[vertex] = [v for v in reversed_graph[vertex] if v not in component]
        yield component

def hamiltonian_dag(graph):
    sorted_vertices = topological_sort(graph)
    for v1, v2 in zip(sorted_vertices, sorted_vertices[1:]):
        if v2 not in graph[v1]:
            return [-1]
    return [1] + sorted_vertices

def find_component_index(vertex, components):
    for index, component in enumerate(components):
        if vertex in component:
            return index

def condense_graph(graph, components):
    condensed_graph = {}
    for i, component in enumerate(components):
        condensed_graph[i] = set(
            find_component_index(neighbor, components)
            for vertex in component
            for neighbor in graph[vertex]
            if neighbor not in component
        )
    return condensed_graph

def is_semi_connected(graph):
    components = list(strongly_connected_components(graph))
    condensed_graph = condense_graph(graph, components)
    return -1 if hamiltonian_dag(condensed_graph) == [-1] else 1

sample_input = """
2

3 2
3 2
2 1

3 2
3 2
1 2
"""

input_lines = sample_input.strip().split("\n")
input_iterator = iter(input_lines)
graphs = parse_multiple_graphs(input_iterator, is_directed=True)
print(*[is_semi_connected(g) for g in graphs])

34 Shortest Paths in DAG

There are two subclasses of graphs that automatically exclude the possibility of negative cycles: graphs without negative edges, and graphs without cycles. We already know how to efficiently handle the former (see the problem “Negative Weight Cycle”). We will now see how the single-source shortest-path problem can be solved in just linear time on directed acyclic graphs.

As before, we need to perform a sequence of updates (recall Bellman-Ford algorithm) that includes every shortest path as a subsequence. The key source of efficiency is that

In any path of a DAG, the vertices appear in increasing linearized order.

Therefore, it is enough to linearize (that is, topologically sort) the DAG by depth-first search, and then visit the vertices in sorted order, updating the edges out of each. The algorithm is given below.

Notice that our scheme doesn’t require edges to be positive. In particular, we can find longest paths in a DAG by the same algorithm: just negate all edge lengths.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

Given: A weighted DAG with integer edge weights from $−10^3$ to $10^3$ and $n≤10^5$ vertices in the edge list format.

Return: An array D[1..n] where D[i] is the length of a shortest path from the vertex 1 to the vertex i (D[1]=0. If i is not reachable from 1 set D[i] to x.

34.1 Sample Dataset

34.2 Sample Output

0 x -4 -2 -3

34.3 Solution

from math import inf
from typing import List, Dict, Set, Iterator, Union, Optional
from collections import defaultdict

def parse_integers(line: str) -> List[int]:
    return list(map(int, line.split()))

def create_graph(input_stream: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]:
    graph_info = next(input_stream)
    if graph_info == "\n":
        graph_info = next(input_stream)
    
    vertex_count, edge_count = parse_integers(graph_info)
    edge_list = [next(input_stream) for _ in range(edge_count)]
    adjacency_list: Dict[int, List[Union[int, Dict[str, int]]]] = {v: [] for v in range(1, vertex_count + 1)}

    for edge in edge_list:
        if is_weighted:
            source, target, weight = parse_integers(edge)
            adjacency_list[source].append({"vertex": target, "weight": weight})
            if not is_directed:
                adjacency_list[target].append({"vertex": source, "weight": weight})
        else:
            source, target = parse_integers(edge)
            adjacency_list[source].append(target)
            if not is_directed:
                adjacency_list[target].append(source)

    return adjacency_list

def get_all_vertices(graph: Dict[int, List[Union[int, Dict[str, int]]]]) -> Set[int]:
    vertex_set: Set[int] = set()
    for vertex, neighbors in graph.items():
        vertex_set.add(vertex)
        vertex_set.update([n if isinstance(n, int) else n["vertex"] for n in neighbors])
    return vertex_set

def topological_sort(graph: Dict[int, List[int]]) -> List[int]:
    def depth_first_search(vertex: int, visited: Dict[int, bool], stack: List[int]) -> None:
        visited[vertex] = True
        for neighbor in graph[vertex]:
            if not visited[neighbor]:
                depth_first_search(neighbor, visited, stack)
        stack.append(vertex)

    visited: Dict[int, bool] = defaultdict(bool)
    stack: List[int] = []
    for vertex in get_all_vertices(graph):
        if not visited[vertex]:
            depth_first_search(vertex, visited, stack)

    return stack[::-1]

def simplify_graph(graph: Dict[int, List[Dict[str, int]]]) -> Dict[int, List[int]]:
    return {k: [x["vertex"] for x in v] for k, v in graph.items()}

def shortest_distances_acyclic_graph(graph: Dict[int, List[Dict[str, int]]]) -> List[Union[str, int]]:
    vertex_count = len(graph)
    distances = [inf for _ in range(vertex_count + 1)]
    distances[1] = 0
    topological_order = topological_sort(simplify_graph(graph))
    
    for current_vertex in topological_order:
        seen_vertices = set()
        for edge in reversed(graph[current_vertex]):
            neighbor = edge["vertex"]
            if neighbor not in seen_vertices:
                seen_vertices.add(neighbor)
                if distances[current_vertex] + edge["weight"] < distances[neighbor]:
                    distances[neighbor] = distances[current_vertex] + edge["weight"]
    
    return ["x" if d == inf else d for d in distances[1:]]

sample_input = """
5 6
2 3 4
4 3 -2
1 4 1
1 5 -3
2 4 -2
5 4 1
"""

input_lines: List[str] = sample_input.strip().split("\n")
input_iterator: Iterator[str] = iter(input_lines)
result = shortest_distances_acyclic_graph(create_graph(input_iterator, is_directed=True, is_weighted=True))
print(*result)

--- title: "Rosalind Algorithmic Heights 문제풀이" author: "Taeyoon Kim" categories: [Python, Rosalind, Bioinformatics, Tip] draft: false date: "2024-09-28" date-modified: last-modified --- ![](Rosalind_algorithmicHeights.png){width=100% fig-align="center"} Dasgupta, Papadimitriou, Vazirani 의 책 "[알고리즘](https://github.com/eherbold/berkeleytextbooks/blob/master/Algorithms%20-%20Sanjoy%20Dasgupta%2C%20Christos%20H.%20Papadimitriou%2C%20and%20Umesh%20V.%20Vazirani.pdf)" 에 포함된 연습문제의 모음입니다. [Rosalind](https://rosalind.info/) 는 [프로젝트 오일러](http://projecteuler.net/), [구글 코드 잼](http://code.google.com/codejam) 에서 영감을 얻었습니다. 이 프로젝트의 이름은 DNA 이중나선을 발견하는 데 기여한 [로잘린드 프랭클린](http://en.wikipedia.org/wiki/Rosalind_Franklin) 에서 따왔습니다. Rosalind 는 프로그래밍 실력을 키우고자 하는 생물학자와 분자생물학의 계산 문제를 접해본 적이 없는 프로그래머들에게 도움이 될 것입니다. # Fibonacci Numbers ## Problem The Fibonacci numbers $0,1,1,2,3,5,8,13,21,34,…$ are generated by the simple rule. Given: A positive integer $n≤25$. Return: The value of Fn. Source: [Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006](https://rosalind.info/glossary/algo-algorithms-by-dasgupta-papadimitriou-vazirani-mcgraw-hill-2006/). ## Sample Dataset ``` 6 ``` ## Sample Output ``` 8 ``` ## Solution ```python def fibonacci(n: int) -> int: fib: list[int] = [0] * (n + 1) fib[1] = 1 for i in range(2, n + 1): fib[i] = fib[i - 1] + fib[i - 2] return fib[n] n: int = 6 print(f"피보나치 수열의 {n}번째 항: {fibonacci(n)}") ``` 아주 큰수의 피보나치 수열을 계산하는 경우에는 다음 코드. ```python import gmpy2 from gmpy2 import mpz def fibonacci_gmpy2(n: int) -> mpz: a: mpz = gmpy2.mpz(0) b: mpz = gmpy2.mpz(1) for _ in range(n): a, b = b, a + b return a # 예제 사용 n: int = 60000 result: mpz = fibonacci_gmpy2(n) print(f"피보나치 수열의 {n}번째 항:") print(result) print(f"자릿수: {len(str(result))}") ``` # Binary Search Binary search is the ultimate [divide-and-conquer](https://rosalind.info/glossary/algo-divide-and-conquer/) algorithm. To find a key k in a large file containing keys A[1..n] in sorted order, we first compare k with A[n/2], and depending on the result we recurse either on the first half of the file, A[1..n/2], or on the second half, A[n/2+1..n]. The recurrence now is $T(n)=T(n/2)+O(1)$. Plugging into the [master theorem](https://rosalind.info/glossary/algo-master-theorem/) with $(a=1,b=2,d=0)$ we get the familiar solution: a running time of just $O(logn)$. Source: [Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006](https://rosalind.info/glossary/algo-algorithms-by-dasgupta-papadimitriou-vazirani-mcgraw-hill-2006/). The problem is to find a given set of keys in a given array. Given: Two positive integers $n≤10^5$ and $m≤10^5$, a sorted [array](https://rosalind.info/glossary/algo-array/) A[1..n] of integers from $−10^5$ to $10^5$ and a list of mm integers $−10^5≤k1,k2,…,km≤10^5$. Return: For each $k_i$, output an index $1≤j≤n$ s.t. $A[j]=k_i$ or"-1"if there is no such index. ## Sample Dataset ``` 5 6 10 20 30 40 50 40 10 35 15 40 20 ``` ## Sample Output ``` 4 1 -1 -1 4 2 ``` ## Solution ```python from typing import List, Tuple def binary_search(arr: List[int], target: int) -> int: low, high = 0, len(arr) - 1 while low <= high: mid = (low + high) // 2 if arr[mid] == target: return mid + 1 # Adding 1 to convert from 0-based to 1-based indexing elif arr[mid] < target: low = mid + 1 else: high = mid - 1 return -1 # Target not found def parse_input(input_str: str) -> Tuple[int, int, List[int], List[int]]: lines = input_str.strip().split("\n") n = int(lines[0]) m = int(lines[1]) array = list(map(int, lines[2].split())) items = list(map(int, lines[3].split())) return n, m, array, items sample_input = """ 5 6 10 20 30 40 50 40 10 35 15 40 20 """ n, m, array, items = parse_input(sample_input) results: List[str] = [str(binary_search(array, item)) for item in items] print(' '.join(results)) ``` # Insertion Sort Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as [“Quick Sort”](https://rosalind.info/problems/qs/), [“Heap Sort”](https://rosalind.info/problems/hs/), or [“Merge Sort”](https://rosalind.info/problems/ms/). However, insertion sort provides several advantages: simple implementation, efficient for (quite) small data sets, O(1)O(1) extra space. When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort. Source: [Wikipedia](http://en.wikipedia.org/wiki/Insertion_sort) Although it is one of the elementary sorting algorithms with $O(n^2)$ worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead). For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead [divide-and-conquer](https://rosalind.info/glossary/algo-divide-and-conquer/) sorting algorithms, such as [“Merge Sort”](https://rosalind.info/problems/ms/) or [“Quick Sort”](https://rosalind.info/problems/qs/). Insertion sort is a simple algorithm with quadratic running time that builds the final sorted array one item at a time. Given: A positive integer $n≤10^3$ and an array A[1..n] of integers. Return: The number of swaps performed by insertion sort algorithm on A[1..n]. ## Sample Dataset ``` 6 6 10 4 5 1 2 ``` ## Sample Output ``` 12 ``` ## Solution ```python from typing import List def parse_input(input_str: str) -> List[int]: lines = input_str.strip().split("\n") n = int(lines[0]) # Get the number of elements array = list(map(int, lines[1].split())) return array def insertion_sort(array: List[int]) -> int: swaps = 0 for i in range(1, len(array)): key = array[i] j = i - 1 while j >= 0 and array[j] > key: array[j + 1] = array[j] swaps += 1 j -= 1 array[j + 1] = key return swaps # Sample input sample_input = """ 6 6 10 4 5 1 2 """ array: List[int] = parse_input(sample_input) swap_count: int = insertion_sort(array) print(f"{swap_count}") ``` # Degree Array In an undirected graph, the degree $d(u)$ of a vertex u is the number of neighbors u has, or equivalently, the number of edges incident upon it. Given: A [simple graph](https://rosalind.info/glossary/algo-simple-graph/) with $n≤10^3$ vertices in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/). Return: An array $D[1..n]$ where $D[i]$ is the degree of vertex i. ## Sample Dataset ``` 6 7 1 2 2 3 6 3 5 6 2 5 2 4 4 1 ``` ## Sample Output ``` 2 4 2 2 2 2 ``` ## Solution ```python from typing import List, Tuple def parse_input(input_str: str) -> Tuple[int, List[int]]: lines = input_str.strip().split("\n") nodes, edges = map(int, lines[0].split()) edge_list: List[int] = [] for line in lines[1:]: edge_list.extend(map(int, line.split())) return nodes, edge_list def calculate_degrees(nodes: int, edge_list: List[int]) -> List[int]: degrees: List[int] = [0] * nodes for node in edge_list: degrees[node - 1] += 1 return degrees # Sample input sample_input = """ 6 7 1 2 2 3 6 3 5 6 2 5 2 4 4 1 """ nodes: int edge_list: List[int] nodes, edge_list = parse_input(sample_input) degrees: List[int] = calculate_degrees(nodes, edge_list) print(" ".join(map(str, degrees))) ``` # Double-Degree Array Source: [Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006](https://rosalind.info/glossary/algo-algorithms-by-dasgupta-papadimitriou-vazirani-mcgraw-hill-2006/). Given: A [simple graph](https://rosalind.info/glossary/algo-simple-graph/) with $n≤10^3$ vertices in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/). Return: An array D[1..n] where D[i] is the sum of the degrees of $i$'s neighbors. ## Sample Dataset ``` 5 4 1 2 2 3 4 3 2 4 ``` ## Sample Output ``` 3 5 5 5 0 ``` ## Solution ```python from typing import List, Tuple, Dict def parse_input(input_str: str) -> Tuple[int, List[List[int]]]: lines = input_str.strip().split("\n") nodes, edges = map(int, lines[0].split()) edge_list: List[List[int]] = [] for line in lines[1:]: edge_list.append(list(map(int, line.split()))) return nodes, edge_list sample_input = """ 5 4 1 2 2 3 4 3 2 4 """ nodes: int edges_list: List[List[int]] nodes, edges_list = parse_input(sample_input) # Create an adjacency list nodes_neighbours: Dict[str, List[str]] = {str(i+1): [] for i in range(nodes)} for edge in edges_list: nodes_neighbours[str(edge[0])].append(str(edge[1])) nodes_neighbours[str(edge[1])].append(str(edge[0])) # Calculate and print the sum of neighbors' degrees for i in range(1, nodes + 1): sum_of_neighbors_degrees: int = sum(len(nodes_neighbours[str(neighbor)]) for neighbor in nodes_neighbours[str(i)]) print(sum_of_neighbors_degrees, end=" ") ``` # Majority Element An array A[1..n] is said to have a majority element if more than half of its entries are the same. Given: A positive integer k≤20, a positive integer $n≤10^4$, and k arrays of size $n$ containing positive integers not exceeding $10^5$. Return: For each array, output an element of this array occurring strictly more than $\frac{n}{2}$ times if such element exists, and"-1"otherwise. Source: [Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006](https://rosalind.info/glossary/algo-algorithms-by-dasgupta-papadimitriou-vazirani-mcgraw-hill-2006/). ## Sample Dataset ``` 4 8 5 5 5 5 5 5 5 5 8 7 7 7 1 7 3 7 7 1 6 5 10 100 1000 1 5 1 6 7 1 1 10 1 ``` ## Sample Output ``` 5 7 -1 -1 ``` ## Solution ```python from typing import List def string_to_int_list(string: str) -> List[int]: return list(map(int, string.split())) def find_possible_majority(numbers: List[int]) -> int: leader_index = 0 leader_count = 1 for i in range(len(numbers)): if numbers[leader_index] == numbers[i]: leader_count += 1 else: leader_count -= 1 if leader_count == 0: leader_index = i leader_count = 1 return numbers[leader_index] def is_majority(numbers: List[int], candidate: int) -> bool: count = sum(1 for num in numbers if num == candidate) return count > len(numbers) / 2 # Using Moore's voting algorithm def find_majority(numbers: List[int]) -> int: candidate = find_possible_majority(numbers) return candidate if is_majority(numbers, candidate) else -1 sample_input = """ 4 8 5 5 5 5 5 5 5 5 8 7 7 7 1 7 3 7 7 1 6 5 10 100 1000 1 5 1 6 7 1 1 10 1 """ _, *number_lists = sample_input.strip().split("\n") number_lists: List[List[int]] = [string_to_int_list(line) for line in number_lists] print(*[find_majority(numbers) for numbers in number_lists]) ``` # Merge Two Sorted Arrays The merging procedure is an essential part of [Merge Sort](https://rosalind.info/problems/ms/) (which is considered in one of the next problems). Given: A positive integer $n≤10^5$ and a sorted array A[1..n] of integers from $−10^5$ to $10^5$, a positive integer $m≤10^5$ and a sorted array $B[1..m]$ of integers from $−10^5$ to $10^5$. Return: A sorted array $C[1..n+m]$ containing all the elements of A and B. ## Sample Dataset ``` 4 2 4 10 18 3 -5 11 12 ``` ## Sample Output ``` -5 2 4 10 11 12 18 ``` ## Solution ```python from typing import List def parse_ints(x: str) -> List[int]: return [int(num) for num in x.split()] def merge_sorted_lists(list1: List[int], list2: List[int]) -> List[int]: merged = [] i, j = 0, 0 while i < len(list1) and j < len(list2): if list1[i] < list2[j]: merged.append(list1[i]) i += 1 else: merged.append(list2[j]) j += 1 merged.extend(list1[i:]) merged.extend(list2[j:]) return merged sample_input = """ 4 2 4 10 18 3 -5 11 12 """ _, list1_str, _, list2_str = sample_input.strip().split("\n") list1 = parse_ints(list1_str) list2 = parse_ints(list2_str) result = merge_sorted_lists(list1, list2) print(*result) ``` # 2SUM Given: A positive integer k≤20, a positive integer $n≤10^4$, and k arrays of size n containing integers from $−10^5$ to $10^5$. Return: For each array $A[1..n]$, output two different indices $1≤p<q≤n$ such that $A[p]=−A[q]$ if exist, and "-1" otherwise. ## Sample Dataset ``` 4 5 2 -3 4 10 5 8 2 4 -2 -8 -5 2 3 2 -4 5 4 -5 6 8 ``` ## Sample Output ``` -1 2 4 -1 1 3 ``` ## Solution ```python from typing import List, Tuple, Optional def parse_ints(x: str) -> List[int]: return [int(num) for num in x.split()] def two_sum(target: int, numbers: List[int]) -> Optional[Tuple[int, int]]: complement_indices = {} for i, num in enumerate(numbers, start=1): if num in complement_indices: return complement_indices[num], i complement_indices[target - num] = i return None def process_input(input_str: str) -> Tuple[int, int, List[List[int]]]: lines = input_str.strip().split("\n") k, n = parse_ints(lines[0]) arrays = [parse_ints(line) for line in lines[1:]] return k, n, arrays sample_input = """ 4 5 2 -3 4 10 5 8 2 4 -2 -8 -5 2 3 2 -4 5 4 -5 6 8 """ k, n, arrays = process_input(sample_input) for arr in arrays: result = two_sum(0, arr) if result: print(*result) else: print(-1) ``` # 3SUM Given: A positive integer $k≤20$, a positive integer $n≤10^4$, and $k$ arrays of size $n$ containing integers from $−10^5$ to $10^5$. Return: For each array $A[1..n]$, output three different indices $1≤p<q<r≤n$ such that $A[p]+A[q]+A[r]=0$ if exist, and"-1"otherwise. ## Sample Dataset ``` 4 5 2 -3 4 10 5 8 -6 4 -2 -8 -5 2 3 2 -4 2 4 -5 6 8 ``` ## Sample Output ``` -1 1 2 4 1 2 3 -1 ``` ## Solution ```python from typing import List, Tuple, Optional def parse_ints(x: str) -> List[int]: return [int(num) for num in x.split()] def process_input(input_str: str) -> Tuple[int, int, List[List[int]]]: lines = input_str.strip().split("\n") k, n = parse_ints(lines[0]) arrays = [parse_ints(line) for line in lines[1:]] return k, n, arrays def three_sum(n: int, a: List[int]) -> List[int]: h = {} for i in range(n): for j in range(i + 1, n): s = a[i] + a[j] if s in h: return [h[s] + 1, i + 1, j + 1] h[-a[i]] = i return [-1] sample_input = """ 4 5 2 -3 4 10 5 8 -6 4 -2 -8 -5 2 3 2 -4 2 4 -5 6 8 """ k, n, arrays = process_input(sample_input) for arr in arrays: print(*three_sum(n, arr)) ``` # Breadth-First Search The task is to use [breadth-first search](https://rosalind.info/glossary/algo-breadth-first-search/) to compute single-source shortest distances in an unweighted directed graph. Given: A [simple directed graph](https://rosalind.info/glossary/algo-simple-directed-graph/) with $n≤10^3$ vertices in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/). Return: An array D[1..n] where D[i] is the length of a shortest path from the vertex 1 to the vertex $i$ (D[1]=0). If i is not reachable from 1 set D[i] to −1. ## Sample Dataset ``` 6 6 4 6 6 5 4 3 3 5 2 1 1 4 ``` ## Sample Output ``` 0 -1 2 1 3 2 ``` ## Solution ```python from io import StringIO from typing import List, Dict, Union, Iterator from collections import deque def parse_ints(line: str) -> List[int]: return [int(num) for num in line.split()] def read_non_empty_line(handle: Iterator[str]) -> str: line = next(handle).strip() while not line: line = next(handle).strip() return line def parse_graph(handle: Iterator[str], directed: bool = False, weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]: nodes, n_edges = parse_ints(read_non_empty_line(handle)) graph = {n: [] for n in range(1, nodes + 1)} for _ in range(n_edges): edge = parse_ints(read_non_empty_line(handle)) if weighted: f, t, w = edge graph[f].append({"n": t, "w": w}) if not directed: graph[t].append({"n": f, "w": w}) else: f, t = edge graph[f].append(t) if not directed: graph[t].append(f) return graph def bfs(graph: Dict[int, List[int]], start: int = 1) -> List[int]: n = max(graph.keys()) distances = [-1] * (n + 1) distances[start] = 0 queue = deque([start]) while queue: node = queue.popleft() for neighbor in graph[node]: if distances[neighbor] == -1: queue.append(neighbor) distances[neighbor] = distances[node] + 1 return distances[1:] # Sample input sample_input = """ 6 6 4 6 6 5 4 3 3 5 2 1 1 4 """ graph = parse_graph(StringIO(sample_input), directed=True) print(*bfs(graph)) ``` # Connected Components The task is to use [depth-first search](https://rosalind.info/glossary/algo-depth-first-search/) to compute the number of [connected components](https://rosalind.info/glossary/algo-connected-graph/) in a given undirected graph. Given: A [simple graph](https://rosalind.info/glossary/algo-simple-graph/) with $n≤10^3$ vertices in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/). Return: The number of connected components in the graph. ## Sample Dataset ``` 12 13 1 2 1 5 5 9 5 10 9 10 3 4 3 7 3 8 4 8 7 11 8 11 11 12 8 12 ``` ## Sample Output ``` 3 ``` ## Solution ```python from typing import List, Dict, Set, Union def parse_integers(input_string: str) -> List[int]: return list(map(int, input_string.split())) def parse_graph(input_lines: List[str], is_directed: bool = False, is_weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]: graph_info = input_lines[0] if graph_info == "": graph_info = input_lines[1] num_nodes, num_edges = parse_integers(graph_info) edge_list = input_lines[1:num_edges+1] adjacency_list: Dict[int, List[Union[int, Dict[str, int]]]] = {} for node in range(1, num_nodes + 1): adjacency_list[node] = list() for edge in edge_list: if is_weighted: from_node, to_node, weight = parse_integers(edge) adjacency_list[from_node].append({"node": to_node, "weight": weight}) if not is_directed: adjacency_list[to_node].append({"node": from_node, "weight": weight}) else: from_node, to_node = parse_integers(edge) adjacency_list[from_node].append(to_node) if not is_directed: adjacency_list[to_node].append(from_node) return adjacency_list def find_connected_component(start_node: int, graph: Dict[int, List[int]]) -> Set[int]: def depth_first_search(current_node: int, visited_nodes: Set[int]) -> Set[int]: visited_nodes.add(current_node) for neighbor in graph[current_node]: if neighbor not in visited_nodes: depth_first_search(neighbor, visited_nodes) return visited_nodes return depth_first_search(start_node, set()) def find_all_components(graph: Dict[int, List[int]]) -> List[Set[int]]: unvisited_nodes = set(graph.keys()) all_components: List[Set[int]] = list() while unvisited_nodes: component = find_connected_component(next(iter(unvisited_nodes)), graph) unvisited_nodes -= component all_components.append(component) return all_components sample_input = """ 12 13 1 2 1 5 5 9 5 10 9 10 3 4 3 7 3 8 4 8 7 11 8 11 11 12 8 12 """ graph: Dict[int, List[int]] = parse_graph(sample_input.strip().split("\n")) print(len(find_all_components(graph))) ``` # Building a Heap A [binary heap](https://rosalind.info/glossary/algo-binary-heap/) is a [binary tree](https://rosalind.info/glossary/algo-binary-tree/) based data structure that is often used to implement [priority queues](https://rosalind.info/glossary/algo-priority-queue/). Binary heaps, in turn, can be easily implemented using an array if the underlying tree is a complete binary tree. The tree nodes have a natural ordering: row by row, starting at the root and moving left to right within each row. If there are nn nodes, this ordering specifies their positions 1,2,…,n within the array. Moving up and down the tree is easily simulated on the array, using the fact that node number j has parent $⌈j/2⌉$ and children 2j and 2j+1. The goal of this problem is to build a heap from the given array. For this, go from the end to the beginning of a given array and let each element"bubble up". Source: [Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006](https://rosalind.info/glossary/algo-algorithms-by-dasgupta-papadimitriou-vazirani-mcgraw-hill-2006/). Given: A positive integer $n≤10^5$ and array A[1..n] of integers from $−10^5$ to $10^5$. Return: A permuted array A satisfying the binary [max heap](https://rosalind.info/glossary/algo-heap/) property: for any $2≤i≤n$, $A[⌊i/2⌋]≥A[i]$. ## Sample Dataset ``` 5 1 3 5 7 2 ``` ## Sample Output ``` 7 5 1 3 2 ``` # Merge Sort The problem of [sorting](https://rosalind.info/glossary/algo-sorting-algorithm/) a list of numbers lends itself immediately to a [divide-and-conquer](https://rosalind.info/glossary/algo-divide-and-conquer/) strategy: split the list into two halves, recursively sort each half, and then merge the two sorted sublists (recall the problem [“Merge Two Sorted Arrays”](https://rosalind.info/problems/mer/)). Source: [Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006](https://rosalind.info/glossary/algo-algorithms-by-dasgupta-papadimitriou-vazirani-mcgraw-hill-2006/). Given: A positive integer $n≤10^5$ and an array $A[1..n]$ of integers from $−10^5$ to $10^5$. Return: A sorted array $A[1..n]$. ## Sample Dataset ``` 10 20 19 35 -18 17 -20 20 1 4 4 ``` ## Sample Output ``` -20 -18 1 4 4 17 19 20 20 35 ``` ## Solution ```python from typing import List def parse_integers(line: str) -> List[int]: return [int(num) for num in line.split()] def merge(left: List[int], right: List[int]) -> List[int]: merged = [] left_index, right_index = 0, 0 while left_index < len(left) and right_index < len(right): if left[left_index] < right[right_index]: merged.append(left[left_index]) left_index += 1 else: merged.append(right[right_index]) right_index += 1 # Append any remaining elements from both halves merged.extend(left[left_index:]) merged.extend(right[right_index:]) return merged def merge_sort(array: List[int]) -> List[int]: if len(array) > 1: mid_index = len(array) // 2 left_half = merge_sort(array[:mid_index]) right_half = merge_sort(array[mid_index:]) return merge(left_half, right_half) else: return array sample_input = """ 10 20 19 35 -18 17 -20 20 1 4 4 """ _, numbers = sample_input.strip().split("\n") print(*merge_sort(parse_integers(numbers))) ``` # 2-Way Partition A partition procedure is an essential part of the Quick Sort algorithm, the subject of one of the following problems. Its main goal is to put the first element of a given array to its proper place in a sorted array. It can be implemented in [linear](https://rosalind.info/glossary/algo-linear/) time, by a single scan of a given array. Moreover, it is not hard to come up with an [in-place](https://rosalind.info/glossary/algo-in-place-algorithm/) algorithm. Given: A positive integer $n≤10^5$ and an array $A[1..n]$ of integers from $−10^5$ to $10^5$. Return: A permuted array $B[1..n]$ such that it is a permutation of A and there is an index $1≤q≤n$ such that $B[i]≤A[1]$ for all $1≤i≤q−1$, $B[q]=A[1]$, and $B[i]>A[1]$ for all $q+1≤i≤n$. ## Sample Dataset ``` 9 7 2 5 6 1 3 9 4 8 ``` ## Sample Output ``` 4 2 5 6 1 3 7 9 8 ``` ## Solution ```python from typing import List def parse_integers(line: str) -> List[int]: return [int(number) for number in line.split()] def partition(array: List[int]) -> List[int]: if len(array) <= 1: return array pivot = array[0] swap_index = 0 for current_index in range(1, len(array)): if array[current_index] <= pivot: swap_index += 1 array[current_index], array[swap_index] = array[swap_index], array[current_index] array[0], array[swap_index] = array[swap_index], array[0] return array sample_input = """ 9 7 2 5 6 1 3 9 4 8 """ _, input_numbers = sample_input.strip().split("\n") result = partition(parse_integers(input_numbers)) print(*result) ``` # 3-Way Partition This problem is very similar to [“2-Way Partition”](https://rosalind.info/problems/par/), but now the goal is to partition an input array more carefully. Given: A positive integer $n≤10^5$ and an array $A[1..n]$ of integers from $−10^5$ to $10^5$. Return: An array B[1..n] such that it is a permutation of A and there are indices $1≤q≤r≤n$ such that $B[i]<A[1]$ for all $1≤i≤q−1$, $B[i]=A[1]$ for all $q≤i≤r$, and $B[i]>A[1]$ for all $r+1≤i≤n$. ## Sample Dataset ``` 9 4 5 6 4 1 2 5 7 4 ``` ## Sample Output ``` 2 1 4 4 4 5 7 6 5 ``` ## Solution ```python from typing import List, Tuple def parse_integers(line: str) -> List[int]: return [int(number) for number in line.split()] def three_way_partition(array: List[int], start: int = None, end: int = None) -> Tuple[int, int]: if start is None: start = 0 if end is None: end = len(array) - 1 pivot = array[start] low = start current = start high = end while current <= high: if array[current] < pivot: array[current], array[low] = array[low], array[current] current += 1 low += 1 elif array[current] > pivot: array[current], array[high] = array[high], array[current] high -= 1 else: current += 1 return low, high sample_input = """ 9 4 5 6 4 1 2 5 7 4 """ _, input_line = sample_input.strip().split("\n") numbers = parse_integers(input_line) three_way_partition(numbers) print(*numbers) ``` # Square in a Graph Given: A positive integer k≤20 and k [simple undirected graphs](https://rosalind.info/glossary/algo-simple-graph/) with $n≤400$ vertices in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/). Return: For each graph, output"1"if it contains a simple cycle (that is, a cycle which doesn't intersect itself) of length $4$ and"-1"otherwise. Source: [Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006](https://rosalind.info/glossary/algo-algorithms-by-dasgupta-papadimitriou-vazirani-mcgraw-hill-2006/). ## Sample Dataset ``` 2 4 5 3 4 4 2 3 2 3 1 1 2 4 4 1 2 3 4 2 4 4 1 ``` ## Sample Output ``` 1 -1 ``` ## Solution ```python from typing import List, Dict, Union, Iterator def parse_integers(line: str) -> List[int]: return [int(num) for num in line.split()] def read_non_empty_line(input_iterator: Iterator[str]) -> str: line = next(input_iterator).strip() while not line: line = next(input_iterator).strip() return line def create_graph(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]: num_nodes, num_edges = parse_integers(read_non_empty_line(input_iterator)) graph = {node: [] for node in range(1, num_nodes + 1)} for _ in range(num_edges): edge_data = parse_integers(read_non_empty_line(input_iterator)) if is_weighted: from_node, to_node, weight = edge_data graph[from_node].append({"node": to_node, "weight": weight}) if not is_directed: graph[to_node].append({"node": from_node, "weight": weight}) else: from_node, to_node = edge_data graph[from_node].append(to_node) if not is_directed: graph[to_node].append(from_node) return graph def depth_first_search(graph: Dict[int, List[Union[int, Dict[str, int]]]], start: int, max_depth: int): def dfs_recursive(current_node: int, current_depth: int, visited: set): if current_depth == max_depth: yield current_node if current_depth < max_depth: for neighbor in graph[current_node]: neighbor_node = neighbor if isinstance(neighbor, int) else neighbor['node'] if neighbor_node not in visited: yield from dfs_recursive(neighbor_node, current_depth + 1, visited | {current_node}) return dfs_recursive(start, 0, set()) def has_square_cycle(graph: Dict[int, List[Union[int, Dict[str, int]]]], cycle_length: int) -> int: for start_node in graph: for end_node in depth_first_search(graph, start_node, cycle_length - 1): if end_node in graph[start_node]: return 1 return -1 def parse_multiple_graphs(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> List[Dict[int, List[Union[int, Dict[str, int]]]]]: num_graphs = int(read_non_empty_line(input_iterator)) return [create_graph(input_iterator, is_directed, is_weighted) for _ in range(num_graphs)] # Sample input sample_input = """ 2 4 5 3 4 4 2 3 2 3 1 1 2 4 4 1 2 3 4 2 4 4 1 """.strip().split("\n") # Process the input and print results graphs = parse_multiple_graphs(iter(sample_input), is_directed=False) results = [has_square_cycle(graph, 4) for graph in graphs] print(*results) ``` # Testing Bipartiteness A *bipartite* graph is a graph $G=(V,E)$ whose vertices can be partitioned into two sets ($V=V_1∪V_2$ and $V_1∩V_2=∅$) such that there are no edges between vertices in the same set (for instance, if $u,v∈V1$, then there is no edge between u and v). There are many other ways to formulate this property. For instance, an undirected graph is bipartite if and only if it can be colored with just two colors. Another one: an undirected graph is bipartite if and only if it contains no cycles of odd length. Source: [Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006](https://rosalind.info/glossary/algo-algorithms-by-dasgupta-papadimitriou-vazirani-mcgraw-hill-2006/). Given: A positive integer k≤20 and k [simple graphs](https://rosalind.info/glossary/algo-simple-graph/) in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/) with at most $10^3$ vertices each. Return: For each graph, output"1"if it is bipartite and"-1"otherwise. ## Sample Dataset ``` 2 3 3 1 2 3 2 3 1 4 3 1 4 3 1 1 2 ``` ## Sample Output ``` -1 1 ``` ## Solution ```python from typing import List, Dict, Union, Iterator def parse_integers(line: str) -> List[int]: return [int(num) for num in line.split()] def read_non_empty_line(input_iterator: Iterator[str]) -> str: line = next(input_iterator).strip() while not line: line = next(input_iterator).strip() return line def parse_graph(input_iterator: Iterator[str], directed: bool = False, weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]: num_nodes, num_edges = parse_integers(read_non_empty_line(input_iterator)) graph = {node: [] for node in range(1, num_nodes + 1)} for _ in range(num_edges): edge = parse_integers(read_non_empty_line(input_iterator)) if weighted: from_node, to_node, weight = edge graph[from_node].append({"node": to_node, "weight": weight}) if not directed: graph[to_node].append({"node": from_node, "weight": weight}) else: from_node, to_node = edge graph[from_node].append(to_node) if not directed: graph[to_node].append(from_node) return graph def is_bipartite(graph: Dict[int, List[int]]) -> int: color = {1: 0} queue = [1] while queue: current_node = queue.pop(0) for neighbor in graph[current_node]: neighbor_color = (color[current_node] + 1) % 2 if neighbor not in color: queue.append(neighbor) color[neighbor] = neighbor_color elif color[neighbor] != neighbor_color: return -1 return 1 def process_multiple_graphs(input_iterator: Iterator[str]) -> List[int]: num_cases = int(read_non_empty_line(input_iterator)) results = [] for _ in range(num_cases): graph = parse_graph(input_iterator) results.append(is_bipartite(graph)) return results sample_input = """ 2 3 3 1 2 3 2 3 1 4 3 1 4 3 1 1 2 """.strip().split("\n") # Convert the list to an iterator sample_input_iterator = iter(sample_input) # Process multiple graphs results = process_multiple_graphs(sample_input_iterator) print(*results) ``` # Testing Acyclicity Given: A positive integer $k≤20$ and k [simple directed graphs](https://rosalind.info/glossary/algo-simple-directed-graph/) in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/) with at most $10^3$ vertices and $3⋅10^3$ edges each. Return: For each graph, output"1"if the graph is [acyclic](https://rosalind.info/glossary/algo-directed-acyclic-graph/) and"-1"otherwise. ## Sample Dataset ``` 3 2 1 1 2 4 4 4 1 1 2 2 3 3 1 4 3 4 3 3 2 2 1 ``` ## Sample Output ``` 1 -1 1 ``` ## Solution ```python from typing import List, Dict, Union, Iterator def parse_integers(line: str) -> List[int]: return [int(num) for num in line.split()] def read_non_empty_line(input_iter: Iterator[str]) -> str: line = next(input_iter).strip() while not line: line = next(input_iter).strip() return line def parse_graph(input_iter: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]: node_count, edge_count = parse_integers(read_non_empty_line(input_iter)) graph = {node: [] for node in range(1, node_count + 1)} for _ in range(edge_count): edge = parse_integers(read_non_empty_line(input_iter)) if is_weighted: source, target, weight = edge graph[source].append({"node": target, "weight": weight}) if not is_directed: graph[target].append({"node": source, "weight": weight}) else: source, target = edge graph[source].append(target) if not is_directed: graph[target].append(source) return graph def graph_nodes(graph): nodes = set() for node, neighbors in graph.items(): nodes.add(node) nodes = nodes.union(neighbors) return nodes def remove_leaves(graph): nodes = graph_nodes(graph) leaves = nodes - graph.keys() return {n: set(v) - leaves for n, v in graph.items() if len(set(v) - leaves)} def is_dag(graph): while graph: new_graph = remove_leaves(graph) if len(graph) == len(new_graph): return -1 graph = new_graph return 1 def parse_multiple_graphs(input_iter: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> List[Dict[int, List[Union[int, Dict[str, int]]]]]: case_count = int(read_non_empty_line(input_iter)) graphs = [] for _ in range(case_count): graphs.append(parse_graph(input_iter, is_directed, is_weighted)) return graphs sample_input = """ 3 2 1 1 2 4 4 4 1 1 2 2 3 3 1 4 3 4 3 3 2 2 1 """.strip().split("\n") # Convert the list to an iterator input_iterator = iter(sample_input) # Parse multiple graphs graphs = parse_multiple_graphs(input_iterator, is_directed=True) # Process each graph results = [is_dag(graph) for graph in graphs] print(*results) ``` # Dijkstra's Algorithm The task is to use [Dijkstra's algorithm](https://rosalind.info/glossary/algo-dijkstras-algorithm/) to compute single-source shortest distances in a directed graph with positive edge weights. Given: A [simple directed graph](https://rosalind.info/glossary/algo-simple-directed-graph/) with positive edge weights from 1 to $10^3$ and $n≤10^3$ vertices in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/). Return: An array $D[1..n]$ where $D[i]$ is the length of a shortest path from the vertex 1 to the vertex i ($D[1]=0$). If ii is not reachable from 1 set D[i] to −1. ## Sample Dataset ``` 6 10 3 4 4 1 2 4 1 3 2 2 3 3 6 3 2 3 5 5 5 4 1 3 2 1 2 4 2 2 5 3 ``` ## Sample Output ``` 0 3 2 5 6 -1 ``` ## Solution ```python from math import inf from heapq import heappush, heappop from typing import List, Dict, Union, Iterator def parse_integers(line: str) -> List[int]: return [int(num) for num in line.split()] def read_non_empty_line(input_iter: Iterator[str]) -> str: line = next(input_iter).strip() while not line: line = next(input_iter).strip() return line def parse_graph(input_iter: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]: vertex_count, edge_count = parse_integers(read_non_empty_line(input_iter)) adjacency_list = {vertex: [] for vertex in range(1, vertex_count + 1)} for _ in range(edge_count): edge = parse_integers(read_non_empty_line(input_iter)) if is_weighted: source, destination, weight = edge adjacency_list[source].append({"vertex": destination, "weight": weight}) if not is_directed: adjacency_list[destination].append({"vertex": source, "weight": weight}) else: source, destination = edge adjacency_list[source].append(destination) if not is_directed: adjacency_list[destination].append(source) return adjacency_list def dijkstra(graph, start_vertex=1): distances = [inf for _ in range(len(graph) + 1)] distances[start_vertex] = 0 priority_queue = [] heappush(priority_queue, (0, start_vertex)) visited = set() while priority_queue: current_vertex = heappop(priority_queue)[1] visited.add(current_vertex) for neighbor in graph[current_vertex]: if isinstance(neighbor, dict): next_vertex = neighbor["vertex"] edge_weight = neighbor["weight"] else: next_vertex = neighbor edge_weight = 1 # Assume unit weight for unweighted graphs if next_vertex not in visited: new_distance = distances[current_vertex] + edge_weight if new_distance < distances[next_vertex]: distances[next_vertex] = new_distance heappush(priority_queue, (distances[next_vertex], next_vertex)) return [-1 if distance == inf else distance for distance in distances[1:]] sample_input = """ 6 10 3 4 4 1 2 4 1 3 2 2 3 3 6 3 2 3 5 5 5 4 1 3 2 1 2 4 2 2 5 3 """.strip().split("\n") # Convert the list to an iterator input_iterator = iter(sample_input) graph = parse_graph(input_iterator, is_directed=True, is_weighted=True) print(*dijkstra(graph)) ``` # Heap Sort The heap sort algorithm first transforms a given array into a [max heap](https://rosalind.info/glossary/algo-heap/) (recall the problem [“Building a Heap”](https://rosalind.info/problems/hea/)). It then repeats the following two simple steps $n−1$ times: - Swap the last element of the heap with its root and decrease the size of the heap by 1. - "Sift-down"the new root element to its proper place. Given: A positive integer $n≤10^5$ and an array A[1..n] of integers from $−10^5$ to $10^5$. Return: A sorted array A. ## Sample Dataset ``` 9 2 6 7 1 3 5 4 8 9 ``` ## Sample Output ``` 1 2 3 4 5 6 7 8 9 ``` ## Solution ```python from typing import List, Any def parse_integers(line: str) -> List[int]: return [int(num) for num in line.split()] def bubble_up(heap: List[int], index: int) -> None: if index == 0: return parent_index: int = (index - 1) // 2 current_index: int = index if heap[parent_index] > heap[current_index]: bubble_up(heap, parent_index) else: heap[parent_index], heap[current_index] = heap[current_index], heap[parent_index] bubble_up(heap, parent_index) def build_heap(array: List[int]) -> List[int]: heap: List[int] = [] for i, element in enumerate(array): heap.append(element) bubble_up(heap, i) return heap def sift_down(heap: List[int], start_index: int, end_index: int) -> None: root_index: int = start_index while root_index * 2 + 1 <= end_index: left_child_index: int = root_index * 2 + 1 right_child_index: int = left_child_index + 1 swap_index: int = root_index if heap[swap_index] < heap[left_child_index]: swap_index = left_child_index if right_child_index <= end_index and heap[swap_index] < heap[right_child_index]: swap_index = right_child_index if swap_index != root_index: heap[root_index], heap[swap_index] = heap[swap_index], heap[root_index] root_index = swap_index else: return def heap_sort(array: List[int]) -> List[int]: heap: List[int] = build_heap(array) last_index: int = len(heap) - 1 while last_index > 0: heap[0], heap[last_index] = heap[last_index], heap[0] last_index -= 1 sift_down(heap, 0, last_index) return heap sample_input: str = """ 9 2 6 7 1 3 5 4 8 9 """ _, input_array_str = sample_input.strip().split("\n") input_array: List[int] = parse_integers(input_array_str) sorted_array: List[int] = heap_sort(input_array) print(*sorted_array) ``` # Counting Inversions An inversion of an array A[1..n] is a pair of indices $(i,j)$ such that $1≤i<j≤n$ and A[i]>A[j]. The number of inversions shows how far the array is from being sorted: if it is already sorted then there are no inversions, whereas if it is sorted in reverse order then the number of inversions is maximal. Given: A positive integer $n≤10^5$ and an array $A[1..n]$ of integers from $−10^5$ to $10^5$. Return: The number of inversions in A. ## Sample Dataset ``` 5 -6 1 15 8 10 ``` ## Sample Output ``` 2 ``` ## Solution ```python from typing import List, Tuple def parse_integers(line: str) -> List[int]: return [int(num) for num in line.split()] def merge_and_count_inversions(left: List[int], right: List[int]) -> Tuple[List[int], int]: merged: List[int] = [] inversion_count: int = 0 left_length: int = len(left) left_index: int = 0 while left and right: if left[0] <= right[0]: left_index += 1 merged.append(left.pop(0)) else: inversion_count += left_length - left_index merged.append(right.pop(0)) merged.extend(left) merged.extend(right) return merged, inversion_count def merge_sort_and_count_inversions(arr: List[int]) -> Tuple[List[int], int]: if len(arr) > 1: mid: int = len(arr) // 2 left_half, left_inversions = merge_sort_and_count_inversions(arr[:mid]) right_half, right_inversions = merge_sort_and_count_inversions(arr[mid:]) merged, merge_inversions = merge_and_count_inversions(left_half, right_half) total_inversions: int = left_inversions + right_inversions + merge_inversions return merged, total_inversions else: return arr, 0 sample_input: str = """ 5 -6 1 15 8 10 """ _, input_array_str = sample_input.strip().split("\n") input_array: List[int] = parse_integers(input_array_str) _, inversion_count = merge_sort_and_count_inversions(input_array) print(inversion_count) ``` # Bellman-Ford Algorithm The task is to use [Bellman-Ford algorithm](https://rosalind.info/glossary/algo-bellman-ford-algorithm/) to compute single-source shortest distances in a directed graph with possibly negative edge weights (but without negative cycles). Given: A [simple directed graph](https://rosalind.info/glossary/algo-simple-directed-graph/) with integer edge weights from $−10^3$ to $10^3$ and $n≤10^3$ vertices in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/). Return: An array D[1..n] where D[i] is the length of a shortest path from the vertex 1 to the vertex ii (D[1]=0). If ii is not reachable from 1 set D[i] to `x`. ## Sample Dataset ``` 9 13 1 2 10 3 2 1 3 4 1 4 5 3 5 6 -1 7 6 -1 8 7 1 1 8 8 7 2 -4 2 6 2 6 3 -2 9 5 -10 9 4 7 ``` ## Sample Output ``` 0 5 5 6 9 7 9 8 x ``` ## Solution ```python from math import inf, isinf from typing import List, Dict, Union, Iterator, Set, Tuple def parse_integers(line: str) -> List[int]: return [int(num) for num in line.split()] def read_non_empty_line(input_iterator: Iterator[str]) -> str: line = next(input_iterator).strip() while not line: line = next(input_iterator).strip() return line EdgeInfo = Dict[str, int] Graph = Dict[int, List[Union[int, EdgeInfo]]] def parse_graph(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Graph: vertex_count, edge_count = parse_integers(read_non_empty_line(input_iterator)) adjacency_list: Graph = {vertex: [] for vertex in range(1, vertex_count + 1)} for _ in range(edge_count): edge_data = parse_integers(read_non_empty_line(input_iterator)) if is_weighted: source_vertex, target_vertex, edge_weight = edge_data adjacency_list[source_vertex].append({"node": target_vertex, "weight": edge_weight}) if not is_directed: adjacency_list[target_vertex].append({"node": source_vertex, "weight": edge_weight}) else: source_vertex, target_vertex = edge_data adjacency_list[source_vertex].append(target_vertex) if not is_directed: adjacency_list[target_vertex].append(source_vertex) return adjacency_list def count_edges(graph: Graph) -> int: return sum(len(neighbors) for neighbors in graph.values()) def get_all_vertices(graph: Graph) -> Set[int]: all_vertices: Set[int] = set(graph.keys()) for neighbors in graph.values(): for neighbor in neighbors: if isinstance(neighbor, dict): all_vertices.add(neighbor["node"]) else: all_vertices.add(neighbor) return all_vertices def bellman_ford(graph: Graph, start_vertex: int = 1) -> List[Union[int, str]]: distances: Dict[int, float] = {vertex: inf for vertex in get_all_vertices(graph)} distances[start_vertex] = 0 for _ in range(count_edges(graph) - 1): for current_vertex, neighbors in graph.items(): for neighbor in neighbors: if isinstance(neighbor, dict): target_vertex = neighbor["node"] edge_weight = neighbor["weight"] if distances[current_vertex] + edge_weight < distances[target_vertex]: distances[target_vertex] = distances[current_vertex] + edge_weight return ["x" if isinf(distance) else distance for distance in distances.values()] sample_input: str = """ 9 13 1 2 10 3 2 1 3 4 1 4 5 3 5 6 -1 7 6 -1 8 7 1 1 8 8 7 2 -4 2 6 2 6 3 -2 9 5 -10 9 4 7 """.strip().split("\n") # Convert the list to an iterator input_iterator = iter(sample_input) # Parse the graph with correct parameters graph = parse_graph(input_iterator, is_directed=True, is_weighted=True) # Run Bellman-Ford algorithm result = bellman_ford(graph) print(*result) ``` # Shortest Cycle Through a Given Edge Given: A positive integer $k≤20$ and k [simple directed graphs](https://rosalind.info/glossary/algo-simple-directed-graph/) with positive integer edge weights and at most $10^3$ vertices in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/). Return: For each graph, output the length of a shortest cycle going through the first specified edge if there is a cycle and"-1"otherwise. ## Sample Dataset ``` 2 4 5 2 4 2 3 2 1 1 4 3 2 1 10 1 3 4 4 5 3 2 1 2 4 2 4 1 3 2 1 10 1 3 4 ``` ## Sample Output ``` -1 10 ``` ## Solution ```python from typing import List, Dict, Union, Iterator, Tuple from math import inf from heapq import heappush, heappop from io import StringIO GraphNode = Union[int, Dict[str, int]] Graph = Dict[int, List[GraphNode]] def parse_integers(line: str) -> List[int]: return [int(num) for num in line.split()] def read_non_empty_line(input_iter: Iterator[str]) -> str: line = next(input_iter).strip() while not line: line = next(input_iter).strip() return line def parse_graph(input_iter: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Graph: vertex_count, edge_count = parse_integers(read_non_empty_line(input_iter)) adj_list: Graph = {vertex: [] for vertex in range(1, vertex_count + 1)} for _ in range(edge_count): edge_data = parse_integers(read_non_empty_line(input_iter)) if is_weighted: src, dest, weight = edge_data adj_list[src].append({"node": dest, "weight": weight}) if not is_directed: adj_list[dest].append({"node": src, "weight": weight}) else: src, dest = edge_data adj_list[src].append(dest) if not is_directed: adj_list[dest].append(src) return adj_list def dijkstra(graph: Graph, start: int = 1) -> List[int]: distances = [inf for _ in range(len(graph) + 1)] distances[start] = 0 priority_queue = [] heappush(priority_queue, (0, start)) visited = set() while priority_queue: _, current_node = heappop(priority_queue) if current_node in visited: continue visited.add(current_node) for neighbor in graph[current_node]: if isinstance(neighbor, dict): neighbor_node, edge_weight = neighbor["node"], neighbor["weight"] else: neighbor_node, edge_weight = neighbor, 1 if neighbor_node not in visited: new_distance = distances[current_node] + edge_weight if new_distance < distances[neighbor_node]: distances[neighbor_node] = new_distance heappush(priority_queue, (new_distance, neighbor_node)) return [-1 if d == inf else d for d in distances[1:]] def extract_first_edges(input_handle: StringIO) -> List[List[int]]: lines = input_handle.read().splitlines() graph_count = int(lines[0]) current_line = 1 first_edges = [] for _ in range(graph_count): while not lines[current_line]: current_line += 1 _, edge_count = map(int, lines[current_line].split()) first_edges.append(list(map(int, lines[current_line + 1].split()))) current_line += int(edge_count) + 1 return first_edges def calculate_cycle_length(graph: Graph, edge: List[int]) -> int: distance = dijkstra(graph, start=edge[1])[edge[0] - 1] return distance if distance == -1 else distance + edge[2] def parse_multiple_graphs(input_str: str, directed: bool = False, weighted: bool = True) -> List[Graph]: input_iter = iter(input_str.splitlines()) graph_count = int(next(input_iter)) graphs = [] for _ in range(graph_count): graphs.append(parse_graph(input_iter, is_directed=directed, is_weighted=weighted)) return graphs # Sample input sample_input = """ 2 4 5 2 4 2 3 2 1 1 4 3 2 1 10 1 3 4 4 5 3 2 1 2 4 2 4 1 3 2 1 10 1 3 4 """ # Main execution input_handle = StringIO(sample_input.strip()) first_edges = extract_first_edges(input_handle) input_handle.seek(0) # Reset the StringIO object to the beginning graphs = parse_multiple_graphs(input_handle.read(), directed=True, weighted=True) results = [calculate_cycle_length(graphs[i], first_edges[i]) for i in range(len(graphs))] print(*results) ``` # Median The task is to implement a linear time randomized algorithm for the [selection](https://rosalind.info/glossary/algo-selection-algorithm/) problem. Given: A positive integer n≤105n≤105 and an array $A[1..n]$ of integers from $−10^5$ to $10^5$, a positive number $k≤n$. Return: The k-th smallest element of A. Source: [Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006](https://rosalind.info/glossary/algo-algorithms-by-dasgupta-papadimitriou-vazirani-mcgraw-hill-2006/). ## Sample Dataset ``` 11 2 36 5 21 8 13 11 20 5 4 1 8 ``` ## Sample Output ``` 13 ``` ## Solution ```python from typing import List, Tuple from io import StringIO def parse_integers(line: str) -> List[int]: """Parse a line of space-separated integers into a list of integers.""" return [int(num) for num in line.split()] def three_way_partition(arr: List[int], low: int = 0, high: int = None) -> Tuple[int, int]: """Partition the array into three parts based on a pivot.""" if high is None: high = len(arr) - 1 pivot = arr[low] mid = low while mid <= high: if arr[mid] < pivot: arr[low], arr[mid] = arr[mid], arr[low] low += 1 mid += 1 elif arr[mid] > pivot: arr[mid], arr[high] = arr[high], arr[mid] high -= 1 else: mid += 1 return low, high def find_kth_element(arr: List[int], k: int) -> int: """Find the k-th element in the array using a three-way partitioning method.""" def find_kth_recursive(arr: List[int], k: int, low: int, high: int) -> int: left, right = three_way_partition(arr, low, high) if k < left: return find_kth_recursive(arr, k, low, left - 1) elif k > right: return find_kth_recursive(arr, k, right + 1, high) else: return arr[k] return find_kth_recursive(arr, k, 0, len(arr) - 1) def process_input(input_str: str) -> Tuple[List[int], int]: """Process the input string and return the list of integers and the index k.""" lines = input_str.strip().split('\n') arr = parse_integers(lines[1]) k = int(lines[2]) return arr, k sample_input = """ 11 2 36 5 21 8 13 11 20 5 4 1 8 """ arr, k = process_input(sample_input) result = find_kth_element(arr, k - 1) print(result) ``` # Partial Sort Given: A positive integer $n≤10^5$ and an array A[1..n] of integers from $−10^5$ to $10^5$, a positive integer k≤1000. Return: The k smallest elements of a sorted array A. ## Sample Dataset ``` 10 4 -6 7 8 -9 100 12 13 56 17 3 ``` ## Sample Output ``` -9 -6 4 ``` ## Solution ```python from typing import List def parse_integers(line: str) -> List[int]: """Parse a line of space-separated integers into a list of integers.""" return [int(num) for num in line.split()] def heapify_up(heap: List[int], i: int) -> None: """Maintain heap property by moving an element up the heap.""" while i > 0: parent = (i - 1) // 2 if heap[parent] < heap[i]: heap[parent], heap[i] = heap[i], heap[parent] i = parent else: break def build_max_heap(arr: List[int]) -> List[int]: """Build a max heap from an array.""" heap = [] for x in arr: heap.append(x) heapify_up(heap, len(heap) - 1) return heap def sift_down(heap: List[int], start: int, end: int) -> None: """Maintain heap property by moving an element down the heap.""" root = start while root * 2 + 1 <= end: left = root * 2 + 1 right = left + 1 swap = root if heap[swap] < heap[left]: swap = left if right <= end and heap[swap] < heap[right]: swap = right if swap != root: heap[root], heap[swap] = heap[swap], heap[root] root = swap else: return def heap_sort(arr: List[int]) -> List[int]: """Sort an array using heap sort algorithm.""" heap = build_max_heap(arr) for i in range(len(heap) - 1, 0, -1): heap[0], heap[i] = heap[i], heap[0] sift_down(heap, 0, i - 1) return heap def partial_sort(arr: List[int], k: int) -> List[int]: """Find and sort the k smallest elements in the array.""" heap = build_max_heap(arr[:k]) for x in arr[k:]: if x < heap[0]: heap[0] = x sift_down(heap, 0, k - 1) return heap_sort(heap) # Sample input processing sample_input = """ 10 4 -6 7 8 -9 100 12 13 56 17 3 """ _, arr_str, k_str = sample_input.strip().split("\n") arr = parse_integers(arr_str) k = int(k_str) # Perform partial sort and print result result = partial_sort(arr, k) print(*result) ``` # Topological Sorting Given: A [simple directed acyclic graph](https://rosalind.info/glossary/algo-simple-directed-acyclic-graph/) with $n≤10^3$ vertices in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/). Return: A [topological sorting](https://rosalind.info/glossary/algo-topological-sorting/) (i.e., a permutation of vertices) of the graph. ## Sample Dataset ``` 4 5 1 2 3 1 3 2 4 3 4 2 ``` ## Sample Output ``` 4 3 1 2 ``` ## Solution ```python from typing import List, Iterator, Dict, Union, Set from collections import defaultdict from io import StringIO GraphNode = Union[int, Dict[str, int]] Graph = Dict[int, List[GraphNode]] def parse_integers(line: str) -> List[int]: return [int(num) for num in line.split()] def read_non_empty_line(input_iterator: Iterator[str]) -> str: line = next(input_iterator).strip() while not line: line = next(input_iterator).strip() return line def parse_graph(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Graph: vertex_count, edge_count = parse_integers(read_non_empty_line(input_iterator)) adjacency_list: Graph = {vertex: [] for vertex in range(1, vertex_count + 1)} for _ in range(edge_count): edge_data = parse_integers(read_non_empty_line(input_iterator)) if is_weighted: source, destination, weight = edge_data adjacency_list[source].append({"node": destination, "weight": weight}) if not is_directed: adjacency_list[destination].append({"node": source, "weight": weight}) else: source, destination = edge_data adjacency_list[source].append(destination) if not is_directed: adjacency_list[destination].append(source) return adjacency_list def get_all_graph_nodes(graph: Graph) -> Set[int]: nodes = set() for node, neighbors in graph.items(): nodes.add(node) for neighbor in neighbors: if isinstance(neighbor, dict): nodes.add(neighbor["node"]) else: nodes.add(neighbor) return nodes def topological_sort(graph: Graph) -> List[int]: def dfs_topological(vertex: int, visited: Dict[int, bool], stack: List[int]): visited[vertex] = True for neighbor in graph[vertex]: neighbor_node = neighbor["node"] if isinstance(neighbor, dict) else neighbor if not visited[neighbor_node]: dfs_topological(neighbor_node, visited, stack) stack.append(vertex) visited = defaultdict(bool) stack = [] for node in get_all_graph_nodes(graph): if not visited[node]: dfs_topological(node, visited, stack) return stack[::-1] # Sample input processing sample_input = """ 4 5 1 2 3 1 3 2 4 3 4 2 """ input_iterator = iter(StringIO(sample_input.strip()).readlines()) graph = parse_graph(input_iterator, is_directed=True) sorted_nodes = topological_sort(graph) print(*sorted_nodes) ``` # Hamiltonian Path in DAG A Hamiltonian path is a path in a graph that visits each vertex exactly once. Checking whether a graph contains a Hamiltonian path is a well-known hard problem. At the same time it is easy to perform such a check if a given graph is a [DAG](https://rosalind.info/glossary/algo-directed-acyclic-graph/). Given: A positive integer k≤20 and k [simple directed acyclic graphs](https://rosalind.info/glossary/algo-simple-directed-acyclic-graph/) in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/) with at most $10^3$ vertices each. Return: For each graph, if it contains a Hamiltonian path output"1"followed by a Hamiltonian path (i.e., a list of vertices), otherwise output"-1". ## Sample Dataset ``` 2 3 3 1 2 2 3 1 3 4 3 4 3 3 2 4 1 ``` ## Sample Output ``` 1 1 2 3 -1 ``` ## Solution ```python from typing import List, Iterator, Dict, Set from collections import defaultdict from io import StringIO Graph = Dict[int, List[int]] def parse_integers(line: str) -> List[int]: return list(map(int, line.split())) def read_non_empty_line(input_iterator: Iterator[str]) -> str: return next(line for line in input_iterator if line.strip()) def parse_graph(input_iterator: Iterator[str], is_directed: bool = False) -> Graph: vertex_count, edge_count = parse_integers(read_non_empty_line(input_iterator)) adjacency_list: Graph = defaultdict(list) for _ in range(edge_count): source, destination = parse_integers(read_non_empty_line(input_iterator)) adjacency_list[source].append(destination) if not is_directed: adjacency_list[destination].append(source) return adjacency_list def parse_multiple_graphs(input_iterator: Iterator[str], is_directed: bool = False) -> List[Graph]: num_cases = int(read_non_empty_line(input_iterator)) return [parse_graph(input_iterator, is_directed) for _ in range(num_cases)] def graph_nodes(graph: Graph) -> Set[int]: return set(graph.keys()) | set.union(*(set(val) for val in graph.values())) def topological_sort(graph: Graph) -> List[int]: def dfs(node: int, visited: Set[int], stack: List[int]): visited.add(node) for neighbor in graph[node]: if neighbor not in visited: dfs(neighbor, visited, stack) stack.append(node) visited: Set[int] = set() stack: List[int] = [] for node in graph_nodes(graph): if node not in visited: dfs(node, visited, stack) return stack[::-1] def hdag(graph: Graph) -> List[int]: sorted_nodes = topological_sort(graph) for a, b in zip(sorted_nodes, sorted_nodes[1:]): if b not in graph[a]: return [-1] return [1] + sorted_nodes sample_input = """ 2 3 3 1 2 2 3 1 3 4 3 4 3 3 2 4 1 """ input_iterator = iter(StringIO(sample_input.strip()).readlines()) graphs = parse_multiple_graphs(input_iterator, is_directed=True) for graph in graphs: print(*hdag(graph)) ``` # Negative Weight Cycle The task is to use [Bellman-Ford algorithm](https://rosalind.info/glossary/algo-bellman-ford-algorithm/) to check whether a given graph contains a cycle of negative weight. Given: A positive integer k≤20 and k [simple directed graphs](https://rosalind.info/glossary/algo-simple-directed-graph/) with integer edge weights from $−10^3$ to $10^3$ and $n≤10^3$ vertices in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/). Return: For each graph, output"1"if it contains a negative weight cycle and"-1"otherwise. ## Sample Dataset ``` 2 4 5 1 4 4 4 2 3 2 3 1 3 1 6 2 1 -7 3 4 1 2 -8 2 3 20 3 1 -1 3 2 -30 ``` ## Sample Output ``` -1 1 ``` ## Solution ```python from io import StringIO from typing import List, Dict, Union, Iterator from collections import deque def parse_integers(line: str) -> List[int]: return [int(num) for num in line.split()] def read_non_empty_line(input_iterator: Iterator[str]) -> str: line = next(input_iterator).strip() while not line: line = next(input_iterator).strip() return line def parse_graph(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]: node_count, edge_count = parse_integers(read_non_empty_line(input_iterator)) adjacency_list = {node: [] for node in range(1, node_count + 1)} for _ in range(edge_count): edge_data = parse_integers(read_non_empty_line(input_iterator)) if is_weighted: source, target, weight = edge_data adjacency_list[source].append({"node": target, "weight": weight}) if not is_directed: adjacency_list[target].append({"node": source, "weight": weight}) else: source, target = edge_data adjacency_list[source].append(target) if not is_directed: adjacency_list[target].append(source) return adjacency_list def parse_multiple_graphs(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> List[Dict[int, List[Union[int, Dict[str, int]]]]]: test_case_count = int(read_non_empty_line(input_iterator)) return [parse_graph(input_iterator, is_directed, is_weighted) for _ in range(test_case_count)] def count_edges(graph): edge_count = 0 for _, neighbors in graph.items(): for _ in neighbors: edge_count += 1 return edge_count def get_all_nodes(graph): source_nodes = list(graph.keys()) target_nodes = [neighbor["node"] for neighbors in graph.values() for neighbor in neighbors] return set(source_nodes) | set(target_nodes) def detect_negative_weight_cycle(graph): distances = {node: 10**20 for node in get_all_nodes(graph)} distances[1] = 0 for _ in range(count_edges(graph) - 1): for source, neighbors in graph.items(): for neighbor in neighbors: distances[neighbor["node"]] = min(distances[source] + neighbor["weight"], distances[neighbor["node"]]) for source, neighbors in graph.items(): for neighbor in neighbors: if distances[source] + neighbor["weight"] < distances[neighbor["node"]]: return 1 return -1 sample_input = """ 2 4 5 1 4 4 4 2 3 2 3 1 3 1 6 2 1 -7 3 4 1 2 -8 2 3 20 3 1 -1 3 2 -30 """ input_iterator = iter(StringIO(sample_input.strip()).readlines()) graphs = parse_multiple_graphs(input_iterator, is_directed=True, is_weighted=True) print(*[detect_negative_weight_cycle(graph) for graph in graphs]) ``` # Quick Sort Comparing the algorithms for [sorting](https://rosalind.info/glossary/algo-sorting-algorithm/) and [“Median”](https://rosalind.info/problems/med/) finding we notice that, beyond the common [divide-and-conquer](https://rosalind.info/glossary/algo-divide-and-conquer/) philosophy and structure, they are exact opposites. [“Merge Sort”](https://rosalind.info/problems/ms/) splits the array in two in the most convenient way (first half, second half), without any regard to the magnitudes of the elements in each half; but then it works hard to put the sorted subarrays together. In contrast, the median algorithm is careful about its splitting (smaller numbers first, then the larger ones), but its work ends with the recursive call. *Quick sort* is a sorting algorithm that splits the array in exactly the same way as the median algorithm; and once the subarrays are sorted, by two recursive calls, there is nothing more to do. Its worst-case performance is $Θ(n2)$, like that of median-finding. But it can be proved that its average case is $O(n \log ⁡n)$; furthermore, empirically it outperforms other sorting algorithms. This has made quicksort a favorite in many applications— for instance, it is the basis of the code by which really enormous files are sorted. Source: [Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006](https://rosalind.info/glossary/algo-algorithms-by-dasgupta-papadimitriou-vazirani-mcgraw-hill-2006/). Given: A positive integer $n≤10^5$ and an array A[1..n] of integers from $−10^5$ to $10^5$. Return: A sorted array A[1..n]. ## Sample Dataset ``` 7 5 -2 4 7 8 -10 11 ``` ## Sample Output ``` -10 -2 4 5 7 8 11 ``` ## Solution ```python from typing import List def parse_integers(input_line: str) -> List[int]: return [int(number) for number in input_line.split()] def three_way_partition(array: List[int], start: int = None, end: int = None) -> tuple: if start is None: start = 0 if end is None: end = len(array) - 1 pivot = array[start] current = start while current <= end: if array[current] < pivot: array[current], array[start] = array[start], array[current] current += 1 start += 1 elif array[current] > pivot: array[current], array[end] = array[end], array[current] end -= 1 else: current += 1 return start, end def quick_sort(array: List[int]): def quick_sort_recursive(array: List[int], start: int, end: int): if start < end: partition_start, partition_end = three_way_partition(array, start, end) if start < partition_start: quick_sort_recursive(array, start, partition_start - 1) if end > partition_end: quick_sort_recursive(array, partition_end + 1, end) quick_sort_recursive(array, 0, len(array) - 1) sample_input = """ 7 5 -2 4 7 8 -10 11 """ _, input_numbers = sample_input.strip().split("\n") numbers = parse_integers(input_numbers) # Convert the input string to a list of integers quick_sort(numbers) print(*numbers) ``` # Strongly Connected Components Given: A [simple directed graph](https://rosalind.info/glossary/algo-simple-directed-graph/) with $n≤10^3$ vertices in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/). Return: The number of [strongly connected components](https://rosalind.info/glossary/algo-strongly-connected-component/) in the graph. ## Sample Dataset ``` 6 7 4 1 1 2 2 4 5 6 3 2 5 3 3 5 ``` ## Sample Output ``` 3 ``` ## Solution ```python from collections import defaultdict from typing import List, Dict, Set, Union, Iterator from io import StringIO Graph = Dict[int, List[Union[int, Dict[str, int]]]] def parse_integers(line: str) -> List[int]: return [int(num) for num in line.split()] def read_non_empty_line(input_iterator: Iterator[str]) -> str: return next(line.strip() for line in input_iterator if line.strip()) def parse_graph(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Graph: node_count, edge_count = parse_integers(read_non_empty_line(input_iterator)) graph = {n: [] for n in range(1, node_count + 1)} for _ in range(edge_count): edge = parse_integers(read_non_empty_line(input_iterator)) if is_weighted: source, target, weight = edge graph[source].append({"n": target, "w": weight}) if not is_directed: graph[target].append({"n": source, "w": weight}) else: source, target = edge graph[source].append(target) if not is_directed: graph[target].append(source) return graph def get_graph_nodes(graph: Graph) -> Set[int]: return set(graph.keys()) def topological_sort(graph: Graph) -> List[int]: def dfs(node: int, visited: Set[int], stack: List[int]): visited.add(node) for neighbor in graph[node]: if neighbor not in visited: dfs(neighbor, visited, stack) stack.append(node) visited: Set[int] = set() stack: List[int] = [] for node in get_graph_nodes(graph): if node not in visited: dfs(node, visited, stack) return stack[::-1] def find_component(start_node: int, graph: Graph) -> Set[int]: def visit(node: int, visited: Set[int]) -> Set[int]: visited.add(node) for neighbor in set(graph[node]) - visited: visit(neighbor, visited) return visited return visit(start_node, set()) def reverse_graph(graph: Graph) -> Graph: reversed_graph = defaultdict(list) for node in graph: for child in graph[node]: reversed_graph[child].append(node) return reversed_graph def strongly_connected_components(graph: Graph) -> Iterator[Set[int]]: order = topological_sort(graph) reversed_graph = reverse_graph(graph) while order: node = order.pop(0) component = find_component(node, reversed_graph) order = [x for x in order if x not in component] for key in reversed_graph.keys(): reversed_graph[key] = [n for n in reversed_graph[key] if n not in component] yield component sample_input = """ 6 7 4 1 1 2 2 4 5 6 3 2 5 3 3 5 """ input_iterator = iter(StringIO(sample_input.strip()).readlines()) graph = parse_graph(input_iterator, is_directed=True) print(len(list(strongly_connected_components(graph)))) ``` # 2-Satisfiability In the 2SAT problem, you are given a set of *clauses*, where each clause is the dis-junction (OR) of two literals (a literal is a Boolean variable or the negation of a Boolean variable). You are looking for a way to assign a value true or false to each of the variables so that all clauses are satisfied — that is, there is at least one true literal in each clause. For example, here's an instance of 2SAT: $$(x1 \lor \bar x2 \land (\bar x1 \lor \bar x3) \land (x1 \lor x2) \land (\bar x3 \lor x4)\land(\bar x1 \lor x4).$$ This instance has a satisfying assignment: set x1, x2, x3, and x4 to true, false, false, and true, respectively. 1. Are there other satisfying truth assignments of this 2SAT formula? If so, find them all. 2. Give an instance of 2SAT with four variables, and with no satisfying assignment. The purpose of this problem is to lead you to a way of solving 2SAT efficiently by reducing it to the problem of finding the [strongly connected components](https://rosalind.info/glossary/algo-strongly-connected-component/) of a directed graph. Given an instance I of 2SAT with nn variables and mm clauses, construct a directed graph $GI=(V,E)$ as follows. - $GI$ has $2n$ nodes, one for each variable and its negation. - $GI$ has $2m$ edges: for each clause ($α∨β)$ of I (where $α,β$ are literals), $GI$ has an edge from the negation of $α$ to $β$, and one from the negation of $β$ to $α$. Note that the clause $(α∨β)$ is equivalent to either of the implications $\bar α⇒β$ or $\bar β⇒α$. In this sense, $GI$ records all implications in I. 4. Carry out this construction for the instance of 2SAT given above, and for the instance you constructed in 2. 5. Show that if $GI$ has a strongly connected component containing both $x$ and $\bar x$ for some variable $x$, then I has no satisfying assignment. 6. Now show the converse of 4: namely, that if none of $GI$'s strongly connected components contain both a literal and its negation, then the instance I must be satisfiable. (Hint: Assign values to the variables as follows: repeatedly pick a sink strongly connected component of $GI$. Assign value true to all literals in the sink, assign false to their negations, and delete all of these. Show that this ends up discovering a satisfying assignment.) 7. Conclude that there is a [linear-time](https://rosalind.info/glossary/algo-linear/) algorithm for solving 2SAT. Source: [Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006](https://rosalind.info/glossary/algo-algorithms-by-dasgupta-papadimitriou-vazirani-mcgraw-hill-2006/). Given: A positive integer $k≤20$ and k 2SAT formulas represented as follows. The first line gives the number of variables $n≤10^3$ and the number of clauses $m≤10^4$, each of the following mm lines gives a clause of length 2 by specifying two different literals: e.g., a clause $(x3 ∨ \bar x5)$ is given by `3 -5`. Return: For each formula, output 0 if it cannot be satisfied or 11 followed by a satisfying assignment otherwise. ## Sample Dataset ``` 2 2 4 1 2 -1 2 1 -2 -1 -2 3 4 1 2 2 3 -1 -2 -2 -3 ``` ## Sample Output ``` 0 1 1 -2 3 ``` ## Solution ```python import sys from collections import defaultdict from io import StringIO def parse_integers(line): return list(map(int, line.split())) class RecursionLimitManager: def __init__(self, new_limit): self.new_limit = new_limit def __enter__(self): self.old_limit = sys.getrecursionlimit() sys.setrecursionlimit(self.new_limit) def __exit__(self, exc_type, exc_value, traceback): sys.setrecursionlimit(self.old_limit) def reverse_graph(original_graph): reversed_graph = defaultdict(list) for node in original_graph: for neighbor in original_graph[node]: reversed_graph[neighbor].append(node) return reversed_graph def find_strongly_connected_components(graph): node_order = topological_sort(graph) reversed_graph = reverse_graph(graph) while node_order: start_node = node_order.pop(0) component = find_component(start_node, reversed_graph) node_order = [node for node in node_order if node not in component] for key in reversed_graph.keys(): reversed_graph[key] = [node for node in reversed_graph[key] if node not in component] yield component def find_component_index(node, components): for index, component in enumerate(components): if node in component: return index def condense_graph(original_graph, components): condensed_graph = {} for index, component in enumerate(components): condensed_graph[index] = set( [ find_component_index(neighbor, components) for node in component for neighbor in original_graph[node] if neighbor not in component ] ) return condensed_graph def topological_sort(graph): def depth_first_search(node, visited_nodes, node_stack): visited_nodes[node] = True for neighbor in graph[node]: if not visited_nodes[neighbor]: depth_first_search(neighbor, visited_nodes, node_stack) node_stack.append(node) visited_nodes = defaultdict(bool) node_stack = [] for node in get_graph_nodes(graph): if not visited_nodes[node]: depth_first_search(node, visited_nodes, node_stack) return node_stack[::-1] def parse_2sat_instances(input_handle): instance_count = int(next(input_handle)) for _ in range(instance_count): yield parse_2sat_instance(input_handle) def parse_2sat_instance(input_handle): info = next(input_handle) if info == "\n": info = next(input_handle) variable_count, clause_count = parse_integers(info) clauses = [next(input_handle) for _ in range(clause_count)] implication_graph = {} for variable in range(1, variable_count + 1): implication_graph[variable] = list() implication_graph[-variable] = list() for clause in clauses: literal1, literal2 = parse_integers(clause) implication_graph[-literal1].append(literal2) implication_graph[-literal2].append(literal1) return implication_graph def solve_2sat(implication_graph): components = list(find_strongly_connected_components(implication_graph)) condensed_graph = condense_graph(implication_graph, components) for component_index in topological_sort(condensed_graph): for literal in components[component_index]: if -literal in components[component_index]: return 0, [] assignment = [] for component_index in reversed(topological_sort(condensed_graph)): for literal in components[component_index]: if literal not in assignment and -literal not in assignment: assignment.append(literal) return 1, sorted(assignment, key=lambda x: abs(x)) sample_input = """ 2 2 4 1 2 -1 2 1 -2 -1 -2 3 4 1 2 2 3 -1 -2 -2 -3 """ with RecursionLimitManager(5000): input_iterator = iter(StringIO(sample_input.strip()).readlines()) implication_graphs = parse_2sat_instances(input_iterator) for implication_graph in implication_graphs: is_satisfiable, satisfying_assignment = solve_2sat(implication_graph) print(is_satisfiable, *satisfying_assignment) ``` # General Sink Given: A positive integer k≤20 and k [simple directed graphs](https://rosalind.info/glossary/algo-simple-directed-graph/) with at most $10^3$ vertices and $2⋅10^3$ edges each in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/). Return: For each graph, output a vertex from which all other vertices are reachable (if such a vertex exists) and"-1"otherwise. Source: [Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006](https://rosalind.info/glossary/algo-algorithms-by-dasgupta-papadimitriou-vazirani-mcgraw-hill-2006/). ## Sample Dataset ``` 2 3 2 3 2 2 1 3 2 3 2 1 2 ``` ## Sample Output ``` 3 -1 ``` ## Solution ```python from collections import defaultdict from typing import List, Dict, Union, Iterator from io import StringIO Graph = Dict[int, List[Union[int, Dict[str, int]]]] def parse_integers(line: str) -> List[int]: return [int(num) for num in line.split()] def read_non_empty_line(input_iterator: Iterator[str]) -> str: return next(line.strip() for line in input_iterator if line.strip()) def parse_graph(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Graph: node_count, edge_count = parse_integers(read_non_empty_line(input_iterator)) graph = {node: [] for node in range(1, node_count + 1)} for _ in range(edge_count): edge = parse_integers(read_non_empty_line(input_iterator)) if is_weighted: source, target, weight = edge graph[source].append({"n": target, "w": weight}) if not is_directed: graph[target].append({"n": source, "w": weight}) else: source, target = edge graph[source].append(target) if not is_directed: graph[target].append(source) return graph def parse_multiple_graphs(input_iterator: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> List[Graph]: test_case_count = int(read_non_empty_line(input_iterator)) return [parse_graph(input_iterator, is_directed, is_weighted) for _ in range(test_case_count)] def bfs(graph: Graph, start_node=1) -> List[int]: node_count = len(graph) distances = [-1 for _ in range(node_count + 1)] distances[start_node] = 0 queue = [start_node] while queue: current_node = queue.pop(0) for neighbor in graph[current_node]: if distances[neighbor] == -1: queue.append(neighbor) distances[neighbor] = distances[current_node] + 1 return distances[1:] def find_good_start_node(graph: Graph) -> int: for node in graph: distances = bfs(graph, node) all_nodes_reachable = [distance >= 0 for distance in distances] if all(all_nodes_reachable): return node return -1 sample_input = """ 2 3 2 3 2 2 1 3 2 3 2 1 2 """ input_iterator = iter(StringIO(sample_input.strip()).readlines()) graphs = parse_multiple_graphs(input_iterator, is_directed=True) print(*[find_good_start_node(g) for g in graphs]) ``` # Semi-Connected Graph A directed graph is *semi-connected* if for all pairs of vertices i,j there is either a path from i to j or a path from j to i. Given: A positive integer k≤20 and k [simple directed graphs](https://rosalind.info/glossary/algo-simple-directed-graph/) with at most $10^3$ vertices each in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/). Return: For each graph, output"1"if the graph is semi-connected and"-1"otherwise. ## Sample Dataset ``` 2 3 2 3 2 2 1 3 2 3 2 1 2 ``` ## Sample Output ``` 1 -1 ``` ## Solution ```python import sys from collections import defaultdict def parse_integers(string): return list(map(int, string.split())) def create_graph(input_stream, is_directed=False, is_weighted=False): while True: try: graph_info = next(input_stream).strip() if graph_info: break except StopIteration: return None try: vertex_count, edge_count = parse_integers(graph_info) except ValueError: return None edge_list = [] for _ in range(edge_count): try: edge = next(input_stream).strip() if edge: edge_list.append(edge) except StopIteration: break adjacency_list = {v: [] for v in range(1, vertex_count + 1)} for edge in edge_list: if is_weighted: source, target, weight = parse_integers(edge) adjacency_list[source].append({"vertex": target, "weight": weight}) if not is_directed: adjacency_list[target].append({"vertex": source, "weight": weight}) else: source, target = parse_integers(edge) adjacency_list[source].append(target) if not is_directed: adjacency_list[target].append(source) return adjacency_list def parse_multiple_graphs(input_stream, is_directed=False, is_weighted=False): try: graph_count = int(next(input_stream).strip()) except (StopIteration, ValueError): return [] graph_list = [] for _ in range(graph_count): graph = create_graph(input_stream, is_directed=is_directed, is_weighted=is_weighted) if graph is not None: graph_list.append(graph) else: break return graph_list def reverse_graph(graph): reversed_graph = defaultdict(list) for vertex in graph: for neighbor in graph[vertex]: reversed_graph[neighbor].append(vertex) return reversed_graph def get_all_vertices(graph): vertex_set = set() for vertex, neighbors in graph.items(): vertex_set.add(vertex) vertex_set.update(neighbors) return vertex_set def topological_sort(graph): def dfs(vertex, visited, stack): visited[vertex] = True for neighbor in graph[vertex]: if not visited[neighbor]: dfs(neighbor, visited, stack) stack.append(vertex) visited = defaultdict(bool) stack = [] for vertex in get_all_vertices(graph): if not visited[vertex]: dfs(vertex, visited, stack) return stack[::-1] def find_connected_component(start_vertex, graph): def dfs(vertex, visited): visited.add(vertex) for neighbor in set(graph[vertex]) - visited: dfs(neighbor, visited) return visited return dfs(start_vertex, set()) def strongly_connected_components(graph): vertex_order = topological_sort(graph) reversed_graph = reverse_graph(graph) while vertex_order: start_vertex = vertex_order.pop(0) component = find_connected_component(start_vertex, reversed_graph) vertex_order = [v for v in vertex_order if v not in component] for vertex in reversed_graph.keys(): reversed_graph[vertex] = [v for v in reversed_graph[vertex] if v not in component] yield component def hamiltonian_dag(graph): sorted_vertices = topological_sort(graph) for v1, v2 in zip(sorted_vertices, sorted_vertices[1:]): if v2 not in graph[v1]: return [-1] return [1] + sorted_vertices def find_component_index(vertex, components): for index, component in enumerate(components): if vertex in component: return index def condense_graph(graph, components): condensed_graph = {} for i, component in enumerate(components): condensed_graph[i] = set( find_component_index(neighbor, components) for vertex in component for neighbor in graph[vertex] if neighbor not in component ) return condensed_graph def is_semi_connected(graph): components = list(strongly_connected_components(graph)) condensed_graph = condense_graph(graph, components) return -1 if hamiltonian_dag(condensed_graph) == [-1] else 1 sample_input = """ 2 3 2 3 2 2 1 3 2 3 2 1 2 """ input_lines = sample_input.strip().split("\n") input_iterator = iter(input_lines) graphs = parse_multiple_graphs(input_iterator, is_directed=True) print(*[is_semi_connected(g) for g in graphs]) ``` # Shortest Paths in DAG There are two subclasses of graphs that automatically exclude the possibility of negative cycles: graphs without negative edges, and graphs without cycles. We already know how to efficiently handle the former (see the problem [“Negative Weight Cycle”](https://rosalind.info/problems/nwc/)). We will now see how the single-source shortest-path problem can be solved in just [linear](https://rosalind.info/glossary/algo-linear/) time on [directed acyclic graphs](https://rosalind.info/glossary/algo-directed-acyclic-graph/). As before, we need to perform a sequence of updates (recall [Bellman-Ford algorithm](https://rosalind.info/glossary/algo-bellman-ford-algorithm/)) that includes every shortest path as a subsequence. The key source of efficiency is that >In any path of a DAG, the vertices appear in increasing linearized order. Therefore, it is enough to [linearize](https://rosalind.info/glossary/algo-topological-sorting/) (that is, topologically sort) the DAG by [depth-first search](https://rosalind.info/glossary/algo-depth-first-search/), and then visit the vertices in sorted order, updating the edges out of each. The algorithm is given below. Notice that our scheme doesn't require edges to be positive. In particular, we can find *longest paths* in a DAG by the same algorithm: just negate all edge lengths. Source: [Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006](https://rosalind.info/glossary/algo-algorithms-by-dasgupta-papadimitriou-vazirani-mcgraw-hill-2006/). Given: A weighted [DAG](https://rosalind.info/glossary/algo-directed-acyclic-graph/) with integer edge weights from $−10^3$ to $10^3$ and $n≤10^5$ vertices in the [edge list format](https://rosalind.info/glossary/algo-edge-list-format/). Return: An array D[1..n] where D[i] is the length of a shortest path from the vertex 1 to the vertex i (D[1]=0. If i is not reachable from 1 set D[i] to `x`. ## Sample Dataset ``` 5 6 2 3 4 4 3 -2 1 4 1 1 5 -3 2 4 -2 5 4 1 ``` ## Sample Output ``` 0 x -4 -2 -3 ``` ## Solution ```python from math import inf from typing import List, Dict, Set, Iterator, Union, Optional from collections import defaultdict def parse_integers(line: str) -> List[int]: return list(map(int, line.split())) def create_graph(input_stream: Iterator[str], is_directed: bool = False, is_weighted: bool = False) -> Dict[int, List[Union[int, Dict[str, int]]]]: graph_info = next(input_stream) if graph_info == "\n": graph_info = next(input_stream) vertex_count, edge_count = parse_integers(graph_info) edge_list = [next(input_stream) for _ in range(edge_count)] adjacency_list: Dict[int, List[Union[int, Dict[str, int]]]] = {v: [] for v in range(1, vertex_count + 1)} for edge in edge_list: if is_weighted: source, target, weight = parse_integers(edge) adjacency_list[source].append({"vertex": target, "weight": weight}) if not is_directed: adjacency_list[target].append({"vertex": source, "weight": weight}) else: source, target = parse_integers(edge) adjacency_list[source].append(target) if not is_directed: adjacency_list[target].append(source) return adjacency_list def get_all_vertices(graph: Dict[int, List[Union[int, Dict[str, int]]]]) -> Set[int]: vertex_set: Set[int] = set() for vertex, neighbors in graph.items(): vertex_set.add(vertex) vertex_set.update([n if isinstance(n, int) else n["vertex"] for n in neighbors]) return vertex_set def topological_sort(graph: Dict[int, List[int]]) -> List[int]: def depth_first_search(vertex: int, visited: Dict[int, bool], stack: List[int]) -> None: visited[vertex] = True for neighbor in graph[vertex]: if not visited[neighbor]: depth_first_search(neighbor, visited, stack) stack.append(vertex) visited: Dict[int, bool] = defaultdict(bool) stack: List[int] = [] for vertex in get_all_vertices(graph): if not visited[vertex]: depth_first_search(vertex, visited, stack) return stack[::-1] def simplify_graph(graph: Dict[int, List[Dict[str, int]]]) -> Dict[int, List[int]]: return {k: [x["vertex"] for x in v] for k, v in graph.items()} def shortest_distances_acyclic_graph(graph: Dict[int, List[Dict[str, int]]]) -> List[Union[str, int]]: vertex_count = len(graph) distances = [inf for _ in range(vertex_count + 1)] distances[1] = 0 topological_order = topological_sort(simplify_graph(graph)) for current_vertex in topological_order: seen_vertices = set() for edge in reversed(graph[current_vertex]): neighbor = edge["vertex"] if neighbor not in seen_vertices: seen_vertices.add(neighbor) if distances[current_vertex] + edge["weight"] < distances[neighbor]: distances[neighbor] = distances[current_vertex] + edge["weight"] return ["x" if d == inf else d for d in distances[1:]] sample_input = """ 5 6 2 3 4 4 3 -2 1 4 1 1 5 -3 2 4 -2 5 4 1 """ input_lines: List[str] = sample_input.strip().split("\n") input_iterator: Iterator[str] = iter(input_lines) result = shortest_distances_acyclic_graph(create_graph(input_iterator, is_directed=True, is_weighted=True)) print(*result) ```