The 2025-2026 ICPC RSU Northeast Oklahoma Provincial Programming Contest

Problem Statement

Implement Breadth-First Search (BFS) and Depth-First Search (DFS) traversal for a given adjacency list representation of a graph.

Input

The first line contains two integers V and E, representing the number of vertices and edges respectively. The next E lines each contain two integers representing an edge between two vertices. The last line contains an integer S representing the starting vertex.

Output

Two lines: first line shows the BFS traversal order, second line shows the DFS traversal order.

Sample Input

4 3
0 1
0 2
1 3
0

Sample Output

0 1 2 3
0 1 3 2

Solution Approach

For BFS, use a queue to visit nodes level by level. For DFS, use recursion or a stack to visit nodes as deep as possible before backtracking.

Problem Statement

Implement binary search to find an element in a sorted array of integers.

Input

The first line contains an integer N, the size of the array. The second line contains N space-separated integers representing the sorted array. The third line contains an integer T, the target value to search for.

Output

The index of the target value if found, or -1 if not found.

Sample Input

5
1 3 5 7 9
5

Sample Output

2

Solution Approach

Binary search works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half.

Problem Statement

Find the shortest path between two nodes in a weighted graph using Dijkstra's algorithm.

Input

The first line contains two integers V and E, representing the number of vertices and edges respectively. The next E lines each contain three integers representing an edge between two vertices and its weight. The last line contains two integers S and D representing the source and destination vertices.

Output

The shortest distance from S to D.

Sample Input

4 4
0 1 24
0 3 20
1 3 3
3 2 12
0 2

Sample Output

35

Solution Approach

Dijkstra's algorithm uses a priority queue to always expand the least-cost node first. Maintain distances to all nodes and update them when a shorter path is found.

Problem Statement

Implement the merge sort algorithm to sort an array of integers.

Input

The first line contains an integer N, the size of the array. The second line contains N space-separated integers representing the array to be sorted.

Output

The sorted array in ascending order.

Sample Input

5
5 4 3 2 1

Sample Output

1 2 3 4 5

Solution Approach

Merge sort is a divide-and-conquer algorithm that divides the input array into two halves, sorts them recursively, and then merges the two sorted halves.

Problem Statement

Solve the classic 0/1 knapsack problem using dynamic programming techniques.

Input

The first line contains two integers N and W, representing the number of items and the maximum weight capacity. The next N lines each contain two integers representing the weight and value of each item.

Output

The maximum value that can be obtained without exceeding the weight capacity.

Sample Input

3 50
10 60
20 100
30 120

Sample Output

220

Solution Approach

Create a 2D DP table where dp[i][w] represents the maximum value that can be obtained with the first i items and weight limit w. Fill the table by considering whether to include or exclude each item.

Problem Statement

Implement AVL tree insertion and balancing operations.

Input

The first line contains an integer N, the number of values to insert. The second line contains N space-separated integers to be inserted into the AVL tree.

Output

The level order traversal of the constructed AVL tree.

Sample Input

7
30 20 40 10 25 50 5

Sample Output

20 10 30 5 25 40 50

Solution Approach

After each insertion, check the balance factor of each node and perform rotations (LL, RR, LR, RL) as needed to maintain the AVL property.