Challenge - 5 Problems
Rod Cutting Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of Rod Cutting Recursive Function
What is the output of the following Rust code that uses recursion to solve the rod cutting problem for a rod of length 4?
DSA Rust
fn rod_cutting(prices: &[i32], n: usize) -> i32 {
if n == 0 {
return 0;
}
let mut max_val = i32::MIN;
for i in 1..=n {
let val = prices[i - 1] + rod_cutting(prices, n - i);
if val > max_val {
max_val = val;
}
}
max_val
}
fn main() {
let prices = [1, 5, 8, 9];
let n = 4;
let result = rod_cutting(&prices, n);
println!("{}", result);
}Attempts:
2 left
💡 Hint
Think about all possible ways to cut the rod and sum prices.
✗ Incorrect
The function tries all cuts from length 1 to n and picks the maximum sum of prices. For length 4, the best is cutting into lengths 2 and 2 (5 + 5 = 10).
❓ Predict Output
intermediate2:00remaining
Output of Bottom-Up Rod Cutting DP
What is the output of this Rust code using bottom-up dynamic programming for rod cutting with prices [2, 5, 7, 8] and rod length 4?
DSA Rust
fn rod_cutting(prices: &[i32], n: usize) -> i32 {
let mut dp = vec![0; n + 1];
for i in 1..=n {
let mut max_val = i32::MIN;
for j in 1..=i {
max_val = max_val.max(prices[j - 1] + dp[i - j]);
}
dp[i] = max_val;
}
dp[n]
}
fn main() {
let prices = [2, 5, 7, 8];
let n = 4;
let result = rod_cutting(&prices, n);
println!("{}", result);
}Attempts:
2 left
💡 Hint
Check all possible cuts and their sums stored in dp array.
✗ Incorrect
The best cut is two pieces of length 2 each priced at 5, total 10.
🔧 Debug
advanced2:00remaining
Identify the Error in Memoized Rod Cutting
What error will this Rust code produce when running the memoized rod cutting function?
DSA Rust
fn rod_cutting(prices: &[i32], n: usize, memo: &mut Vec<Option<i32>>) -> i32 {
if n == 0 {
return 0;
}
if let Some(val) = memo[n] {
return val;
}
let mut max_val = i32::MIN;
for i in 1..=n {
let val = prices[i - 1] + rod_cutting(prices, n - i, memo);
if val > max_val {
max_val = val;
}
}
memo[n] = Some(max_val);
max_val
}
fn main() {
let prices = [1, 5, 8, 9];
let n = 4;
let mut memo = vec![None; n + 1];
let result = rod_cutting(&prices, n, &mut memo);
println!("{}", result);
}Attempts:
2 left
💡 Hint
Check the size of memo vector and indexing.
✗ Incorrect
The memo vector has size n+1=5 and indexing uses memo[n], which is memo[4], valid since indices go 0..4.
🧠 Conceptual
advanced1:30remaining
Time Complexity of Rod Cutting DP
What is the time complexity of the bottom-up dynamic programming solution for the rod cutting problem with rod length n?
Attempts:
2 left
💡 Hint
Consider the nested loops iterating over rod lengths and cuts.
✗ Incorrect
The outer loop runs n times and the inner loop runs up to n times, resulting in O(n^2) time complexity.
🚀 Application
expert3:00remaining
Maximum Revenue and Cuts for Rod Cutting
Given prices [3, 5, 8, 9, 10] for rod lengths 1 to 5, what is the maximum revenue and the cuts that produce it for a rod of length 5 using bottom-up DP?
DSA Rust
fn rod_cutting_with_solution(prices: &[i32], n: usize) -> (i32, Vec<usize>) {
let mut dp = vec![0; n + 1];
let mut cuts = vec![0; n + 1];
for i in 1..=n {
let mut max_val = i32::MIN;
for j in 1..=i {
if prices[j - 1] + dp[i - j] > max_val {
max_val = prices[j - 1] + dp[i - j];
cuts[i] = j;
}
}
dp[i] = max_val;
}
let mut result_cuts = Vec::new();
let mut length = n;
while length > 0 {
result_cuts.push(cuts[length]);
length -= cuts[length];
}
(dp[n], result_cuts)
}
fn main() {
let prices = [3, 5, 8, 9, 10];
let n = 5;
let (max_revenue, cuts) = rod_cutting_with_solution(&prices, n);
println!("Max revenue: {}", max_revenue);
print!("Cuts: ");
for c in cuts {
print!("{} ", c);
}
}Attempts:
2 left
💡 Hint
Trace the dp and cuts arrays to find max revenue and cuts.
✗ Incorrect
The best revenue is 15 by cutting into lengths 2 and 3 with prices 5 and 8 respectively.