DP problems — rod cutting, egg drop, DP on trees: Exercises

3.7.14 · D4 · Coding › Algorithm Paradigms › DP problems — rod cutting, egg drop, DP on trees

Yeh page ek self-test hai. Problem padho, khud try karo, phir collapsible solution kholо. Har problem parent note aur Dynamic Programming ki core idea pe build karti hai: recursive structure dhundho, phir usse baar-baar compute karna band karo.

Yahaan ki har recurrence teen prerequisites pe tiki hai jo tumhe open rakhni chahiye: Recursion and Memoization (kyun ek baar solve karke store karna better hai), Tree Traversal (DFS) (woh order jisme hum tree nodes visit karte hain), aur Binary Search (jo ek galat shortcut aur ek sahi optimization ke roop mein aata hai).

Level 1 — Recognition

Exercise 1.1 — Subproblem ka naam bolo

Recall Solution

Yeh pure pattern recognition hai — koi arithmetic nahi.

(a) ek chhoti rod. Hum ek baar left pe cut karte hain, $p [i]$ kamate hain, aur length $n - i$ ki rod ke saath reh jaate hain — wahi problem, chhota input.
(b) ek chhota (eggs, floors) pair. Ek drop ke baad, ya toh egg toota (kam eggs, neeche ke kam floors) ya bacha (same eggs, upar ke kam floors). Dono tarah se state $(e, f)$ shrink hoti hai.
(c) ek subtree. Kyunki tree mein no cycles hote hain, har child ka subtree ek self-contained problem hai jiska answer hum parent pe combine karte hain.

Ek unifying sentence: "Subproblems ka smallest set kya hai jiske answers milaakar poore problem ka answer milta hai?"

Exercise 1.2 — Base case padho

Recall Solution

$D (5, 0) = 0$ . Zero floors ke saath test karne ko kuch nahi hai — threshold question already answer ho chuka hai, isliye hum zero drops karte hain. (Jab koi floor nahi hai toh eggs ki count irrelevant hai.)
$D (1, f) = f$ . Single egg ke saath, toot jaana information ka permanent loss hai. Agar tum gamble karo aur floor $k > 1$ se drop karo aur woh toot jaye, toh tum floors $1.. k - 1$ test nahi kar sakte. Isliye single safe strategy hai neeche se floor by floor chadhna, worst case $f$ drops.

Level 2 — Application

Exercise 2.1 — Rod-cutting ka crank ghumaо

Recall Solution

WHAT hum karte hain: table left to right fill karo, har entry every leftmost piece length $i$ try karti hai.

$j$	computation	$r [j]$	first cut $i$
0	—	0	—
1	$p [1] + r [0] = 2$	2	1
2	$max (p [1] + r [1], p [2] + r [0]) = max (4, 5)$	5	2
3	$max (2 + 5, 5 + 2, 7 + 0) = max (7, 7, 7)$	7	1
4	$max (2 + 7, 5 + 5, 7 + 2, 8 + 0) = max (9, 10, 9, 8)$	10	2

WHY $j = 4$ pe 10 aata hai: leftmost piece $i = 2$ lena (price 5) ek length-2 rod chhod deta hai jiska worth $r [2] = 5$ hai, total $10$ — poori rod $8$ mein bechne se zyaada.

Reconstruct: $j = 4$ pe pehla cut $i = 2$ hai → length 2 ka piece. Remaining rod length $4 - 2 = 2$ ; $j = 2$ pe pehla cut $i = 2$ hai → ek aur length-2 piece. Pieces $= {2, 2}$ , revenue $5 + 5 = 10$ .

Exercise 2.2 — Tree ka crank ghumaо

Recall Solution

WHAT hum karte hain: leaves pehle process karo (post-order DFS), kyunki parent ko apne children ke answers chahiye.

Node 3 (leaf): $f 1 = w_{3} = 1$ , $f 0 = 0$ .
Node 2 (child 3): $f 1 = w_{2} + f 0 [3] = 5 + 0 = 5$ . $f 0 = max (f 1 [3], f 0 [3]) = max (1, 0) = 1$ .
Node 1 (child 2): $f 1 = w_{1} + f 0 [2] = 2 + 1 = 3$ . $f 0 = max (f 1 [2], f 0 [2]) = max (5, 1) = 5$ .
Node 0 (child 1): $f 1 = w_{0} + f 0 [1] = 3 + 5 = 8$ . $f 0 = max (f 1 [1], f 0 [1]) = max (3, 5) = 5$ .

Answer $= max (f 1 [0], f 0 [0]) = max (8, 5) = 8$ .

WHY 8: node 0 ko exclude karna (state $f 0 [0] = 5$ ) node 1 ke subtree ko apna best karne deta hai (jo tha ki 1 ko exclude karo aur node 2 lo). Node 0 ko include karna node 1 ko exclude karne par majboor karta hai, lekin node 2 ab free hai — set ${0, 2}$ weight $3 + 5 = 8$ ke saath jeetta hai.

Level 3 — Analysis

Exercise 3.1 — Egg drop mein choices compare karo

Recall Solution

Har candidate first-drop floor $x$ ke liye, do branches hain: toot jaye → $D (1, x - 1) = x - 1$ , bach jaye → $D (2, 6 - x)$ . Hum unka $max$ lete hain (adversary), 1 add karte hain, phir woh $x$ choose karte hain jo sabse chhota total de.

$x$	break $= x - 1$	survive $= D (2, 6 - x)$	$max$	$1 + max$
1	0	$D (2, 5) = 3$	3	4
2	1	$D (2, 4) = 3$	3	4
3	2	$D (2, 3) = 2$	2	3
4	3	$D (2, 2) = 2$	3	4
5	4	$D (2, 1) = 1$	4	5
6	5	$D (2, 0) = 0$	5	6

Minimum $x = 3$ pe hai: $D (2, 6) = 3$ , optimal first drop floor 3 se.

WHY $x = 3$ do branches ko best balance karta hai: ek achha first drop "cost if it breaks" aur "cost if it survives" ko equalize karta hai. $x = 3$ pe dono branches ka cost $2$ hai, isliye na break na survive case dusre se worse ho sakta hai — adversary ke paas koi lever nahi hai.

Exercise 3.2 — Rod cut path reconstruct karo

Recall Solution

Reconstruction cut array ko ek linked list ki tarah walk karta hai:

Length $4$ pe: $cut [4] = 2$ → length $2$ ka piece emit karo. Remaining $= 4 - 2 = 2$ .
Length $2$ pe: $cut [2] = 2$ → length $2$ ka piece emit karo. Remaining $= 2 - 2 = 0$ .
Length $0$ → ruk jao.

Pieces $= {2, 2}$ , revenue $p [2] + p [2] = 5 + 5 = 10$ . Yeh $r [4]$ se match karta hai, reconstruction confirm karta hai.

Level 4 — Synthesis

Exercise 4.1 — Recurrence invent karo: rod cutting with a per-cut cost

Recall Solution

WHAT badalta hai: jab bhi hum split karte hain tab cut charge karna. Isse model karo $c$ ek baar pay karke jab bhi hum leftmost piece lete hain aur rod bacha rehta hai.

$g (j)$ = length $j$ ke liye best net revenue. Leftmost length $i$ try karte hue:

agar $i = j$ toh poori cheez bech do, koi cut nahi: value $p [j]$ ;
agar $i < j$ toh ek cut karo (fee $c$ ) aur continue karo: value $p [i] - c + g (j - i)$ .

$g (0) = 0, g (j) = max (p [j], max_{1 \leq i < j} (p [i] - c + g (j - i))) .$

Apply ( $c = 1$ ):

$g (1) = p [1] = 1$ .
$g (2) = max (p [2], p [1] - 1 + g [1]) = max (5, 1 - 1 + 1) = max (5, 1) = 5$ .
$g (3) = max (p [3], p [1] - 1 + g [2], p [2] - 1 + g [1]) = max (8, 5, 5) = 8$ .
$g (4) = max (p [4], p [1] - 1 + g [3], p [2] - 1 + g [2], p [3] - 1 + g [1]) = max (9, 8, 8, 8) = 9$ .

WHY answer 10 se gir ke 9 ho gaya: purana winner ${2, 2}$ gross $10$ kamata tha lekin ek cut chahiye, net $10 - 1 = 9$ — ab sirf poori rod $9$ mein bechne ke barabar (koi cut nahi). Cut fee ne split karne ka faayda khatam kar diya.

Exercise 4.2 — States invent karo: tree with "at most one child kept"

Recall Solution

WHAT constraint hai: MWIS (no adjacent pair) ke unlike, yahaan ek picked parent ek picked child ki allow karta hai. Isliye parent ki value depend karti hai ki usne kitne children pe apna allowance "kharch" kiya.

Har node $v$ ke liye do states define karo:

$g (v, 0)$ = $v$ ke subtree mein best jab $v$ pick nahi kiya gaya — children unconstrained hain.
$g (v, 1)$ = $v$ ke subtree mein best jab $v$ pick kiya gaya — at most ek child bhi pick ho sakta hai.

$v$ pick nahi kiya: har child apna best choose karta hai, koi coupling nahi: $g (v, 0) = \sum_{c} max (g (c, 0), g (c, 1)) .$

$v$ pick kiya: default yeh hai ki har child $g (c, 0)$ leta hai (pick nahi). Lekin hum ek child ko "upgrade" karne ki permission rakhte hain. Child $c$ ko upgrade karne se $g (c, 1) - g (c, 0)$ milta hai agar woh positive ho. Sabse profitable single upgrade lo:

g(v,1)=\text{base}+\max\Big(0,\ \max_{c}\big(g(c,1)-g(c,0)\big)\Big).$$ Answer $=\max\big(g(\text{root},0),\,g(\text{root},1)\big)$; phir bhi $O(n)$ hai kyunki har edge ek baar touch hoti hai. WHY correct: subtrees disjoint hain isliye values add hote hain; sirf ek "upgrade" allowance ka coupling hai, jo best single child gain choose karke capture hota hai.

Level 5 — Mastery

Exercise 5.1 — Dual "forward" egg-drop aur ek complexity claim

Recall Solution

WHAT dual kehta hai: "min drops for $f$ floors" ke bajaye pucho "with $d$ drops, kitne floors clear kar sakta hoon?" $d$ badhao jab tak $F (2, d) \geq 100$ na ho jaye.

$2$ eggs ke liye, $F (2, d) = F (1, d - 1) + F (2, d - 1) + 1$ aur $F (1, k) = k$ (ek egg $k$ floors $k$ drops mein clear karta hai). Yeh telescope karke triangular numbers deta hai $F (2, d) = \frac{d ( d + 1 )}{2}$ .

$d$	$F (2, d) = d (d + 1) /2$
12	78
13	91
14	105 ≥ 100 ✓

Sabse chhota $d$ jisme $F (2, d) \geq 100$ ho woh hai $d = 14$ .

WHY yeh faster hai: naive table $O (e \cdot f)$ cells fill karta hai, har ek $O (f)$ inner $min_{x}$ scan karta hai → $O (e \cdot f^{2})$ . Forward version $e \times d$ table fill karta hai $O (1)$ per cell ke saath, aur $d$ sirf $O (f)$ hai chhote $e$ ke liye — yahaan $d \leq 14$ versus $f = 100$ . Toh hum $\approx 2 \times 10 0^{2}$ ke bajaye $\approx 2 \times 14$ constant-time steps karte hain.

Exercise 5.2 — Greedy ek star pe exactly kyun fail karta hai

Recall Solution

(a) Greedy: centre ko leta hai (weight $10$ , single heaviest). Centre saare leaves ke adjacent hai, isliye har leaf ab forbidden hai. Greedy total $= 10$ .

(b) DP optimum do MWIS states se, root = centre:

Har leaf $ℓ$ : $f 1 [ℓ] = 4$ , $f 0 [ℓ] = 0$ .
Centre included: $f 1 = 10 + \sum f 0 [ℓ] = 10 + 0 = 10$ .
Centre excluded: $f 0 = \sum max (f 1 [ℓ], f 0 [ℓ]) = 4 \times max (4, 0) = 16$ .
Answer $= max (10, 16) = 16$ → set = chaar leaves.

(c) Greedy kab haar jaata hai: jab bhi ek heavy node ke neighbours collectively usse outweigh kar lein. Formally, node $v$ ko pick karna ek galti hai agar $w_{v} < \sum_{c \in N (v)} (unka achievable contribution jab v exclude ho)$ . Greedy locally sahi hai ( $10 > 4$ per node) lekin globally galat ( $10 < 16$ ). Do-state DP include-vs-exclude ko poore subtree mein ek saath compare karta hai, isliye woh kabhi isme nahi phasta. Yahi wajah hai Greedy Algorithms Knapsack Problem par fail karte hain: locally best pick ek globally better combination block kar sakti hai.

Recall Self-check: problem → state definition match karo

Rod cutting state ::: $r [j]$ = length $j$ ki rod se best revenue (ek dimension). Egg drop state ::: $D (e, f)$ = $e$ eggs, $f$ floors ke saath min worst-case drops (do dimensions). Tree MWIS states ::: $f (v, 0)$ aur $f (v, 1)$ = $v$ exclude / include hone par best subtree weight. Egg drop dual ::: $F (e, d)$ = $e$ eggs aur $d$ drops ke saath max floors clearable.