Scribd
Upload
7 views2 pages

Dynamic Programming Practice Problems

The document presents three distinct problems related to algorithms and data structures. Problem 1 involves minimizing the cost of partitioning an array into segments using dynamic programming and optimization techniques. Problems 2 and 3 focus on performing range sum queries with point updates using a segment tree, and managing connected components in a graph using the Disjoint Set Union method, respectively.

Uploaded by

22ag1a6660
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views2 pages

Dynamic Programming Practice Problems

The document presents three distinct problems related to algorithms and data structures. Problem 1 involves minimizing the cost of partitioning an array into segments using dynamic programming and optimization techniques. Problems 2 and 3 focus on performing range sum queries with point updates using a segment tree, and managing connected components in a graph using the Disjoint Set Union method, respectively.

Uploaded by

22ag1a6660
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Problem 1: Minimum Cost to Partition (Dynamic Programming + Convex

Hull Trick or Divide & Conquer Optimization)

Problem Statement:​
You are given an array A of n integers. You want to partition it into k segments (1 ≤ k ≤ n), such
that the total cost is minimized. The cost of a segment [l, r] is defined as:

Cost(l, r) = (sum of elements from A[l] to A[r])²

Compute the minimum total cost to partition the array into exactly k segments.

Constraints:

●​ 1 ≤ n ≤ 10⁵​

●​ 1 ≤ k ≤ 100​

●​ 1 ≤ A[i] ≤ 1000​

Hint:

●​ Use DP: dp[i][j] = min over p < j of (dp[i-1][p] + cost(p+1, j))​

●​ The cost function is convex ⇒ optimize with Convex Hull Trick or Divide and Conquer
Optimization.​

Problem 2: Range Sum with Point Updates (Segment Tree)

Problem Statement:​
You are given an array A of size n. You have to perform two types of operations:

1.​ Update the value at index i to x.​

2.​ Query the sum of elements in the range [l, r].​

Input Format:

●​ First line: n and q (1 ≤ n, q ≤ 10⁵)​


●​ Second line: n integers, the initial array A​

●​ Next q lines:​

○​ 1 i x for update (0-based indexing)​

○​ 2 l r for range sum query​

Output:​
For each query of type 2, output the sum in a new line.

Hint:​
Use a Segment Tree with O(log n) time per operation.

Problem 3: Connected Components in a Graph (Disjoint Set Union /


Union-Find)

Problem Statement:​
You are given a graph with n nodes and m edges. The graph is initially empty. You will be given
a sequence of edges to add. After each edge is added, report the number of connected
components in the graph.

Input Format:

●​ First line: n and m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2×10⁵)​

●​ Next m lines: two integers u and v (1 ≤ u, v ≤ n)​

Output:​
Output m lines. Each line should contain the number of connected components after adding
that edge.

Hint:​
Use Disjoint Set Union (DSU) with path compression and union by rank for efficient merging.

You might also like