COMPETITIVE PROGRAMMING TASKS 2 (Questions and Solutions(IOI Standard))
Here are a few example tasks from the International Olympiad in Informatics (IOI) style, along with brief
solutions:
### Example Task 1: Shortest Path in a Graph
**Problem**: Given a directed graph with weighted edges, find the shortest path from a starting node
to a target node.
**Input**:
- The first line contains two integers, \( n \) (number of nodes) and \( m \) (number of edges).
- The next \( m \) lines each contain three integers \( u \), \( v \), and \( w \) (an edge from \( u \) to \( v \)
with weight \( w \)).
- The last line contains two integers, \( s \) (start node) and \( t \) (target node).
**Output**: The length of the shortest path from \( s \) to \( t \), or "NO PATH" if no path exists.
**Solution**:
Use Dijkstra's algorithm for finding the shortest path.
```python
import heapq
def dijkstra(n, edges, start, end):
graph = [[] for _ in range(n)]
for u, v, w in edges:
graph[u].append((v, w))
dist = [float('inf')] * n
dist[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_dist, current_node = heapq.heappop(priority_queue)
if current_dist > dist[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_dist + weight
if distance < dist[neighbor]:
dist[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return dist[end] if dist[end] < float('inf') else "NO PATH"
# Example usage:
n=5
edges = [(0, 1, 10), (0, 2, 5), (1, 2, 2), (1, 3, 1), (2, 1, 3), (2, 3, 9), (2, 4, 2), (4, 3, 6)]
start, end = 0, 3
print(dijkstra(n, edges, start, end))
```
### Example Task 2: Knapsack Problem
**Problem**: Given a list of items, each with a weight and a value, determine the maximum value that
can be obtained with a knapsack of capacity \( W \).
**Input**:
- The first line contains two integers, \( n \) (number of items) and \( W \) (maximum weight).
- The next \( n \) lines each contain two integers, \( w_i \) (weight) and \( v_i \) (value).
**Output**: The maximum value that can be carried.
**Solution**:
Use dynamic programming to solve the 0/1 knapsack problem.
```python
def knapsack(n, W, items):
dp = [0] * (W + 1)
for weight, value in items:
for j in range(W, weight - 1, -1):
dp[j] = max(dp[j], dp[j - weight] + value)
return dp[W]
# Example usage:
n=3
W=5
items = [(1, 1), (2, 2), (3, 5)]
print(knapsack(n, W, items))
```
### Example Task 3: Counting Inversions
**Problem**: Given an array of integers, count the number of inversions in the array. An inversion is
defined as a pair of indices \( (i, j) \) such that \( i < j \) and \( arr[i] > arr[j] \).
**Input**:
- The first line contains an integer \( n \) (size of the array).
- The second line contains \( n \) integers.
**Output**: The number of inversions.
**Solution**:
Use a modified merge sort to count inversions.
```python
def merge_and_count(arr, temp_arr, left, mid, right):
i = left # Starting index for left subarray
j = mid + 1 # Starting index for right subarray
k = left # Starting index to be sorted
inv_count = 0
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp_arr[k] = arr[i]
i += 1
else:
temp_arr[k] = arr[j]
inv_count += (mid - i + 1) # There are mid - i inversions
j += 1
k += 1
while i <= mid:
temp_arr[k] = arr[i]
i += 1
k += 1
while j <= right:
temp_arr[k] = arr[j]
j += 1
k += 1
for i in range(left, right + 1):
arr[i] = temp_arr[i]
return inv_count
def merge_sort_and_count(arr, temp_arr, left, right):
inv_count = 0
if left < right:
mid = (left + right) // 2
inv_count += merge_sort_and_count(arr, temp_arr, left, mid)
inv_count += merge_sort_and_count(arr, temp_arr, mid + 1, right)
inv_count += merge_and_count(arr, temp_arr, left, mid, right)
return inv_count
# Example usage:
arr = [1, 20, 6, 4, 5]
n = len(arr)
temp_arr = [0] * n
print(merge_sort_and_count(arr, temp_arr, 0, n - 1))
```
These examples illustrate various common algorithmic problems. If you need more tasks or different
types, feel free to ask!
Here are some additional tasks that resemble those you might find in the International Olympiad in
Informatics (IOI), along with their solutions:
### Example Task 4: Longest Increasing Subsequence
**Problem**: Given an array of integers, find the length of the longest increasing subsequence.
**Input**:
- The first line contains an integer \( n \) (size of the array).
- The second line contains \( n \) integers.
**Output**: The length of the longest increasing subsequence.
**Solution**:
Use dynamic programming with binary search for efficient calculation.
```python
import bisect
def longest_increasing_subsequence(arr):
lis = []
for x in arr:
pos = bisect.bisect_left(lis, x)
if pos == len(lis):
lis.append(x)
else:
lis[pos] = x
return len(lis)
# Example usage:
arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print(longest_increasing_subsequence(arr))
```
### Example Task 5: Maximum Subarray Sum (Kadane’s Algorithm)
**Problem**: Given an array of integers, find the maximum sum of a contiguous subarray.
**Input**:
- The first line contains an integer \( n \) (size of the array).
- The second line contains \( n \) integers.
**Output**: The maximum sum of a contiguous subarray.
**Solution**:
Use Kadane’s algorithm for an efficient solution.
```python
def max_subarray_sum(arr):
max_so_far = max_ending_here = arr[0]
for x in arr[1:]:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
# Example usage:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(arr))
```
### Example Task 6: Coin Change Problem
**Problem**: Given a list of coin denominations and a total amount, determine the number of ways to
make change for that amount using the coins.
**Input**:
- The first line contains two integers, \( n \) (number of denominations) and \( amount \) (the total
amount).
- The second line contains \( n \) integers representing the denominations.
**Output**: The number of ways to make change for the amount.
**Solution**:
Use dynamic programming to solve the coin change problem.
```python
def coin_change(denominations, amount):
dp = [0] * (amount + 1)
dp[0] = 1 # There is one way to make zero amount
for coin in denominations:
for x in range(coin, amount + 1):
dp[x] += dp[x - coin]
return dp[amount]
# Example usage:
denominations = [1, 2, 5]
amount = 5
print(coin_change(denominations, amount))
```
### Example Task 7: 0-1 Knapsack Problem
**Problem**: Given weights and values of \( n \) items, and a maximum capacity \( W \), determine the
maximum value that can be put in the knapsack.
**Input**:
- The first line contains two integers \( n \) and \( W \).
- The next \( n \) lines contain two integers each: \( w_i \) (weight) and \( v_i \) (value).
**Output**: The maximum value achievable with the given weights and values.
**Solution**:
This is a classic dynamic programming problem.
```python
def knapsack_01(n, W, items):
dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
weight, value = items[i - 1]
for w in range(W + 1):
if weight <= w:
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight] + value)
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]
# Example usage:
n=3
W=4
items = [(2, 3), (3, 4), (4, 5)]
print(knapsack_01(n, W, items))
```
### Example Task 8: Finding All Permutations
**Problem**: Given a string, generate all possible permutations of the string.
**Input**:
- A single line containing a string.
**Output**: All permutations of the string in lexicographical order.
**Solution**:
Use backtracking to generate permutations.
```python
def permute(s):
result = []
def backtrack(path, options):
if not options:
result.append(''.join(path))
return
for i in range(len(options)):
backtrack(path + [options[i]], options[:i] + options[i + 1:])
backtrack([], list(s))
return sorted(result)
# Example usage:
s = "abc"
print(permute(s))
```
These tasks demonstrate a variety of algorithmic concepts and approaches. If you’d like more examples
or specific types of tasks, let me know!
