The 2025-2026 ICPC RSU Oklahoma - Asia Invitational Programming Contest

Problem Statement

Given a directed graph with weighted edges, implement an efficient algorithm to find the shortest path between all pairs of nodes (all-pairs shortest path). The graph may contain up to 10,000 nodes.

Input

The first line contains two integers N and M, the number of nodes and edges respectively. The next M lines each contain three integers u, v, and w, representing a directed edge from node u to node v with weight w.

Output

An N×N matrix where the entry at row i and column j represents the shortest distance from node i to node j. If no path exists, output INF.

Sample Input

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

Sample Output

0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0

Solution Approach

This problem requires implementing the Floyd-Warshall algorithm, which efficiently computes all-pairs shortest paths in O(N³) time. The algorithm works by considering each node as an intermediate point and updating the shortest paths accordingly.

Problem Statement

Given a sequence of numbers, find the length of the longest increasing subsequence (LIS). The sequence may contain up to 100,000 elements.

Input

The first line contains an integer N, the number of elements in the sequence. The second line contains N space-separated integers representing the sequence.

Output

A single integer representing the length of the longest increasing subsequence.

Sample Input

8
10 9 2 5 3 7 101 18

Sample Output

4

Solution Approach

This problem can be solved using dynamic programming with binary search to achieve O(N log N) time complexity. Maintain an array where each element represents the smallest possible tail value for all increasing subsequences of a given length.

Problem Statement

Given a set of points in 2D space, find the convex hull using Andrew's monotone chain algorithm. The input may contain up to 1,000,000 points.

Input

The first line contains an integer N, the number of points. The following N lines each contain two integers x and y, representing the coordinates of a point.

Output

The points that form the convex hull in counter-clockwise order, starting from the point with the smallest x-coordinate (and smallest y-coordinate if there are ties).

Sample Input

8
0 3
1 1
2 2
4 4
0 0
1 2
3 1
3 3

Sample Output

0 0
3 1
4 4
0 3

Solution Approach

Andrew's algorithm first sorts the points by x-coordinate (and y-coordinate in case of ties), then constructs the lower and upper parts of the hull. The algorithm runs in O(N log N) time due to the sorting step.

Problem Statement

Given a flow network with capacities on edges, compute the maximum flow from the source node to the sink node using the Dinic's algorithm.

Input

The first line contains four integers: N (number of nodes), M (number of edges), S (source node), and T (sink node). The following M lines each contain three integers u, v, and c, representing a directed edge from node u to node v with capacity c.

Output

A single integer representing the maximum flow from the source to the sink.

Sample Input

6 9 1 6
1 2 10
1 3 10
2 3 2
2 4 4
2 5 8
3 5 9
4 6 10
5 4 6
5 6 10

Sample Output

19

Solution Approach

Dinic's algorithm is an efficient maximum flow algorithm that uses BFS to construct level graphs and DFS to find blocking flows. It has a time complexity of O(V²E), which is faster than the Edmonds-Karp algorithm for many practical cases.

Problem Statement

Implement the Knuth-Morris-Pratt (KMP) algorithm to find all occurrences of a pattern in a text string. The text may be up to 10,000,000 characters long.

Input

The first line contains the pattern string. The second line contains the text string.

Output

All starting positions (0-based) where the pattern occurs in the text, separated by spaces.

Sample Input

ABABC
ABABABCABABCABABABABC

Sample Output

2 7 12

Solution Approach

The KMP algorithm preprocesses the pattern to create a partial match table (failure function) that allows skipping unnecessary comparisons. This results in O(N+M) time complexity where N is the text length and M is the pattern length.

Problem Statement

Implement a thread-safe queue that supports concurrent enqueue and dequeue operations using mutex locks and condition variables.

Input

A series of operations (ENQUEUE x or DEQUEUE) from multiple threads, where x is an integer.

Output

The sequence of dequeued values in the order they were removed from the queue.

Sample Input

Thread 1: ENQUEUE 1
Thread 2: ENQUEUE 2
Thread 3: DEQUEUE
Thread 1: ENQUEUE 3
Thread 2: DEQUEUE
Thread 3: DEQUEUE

Sample Output

1 2 3

Solution Approach

This problem requires implementing a concurrent queue with proper synchronization. Use a mutex to protect the queue from race conditions and condition variables to handle blocking when the queue is empty. The enqueue operation should signal waiting threads when adding an element to an empty queue.