Cpbook Code

https://github.com/stevenhalim/cpbook-code
Admin
A repository providing up-to-date free source code implementations of well-known data structures and...
Tokens:5,253
Snippets:21
Trust Score:8
Update:10 months ago
Show doc for...
Tokens:
Raw
### QuickSelect for k-th Order Statistic - Python

Source: https://context7.com/stevenhalim/cpbook-code/llms.txt

Implements the QuickSelect algorithm to find the k-th smallest element in an array in expected O(n) time. It uses a randomized partitioning strategy. The function takes an array, start and end indices, and the desired rank 'k' as input. It recursively partitions the array until the k-th element is found.

```python
import random

def partition(a, i, j):
    p = random.randint(i, j)
    a[p], a[j] = a[j], a[p]
    pivot = a[j]
    s = i - 1
    for k in range(i, j):
        if a[k] <= pivot:
            s += 1
            a[s], a[k] = a[k], a[s]
    a[s+1], a[j] = a[j], a[s+1]
    return s + 1

def quick_select(a, i, j, k):
    if i == j:
        return a[i]

    p = partition(a, i, j)
    m = p - i + 1

    if k == m:
        return a[p]
    elif k < m:
        return quick_select(a, i, p-1, k)
    else:
        return quick_select(a, p+1, j, k-m)

# Usage example
arr = [7, 4, 6, 3, 9, 1]
print(quick_select(arr, 0, len(arr)-1, 1))  # 1 (smallest)
print(quick_select(arr, 0, len(arr)-1, 3))  # 4 (3rd smallest)
print(quick_select(arr, 0, len(arr)-1, 6))  # 9 (largest)

# Find median
arr = [7, 4, 6, 3, 9, 1, 8]
median = quick_select(arr, 0, len(arr)-1, (len(arr)+1)//2)
print(median)  # 6
```

--------------------------------

### Python Input/Output Handling Patterns

Source: https://context7.com/stevenhalim/cpbook-code/llms.txt

Demonstrates various Python patterns for reading input from standard input, tailored for different test case formats common in competitive programming. Includes reading fixed test cases, sentinel values, numbered cases, and variable-length records.

```python
import sys
inputs = iter(sys.stdin.readlines())
TC = int(next(inputs))
for _ in range(TC):
    print(sum(map(int, next(inputs).split())))

import sys
for line in sys.stdin.readlines():
    if line == '0 0\n': break
    print(sum(map(int, line.split())))

import sys
for c, line in enumerate(sys.stdin.readlines(), 1):
    print("Case %s: %s" % (c, sum(map(int, line.split()))))

import sys
for line in sys.stdin.readlines():
    print(sum(map(int, line.split()[1:])))  # skip the first integer
```

--------------------------------

### Priority Queue (Max Heap) with Python heapq

Source: https://context7.com/stevenhalim/cpbook-code/llms.txt

Implements a max heap priority queue using Python's heapq module. By negating numerical values, heapq (which is a min heap by default) can simulate a max heap. This is useful for scenarios where the highest priority (largest value) elements need to be extracted first. Operations like insertion and extraction take O(log n) time.

```python
import heapq

pq = []
# Python heapq is min heap by default, negate values for max heap
pq.append((-100, "john"))
pq.append((-10, "billy"))
pq.append((-20, "andy"))
pq.append((-100, "steven"))
pq.append((-70, "felix"))
pq.append((-2000, "grace"))
pq.append((-70, "martin"))

# Convert list to heap structure
heapq.heapify(pq)

# Extract top 3 elements (highest money first)
result = heapq.heappop(pq)  # O(log n) to extract and repair
print('{:s} has {:d} $'.format(result[1], -result[0]))  # grace has 2000 $

result = heapq.heappop(pq)
print('{:s} has {:d} $'.format(result[1], -result[0]))  # steven has 100 $

result = heapq.heappop(pq)
print('{:s} has {:d} $'.format(result[1], -result[0]))  # john has 100 $

# When first keys tie, second key determines order
# Insert new element
heapq.heappush(pq, (-150, "alice"))
```

--------------------------------

### Java AVL Tree Implementation

Source: https://context7.com/stevenhalim/cpbook-code/llms.txt

A full Java implementation of an AVL tree, a self-balancing binary search tree. It supports insertion, deletion, search, finding minimum and maximum elements, inorder traversal, and successor/predecessor queries. The tree automatically rebalances to maintain logarithmic height.

```java
import java.util.*;

AVL tree = new AVL();
int[] arr = {15, 32, 100, 6, 23, 4, 7, 71, 5, 50, 3, 1};

// Insert elements
for (int val : arr) {
    tree.insert(val);
}

// Tree remains balanced with height 3 (vs 4 for regular BST)
System.out.println(tree.getHeight());  // 3

// Search operations
System.out.println(tree.search(71));    // 71 (found)
System.out.println(tree.search(22));    // -1 (not found)

// Find min and max
System.out.println(tree.findMin());     // 1
System.out.println(tree.findMax());     // 100

// Inorder traversal (sorted order)
tree.inorder();  // 1 3 4 5 6 7 15 23 32 50 71 100

// Successor and predecessor queries
System.out.println(tree.successor(7));      // 15
System.out.println(tree.predecessor(32));   // 23

// Delete operations (tree rebalances automatically)
tree.delete(23);
tree.delete(100);
System.out.println("Height after deletions: " + tree.getHeight());
tree.inorder();  // 1 3 4 5 6 7 15 32 50 71
```

--------------------------------

### Python Array Sorting and Searching

Source: https://context7.com/stevenhalim/cpbook-code/llms.txt

Demonstrates standard Python array operations including sorting in descending order, binary search using `bisect_left`, finding minimum and maximum values, and multi-field sorting using tuples. These are fundamental for efficient data manipulation.

```python
import bisect

# Sort descending
arr = [10, 7, 2, 15, 4]
arr.sort()
arr.reverse()
for val in arr:
    print(val, end=' ')  # Output: 15 10 7 4 2

# Binary search using lower bound
arr = [2, 4, 7, 10, 15]
i = bisect.bisect_left(arr, 7)  # Returns 2, element found at index 2

j = bisect.bisect_left(arr, 77)  # Element not found
if j == len(arr):
    print("77 not found")

# Min and max operations
print("min(10, 7) = {}".format(min(10, 7)))  # 7
print("max(10, 7) = {}".format(max(10, 7)))  # 10

# Multi-field sorting with tuples
teams = [
    (1, 10, "team_a"),
    (3, 60, "team_b"),
    (1, 20, "team_c"),
    (3, 60, "team_d")
]
# Sorts by number of problems (desc), then penalty (asc), then name
teams.sort(key=lambda x: (-x[0], x[1], x[2]))
```

--------------------------------

### Longest Increasing Subsequence (LIS) - Python

Source: https://context7.com/stevenhalim/cpbook-code/llms.txt

Implements the Longest Increasing Subsequence (LIS) algorithm using dynamic programming and binary search for O(n log n) time complexity. It finds the length of the LIS and reconstructs one such subsequence. Dependencies include the `bisect` module. Inputs are an array and its size, and it outputs the LIS.

```python
from bisect import *

MAX_N = 100000

def reconstruct_print(end, a, p):
    x = end
    s = []
    while p[x] >= 0:
        s.append(a[x])
        x = p[x]
    s.append(a[x])
    print('[' + ', '.join(map(str, s[::-1])) + ']')

n = 11
A = [-7, 10, 9, 2, 3, 8, 8, 1, 2, 3, 4]

L = [None] * MAX_N
L_id = [None] * MAX_N
P = [None] * MAX_N
lis = lis_end = 0

for i in range(n):
    pos = bisect_left(L, A[i], 0, lis)
    L[pos] = A[i]
    L_id[pos] = i
    P[i] = L_id[pos-1] if pos else -1
    if pos+1 > lis:
        lis = pos+1
        lis_end = i
    print('Considering element A[{}] = {}'.format(i, A[i]))
    print('LIS ending at A[{}] is of length {}: '.format(i, pos+1), end='')
    reconstruct_print(i, A, P)
    print('L is now: [' + ', '.join(map(str, L[:lis])) + ']\n')

print('Final LIS is of length {}: '.format(lis), end='')
reconstruct_print(lis_end, A, P)
```

--------------------------------

### Union-Find Disjoint Set (UFDS) with Path Compression and Union by Rank

Source: https://context7.com/stevenhalim/cpbook-code/llms.txt

A Python implementation of the Union-Find Disjoint Set (UFDS) data structure. It uses path compression and union by rank (or size) optimizations to achieve near-constant time complexity for its operations on average. This structure is ideal for problems involving partitioning elements into disjoint sets and efficiently checking connectivity or merging sets.

```python
class UFDS:
    def __init__(self, n):
        self.parents = list(range(n))
        self.ranks = [0] * n
        self.sizes = [1] * n
        self.numdisjoint = n

    def find(self, x):
        xp = x
        children = []
        while xp != self.parents[xp]:
            children.append(xp)
            xp = self.parents[xp]
        for c in children:  # path compression
            self.parents[c] = xp
        return xp

    def union(self, a, b):
        ap = self.find(a)
        bp = self.find(b)
        if ap == bp:
            return

        if self.ranks[ap] < self.ranks[bp]:
            self.parents[ap] = bp
            self.sizes[bp] += self.sizes[ap]
        elif self.ranks[bp] < self.ranks[ap]:
            self.parents[bp] = ap
            self.sizes[ap] += self.sizes[bp]
        else:
            self.parents[bp] = ap
            self.ranks[ap] += 1
            self.sizes[ap] += self.sizes[bp]

        self.numdisjoint -= 1

    def size(self, x):
        return self.sizes[self.find(x)]

# Usage example
u = UFDS(8)
print(u.numdisjoint)  # 8 (initially 8 disjoint sets)

u.union(1, 2)
print(u.find(1) == u.find(2))  # True
print(u.find(1) != u.find(3))  # True
print(u.size(1))               # 2
print(u.numdisjoint)           # 7

u.union(1, 3)
print(u.size(1))      # 3
print(u.numdisjoint)  # 6

u.union(2, 4)
print(u.size(1))      # 4
print(u.numdisjoint)  # 5

# Check if elements are in same set
print(u.find(1) == u.find(4))  # True
print(u.find(1) == u.find(5))  # False
```

--------------------------------

### Fenwick Tree (Binary Indexed Tree) for Range Queries

Source: https://context7.com/stevenhalim/cpbook-code/llms.txt

Provides an efficient implementation of a Fenwick Tree (Binary Indexed Tree) in Python. This data structure supports both point updates and range sum queries in O(log n) time. It also includes functionality for 'select', which finds the index of a given cumulative sum, and variations for Range Update Point Query (RUPQ) and Range Update Range Query (RURQ).

```python
class FTree:
    def __init__(self, f):
        self.n = len(f)
        self.ft = [0] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.ft[i] += f[i - 1]
            if i + self.lsone(i) <= self.n:
                self.ft[i + self.lsone(i)] += self.ft[i]

    def lsone(self, s):
        return s & (-s)

    def query(self, i, j):
        if i > 1:
            return self.query(1, j) - self.query(1, i - 1)
        s = 0
        while j > 0:
            s += self.ft[j]
            j -= self.lsone(j)
        return s

    def update(self, i, v):
        while i <= self.n:
            self.ft[i] += v
            i += self.lsone(i)

    def select(self, k):
        p = 1
        while (p * 2) <= self.n: p *= 2
        i = 0
        while p > 0:
            if k > self.ft[i + p]:
                k -= self.ft[i + p]
                i += p
            p //= 2
        return i + 1

# Usage example
f = [0, 1, 0, 1, 2, 3, 2, 1, 1, 0]
ft = FTree(f)
print(ft.query(1, 6))  # 7 (sum from index 1 to 6)
print(ft.query(1, 3))  # 1 (sum from index 1 to 3)
print(ft.select(7))    # 6 (index where cumulative sum reaches 7)
ft.update(5, 1)        # add 1 to index 5
print(ft.query(1, 10)) # 12 (new total sum)

# Range Update Point Query (RUPQ)
r = RUPQ(10)
r.update(2, 9, 7)   # add 7 to range [2, 9]
r.update(6, 7, 3)   # add 3 to range [6, 7]
print(r.query(6))   # 10 (7 + 3)
print(r.query(8))   # 7

# Range Update Range Query (RURQ)
rr = RURQ(10)
rr.update(2, 9, 7)
rr.update(6, 7, 3)
print(rr.query(3, 5))  # 21
print(rr.query(7, 8))  # 17
```

--------------------------------

### Floyd-Warshall All-Pairs Shortest Path - Python

Source: https://context7.com/stevenhalim/cpbook-code/llms.txt

Implements the Floyd-Warshall algorithm to find the shortest paths between all pairs of vertices in a graph. It has a time complexity of O(V³). The function takes the number of vertices and a list of edges (u, v, w) as input and returns an adjacency matrix containing the shortest path distances. An INF value is used for unreachable paths.

```python
def floyd_warshall(V, edges):
    INF = int(1e9)
    MAX_V = 450

    AM = [[INF for j in range(MAX_V)] for i in range(MAX_V)]

    # Initialize diagonal to 0
    for u in range(V):
        AM[u][u] = 0

    # Read edges: (u, v, w) means edge from u to v with weight w
    for u, v, w in edges:
        AM[u][v] = w  # directed graph

    # Floyd-Warshall algorithm
    for k in range(V):  # intermediate vertex
        for u in range(V):
            for v in range(V):
                AM[u][v] = min(AM[u][v], AM[u][k] + AM[k][v])

    return AM

# Example usage
V = 5
edges = [
    (0, 1, 2),
    (0, 2, 1),
    (0, 4, 3),
    (1, 3, 4),
    (2, 1, 1),
    (2, 4, 1),
    (3, 0, 1),
    (3, 2, 3),
    (3, 4, 5)
]

AM = floyd_warshall(V, edges)
for u in range(V):
    for v in range(V):
        print("APSP({}, {}) = {}".format(u, v, AM[u][v]))
```

--------------------------------

### Python Bit Manipulation Functions

Source: https://context7.com/stevenhalim/cpbook-code/llms.txt

Provides a set of utility functions for common bitwise operations in Python, essential for efficient set manipulation and arithmetic. Includes functions for checking/setting/clearing/toggling bits, finding the lowest set bit, and checking for powers of two.

```python
import math

def isOn(S, j):
    return (S & (1<<j))

def setBit(S, j):
    return (S | (1<<j))

def clearBit(S, j):
    return (S & (~(1<<j)))

def toggleBit(S, j):
    return (S ^ (1<<j))

def lowBit(S):
    return (S&(-S))

def setAll(n):
    return ((1<<n)-1)

def modulo(S, N):  # returns S % N, where N is a power of 2
    return ((S) & (N-1))

def isPowerOfTwo(S):
    return (not(S & (S - 1)))

def turnOffLastBit(S):
    return (S & (S - 1))

# Usage examples
S = 34
print("S = {} = {:b}".format(S, S))
S = setBit(S, 3)
print("S = {} = {:b}".format(S, S))

# Multiply by 2 using left shift, divide by 4 using right shift
S = 34
S = S << 1  # multiply by 2
S = S >> 2  # divide by 4

# Check if bit is on
S = 42
T = isOn(S, 3)
print("T = {}, {}".format(T, "ON" if T else "OFF"))

# Find lowest set bit (useful for Fenwick trees)
S = 40
T = lowBit(S)
print("T = {} (always a power of 2)".format(T))

# Turn on all bits in a set of size n
S = setAll(6)  # S = 63 = 111111 in binary

# Check power of two and find nearest
print("is {} power of two? {}".format(8, isPowerOfTwo(8)))
# Assuming nearestPowerOfTwo is defined elsewhere for this example
# print("Nearest power of two of {} is {}".format(13, nearestPowerOfTwo(13)))
```
Tokens:
Raw