উন্নত DP — bitmask, digit আর tree DP

১ · সমস্যা — ডেলিভারি রাইডারের রুট আর n! টি পথ

ধানমন্ডির একটি রেস্তোরাঁর হাব থেকে একজন ডেলিভারি রাইডার বের হলেন। হাতে ৪টি অর্ডার — চারটি আলাদা এলাকায়। প্রতিটি এলাকায় একবার যেতে হবে, শেষে হাবে ফিরতে হবে। কোন ক্রমে গেলে মোট পথ সবচেয়ে কম? ৪টি এলাকার ক্রম 4! = 24 রকম — হাতেই সব দেখা যায়। কিন্তু অর্ডার ১৫টি হলে ক্রম 15! ≈ 1.3·10¹², আর ২০টিতে প্রায় 2.4·10¹⁸. প্রতি সেকেন্ডে ১০০ কোটি ক্রম দেখলেও ২০টির জন্য ৭০ বছরের বেশি লাগবে।

এটিই বিখ্যাত travelling salesman problem (TSP). এটি NP-hard (পর্ব ৬৪) — polynomial সময়ের কোনো অ্যালগরিদম জানা নেই। তবু n! আর 2ⁿ-এর মধ্যে বিশাল ফাঁক। n = 20-এ 2²⁰·20² ≈ 4.2·10⁸ — এক সেকেন্ডের কাছাকাছি। এই পর্বের প্রথম অর্ধেক সেই কৌশল: “কোন কোন এলাকা ঘোরা হয়েছে”, এই সেটটিকেই DP-র state বানানো।

পর্ব ৫২-তে (DP-র ভিত্তি) দেখেছেন, dynamic programming মানে একই উপসমস্যা বারবার না কষে একবার কষে রাখা। পর্ব ৫৩–৫৪-এর knapsack, LIS, LCS-এ state ছিল এক বা দুটি index — “প্রথম i টি জিনিস”, “প্রথম i আর j টি অক্ষর”. এই পর্বে তিন ধরনের নতুন state দেখবেন:

২ · Bitmask — একটি সংখ্যায় একটি পুরো সেট

এই পূর্ণসংখ্যাকে বলে bitmask. n টি জিনিসের মোট 2ⁿ টি সেট, আর তারা ঠিক 0 থেকে 2ⁿ − 1 পর্যন্ত সংখ্যাগুলো। যেমন n = 4-এ 1011 = 11 মানে সেট {0, 1, 3} (ডান দিক থেকে bit 0). Left shift 1 << j হলো শুধু bit j চালু থাকা সংখ্যা, 2^j. প্রতিদিনের কাজগুলো এক লাইনের:

mask & -mask কেন কাজ করে? Two's complement-এ −x মানে x-এর সব bit উল্টে 1 যোগ — ফলে সবচেয়ে নিচের চালু bit আর তার ডানের শূন্যগুলো x-এর মতোই থাকে, বাকি সব উল্টো। AND করলে শুধু ওই bit বাঁচে — পর্ব ৩৬-এর Fenwick tree-র lowbit. আর mask & (mask − 1): 1 বিয়োগ করলে সবচেয়ে নিচের 1 হয় 0, তার ডানের 0-গুলো হয় 1; AND করলে শুধু ওই bit মুছে যায়। বারবার করলে চালু bit-গুলো একে একে গোনা যায় — popcount.

৩ · Held–Karp — bitmask DP-তে travelling salesman

এলাকাগুলোর নম্বর 0, 1, …, n − 1; এলাকা 0 হলো হাব; d[i][j] হলো i থেকে j-এর দূরত্ব (কিলোমিটারে)। মূল পর্যবেক্ষণ: রাইডার মাঝপথে থাকলে বাকি পথের সেরা পরিকল্পনার জন্য দুটি জিনিসই জানা দরকার — কোন কোন এলাকা ইতিমধ্যে ঘোরা হয়েছে, আর তিনি এখন কোথায়. কোন ক্রমে সেগুলো ঘুরেছেন, তা আর জরুরি নয়। ৪টি এলাকা ঘুরে এলাকা 3-এ আছেন — 0→1→2→3, নাকি 0→2→1→3, তা ভবিষ্যতের পথে কোনো প্রভাব ফেলে না। শুধু অতীতের পথটি যেন সবচেয়ে ছোট হয়।

তাই state সংজ্ঞায়িত করি:

এখানে mask-এ bit 0 (হাব) আর bit j সব সময় চালু। j-তে পৌঁছানোর ঠিক আগে রাইডার ছিলেন কোনো এক k-তে, যেখানে k ∈ mask \ {j}. তাই optimal substructure থেকে recurrence:

শেষে উত্তর: min over j of ( dp[সব][j] + d[j][0] ) — শেষ এলাকা থেকে হাবে ফেরা। mask \ {j} সংখ্যা হিসেবে mask-এর চেয়ে ছোট, তাই mask-গুলো ছোট থেকে বড় ক্রমে ঘুরলেই প্রয়োজনীয় সব ঘর আগে ভরা থাকে। এই DP-র নাম Held–Karp algorithm. প্রথমে ছোট একটি উদাহরণ: হাব আর তিনটি এলাকা।

d   0  1  2  3          0 = hub (Dhanmondi)
0   0  9  5  4          1 = Gulshan
1   9  0  2  7          2 = Banani
2   5  2  0  6          3 = Mirpur
3   4  7  6  0

কেন ঠিক — induction. দাবি: প্রতিটি ঘরে dp[mask][j] ঠিক সংজ্ঞার মান। mask-এ |mask| টি এলাকা থাকলে induction |mask|-এর ওপর। ভিত্তি: dp[{0}][0] = 0, আর {0, j}-এর একমাত্র পথ 0 → j. ধাপ: mask-এর সব এলাকা ঘুরে j-তে শেষ হওয়া যেকোনো পথ নিন, শেষের আগের এলাকা k. পথটির প্রথম অংশ mask \ {j}-এর সব এলাকা ঘুরে k-তে শেষ — তাই তার দৈর্ঘ্য ≥ dp[mask \ {j}][k] (induction hypothesis). ফলে পুরো পথ ≥ dp[mask \ {j}][k] + d[k][j] ≥ recurrence-এর min. উল্টো দিকে, min-টি যে k দেয়, তার সেরা পথের শেষে j জুড়ে দিলেই একটি বৈধ পথ পাওয়া যায় — কারণ j তো mask \ {j}-এ ছিল না, তাই কোনো এলাকা দুবার আসে না। দুই দিক মিলে সমতা। ∎

খরচ. State: 2ⁿ টি mask × n টি শেষ বিন্দু। প্রতিটি state-এ n টি k দেখা। তাই সময় O(2ⁿ·n²), জায়গা O(2ⁿ·n). (bit 0 সব সময় চালু রাখলে আসলে 2ⁿ⁻¹ টি mask — ধ্রুবকে অর্ধেক।) n = 20-এ টেবিলে প্রায় 2·10⁷ টি ঘর; int-এ প্রায় ৮৪ MB, আর par টেবিলসহ দ্বিগুণ। এটিই সীমা — n = 25-এ টেবিলই আর মেমরিতে ধরে না।

এবার পূর্ণ সমস্যা: হাব আর ৪টি এলাকা, অর্থাৎ n = 5. প্রোগ্রামটি DP ভরে, par দিয়ে ট্যুর পুনর্গঠন করে, তারপর 4! = 24টি ক্রমের সবগুলো দেখে (brute force) উত্তর মিলিয়ে নেয়।

#include <algorithm>
#include <climits>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int main() {
    const int n = 5, FULL = (1 << n) - 1, INF = INT_MAX / 2;
    int d[n][n] = {{0, 9, 5, 4, 8}, {9, 0, 2, 7, 4}, {5, 2, 0, 6, 9},
                   {4, 7, 6, 0, 3}, {8, 4, 9, 3, 0}};      // km between 5 areas, 0 = hub
    vector<vector<int>> dp(FULL + 1, vector<int>(n, INF)), par(FULL + 1, vector<int>(n, -1));
    dp[1][0] = 0;                                         // only the hub visited, rider at hub
    for (int mask = 3; mask <= FULL; mask += 2)           // odd masks: bit 0 always set
        for (int j = 1; j < n; ++j) {
            if (!((mask >> j) & 1)) continue;
            int prev = mask ^ (1 << j);                   // the set before arriving at j
            for (int k = 0; k < n; ++k)
                if (((prev >> k) & 1) && dp[prev][k] + d[k][j] < dp[mask][j]) {
                    dp[mask][j] = dp[prev][k] + d[k][j];
                    par[mask][j] = k;
                }
        }
    int best = INF, last = -1;
    for (int j = 1; j < n; ++j)
        if (dp[FULL][j] + d[j][0] < best) { best = dp[FULL][j] + d[j][0]; last = j; }
    vector<int> tour{0};
    for (int mask = FULL, j = last; j != 0; ) {           // walk the parent pointers back
        tour.push_back(j);
        int k = par[mask][j]; mask ^= 1 << j; j = k;
    }
    tour.push_back(0); reverse(tour.begin(), tour.end());
    cout << "Held-Karp best tour = " << best << " km:";
    for (int v : tour) cout << ' ' << v;
    vector<int> p(n - 1); iota(p.begin(), p.end(), 1);
    int brute = INF, orders = 0;
    do {                                                  // brute force: all (n-1)! orders
        int c = d[0][p[0]] + d[p.back()][0];
        for (int i = 0; i + 1 < n - 1; ++i) c += d[p[i]][p[i + 1]];
        brute = min(brute, c); ++orders;
    } while (next_permutation(p.begin(), p.end()));
    cout << "\nbrute force over " << orders << " orders = " << brute << " km\n";
}

Held-Karp best tour = 18 km: 0 3 4 1 2 0
brute force over 24 orders = 18 km

from itertools import permutations

d = [[0, 9, 5, 4, 8], [9, 0, 2, 7, 4], [5, 2, 0, 6, 9],
     [4, 7, 6, 0, 3], [8, 4, 9, 3, 0]]                # km between 5 areas, 0 = hub
n = len(d); FULL = (1 << n) - 1; INF = float("inf")
dp = [[INF] * n for _ in range(FULL + 1)]
par = [[-1] * n for _ in range(FULL + 1)]
dp[1][0] = 0                                          # only the hub visited, rider at hub
for mask in range(3, FULL + 1, 2):                    # odd masks: bit 0 always set
    for j in range(1, n):
        if not (mask >> j) & 1: continue
        prev = mask ^ (1 << j)                        # the set before arriving at j
        for k in range(n):
            if (prev >> k) & 1 and dp[prev][k] + d[k][j] < dp[mask][j]:
                dp[mask][j] = dp[prev][k] + d[k][j]
                par[mask][j] = k
best, last = min((dp[FULL][j] + d[j][0], j) for j in range(1, n))
tour, mask, j = [0], FULL, last
while j != 0:                                         # walk the parent pointers back
    tour.append(j)
    mask, j = mask ^ (1 << j), par[mask][j]
tour = [0] + tour[::-1]
print(f"Held-Karp best tour = {best} km:", *tour)
costs = [d[0][p[0]] + sum(d[a][b] for a, b in zip(p, p[1:])) + d[p[-1]][0]
         for p in permutations(range(1, n))]          # brute force: all (n-1)! orders
print(f"brute force over {len(costs)} orders = {min(costs)} km")

Held-Karp best tour = 18 km: 0 3 4 1 2 0
brute force over 24 orders = 18 km

৪ · আরও bitmask DP — assignment, submask আর SOS

Assignment — কে কোন কাজ করবে

৩ জন রাইডার, ৩টি অর্ডার; cost[i][j] = রাইডার i অর্ডার j নিলে খরচ (মিনিটে)। প্রত্যেকে ঠিক একটি অর্ডার নেবেন — মোট খরচ সবচেয়ে কম কীভাবে? এটি assignment problem. সব ভাগ n! রকম। Bitmask DP-তে state: dp[mask] = mask-এর অর্ডারগুলো প্রথম popcount(mask) জন রাইডারকে দেওয়ার সবচেয়ে কম খরচ. কে কোন অর্ডার পেলেন, তার ক্রম আর জরুরি নয় — শুধু কোন অর্ডারগুলো দেওয়া হয়ে গেছে। পরের রাইডার i = popcount(mask) একটি খালি অর্ডার j নেবেন:

2ⁿ টি state, প্রতিটিতে n টি পছন্দ — O(2ⁿ·n) সময়, O(2ⁿ) জায়গা। Held–Karp-এর চেয়ে এক গুণ n কম, কারণ এখানে “এখন কোথায়” জানার দরকার নেই — রাইডারের পরিচয় mask-এর আকার থেকেই আসে। n ≤ 20-এ চমৎকার। বড় n-এ এই সমস্যার polynomial সমাধান আছে — Hungarian algorithm, O(n³) (পর্ব ৪৭-এ assignment problem প্রসঙ্গে এর নাম দেখেছেন)। অর্থাৎ bitmask DP সব সময় সেরা নয়: সমস্যাটি সত্যিই NP-hard কি না, আগে ভাবুন। কিন্তু শর্ত একটু বদলালেই (“অর্ডার 0 অর্ডার 1-এর আগে বিলি হবে — অর্থাৎ অর্ডার 1 পাবেন অর্ডার 0-এর রাইডারের চেয়ে বড় নম্বরের কেউ”) সাধারণ Hungarian আর সরাসরি খাটে না, আর bitmask DP শুধু transition-এ একটি শর্ত যোগ করে টিকে যায় (j = 1 নেওয়া যাবে কেবল mask-এ bit 0 থাকলে)।

সব submask ঘোরা — আর কেন মোট O(3ⁿ)

অনেক bitmask DP-তে একটি সেটকে দুই ভাগে ভাগ করতে হয়: “এই দলের কিছু কাজ আজ, বাকিটা কাল”. তখন mask-এর প্রতিটি submask s (s ⊆ mask) ঘুরতে হয়। একটি সুন্দর এক-লাইনের লুপ আছে: for (s = m; s > 0; s = (s - 1) & m). s − 1 সবচেয়ে নিচের চালু bit মুছে তার ডানের সব bit চালু করে; & m শুধু m-এর bit রাখে। ফল: m-এর ভেতরের পরের ছোট submask. দেখুন m = 1011-এ:

মোট খরচ O(3ⁿ) — প্রমাণ. সব mask আর তার সব submask-এর জোড়া (mask, s) গুনি। প্রতিটি উপাদান i-এর জন্য ঠিক তিনটি সম্ভাবনা: i mask-এ নেই; i mask-এ আছে কিন্তু s-এ নেই; i দুটিতেই আছে। (s-এ আছে কিন্তু mask-এ নেই — অসম্ভব, কারণ s ⊆ mask.) n টি উপাদানের স্বাধীন তিনটি পছন্দ — মোট 3ⁿ জোড়া। একই কথা binomial theorem দিয়ে: k টি bit-এর mask C(n, k) টি, প্রতিটির 2^k টি submask, আর Σ_k C(n, k)·2^k = (1 + 2)ⁿ = 3ⁿ. n = 15-এ 3¹⁵ ≈ 1.4·10⁷ — দ্রুত; n = 20-এ ≈ 3.5·10⁹ — অনেক ধীর। অনেকে ভুল করে একে O(4ⁿ) ধরেন (2ⁿ mask × 2ⁿ), যা অনেক বেশি।

SOS DP — submask-এর যোগফল দ্রুত. প্রতিটি mask-এর জন্য F[mask] = Σ_{s ⊆ mask} a[s] চাই? উপরের লুপে O(3ⁿ). SOS DP (sum over subsets) এক এক bit ধরে কাজ করে — প্রতিটি bit i-এর জন্য, যেসব mask-এ i চালু, তাদের সাথে i-বন্ধ সঙ্গীর মান যোগ করে। এটি আসলে n-মাত্রার একটি prefix sum (পর্ব ১৭), প্রতিটি মাত্রার দৈর্ঘ্য 2:

Pseudocode — SOS DP (bits 0..n-1), F starts as a copy of a
for i = 0 to n-1:
    for mask = 0 to 2^n - 1:
        if mask has bit i:  F[mask] += F[mask without bit i]
// now F[mask] = sum of a[s] over all s that are submasks of mask   -- O(n 2^n)

৫ · Digit DP — 10¹⁸ পর্যন্ত সংখ্যা গোনা

প্রশ্ন: 1 থেকে 10¹⁸-এর মধ্যে কয়টি সংখ্যার অঙ্কের যোগফল ঠিক 90? বা কয়টি সংখ্যায় 4 অঙ্কটি নেই? (চীনা আর কিছু এশীয় সংস্কৃতিতে 4-কে অশুভ ধরা হয়, তাই অনেক ভবনে ৪ নম্বর তলা থাকে না — “৪ ছাড়া নম্বর” একটি পরিচিত ধাঁধা।) সব সংখ্যা ঘোরা অসম্ভব। কিন্তু খেয়াল করুন: যোগফলের প্রশ্নে একটি সংখ্যার পুরো পরিচয় লাগে না — বাঁ থেকে অঙ্ক বসাতে বসাতে শুধু তিনটি তথ্য মনে রাখলেই চলে। এটিই digit DP.

প্রথম কৌশল: [L, R]-এর বদলে শুধু [0, N] গুনি, কারণ count(L..R) = f(R) − f(L − 1) — পর্ব ১৭-এর prefix sum-এর মতোই। এবার f(N): N-এর অঙ্কগুলো বাঁ থেকে একে একে বসাই। state তিনটি:

• pos — এখন কোন অবস্থানের অঙ্ক বসাচ্ছি (বাঁ থেকে 0, 1, …)।
• tight — এ পর্যন্ত বসানো অঙ্কগুলো কি N-এর শুরুর অঙ্কের সাথে হুবহু মেলে? মিললে এই অবস্থানে N-এর অঙ্কের বেশি বসানো যাবে না; না মিললে (আগেই ছোট অঙ্ক বসেছে) 0–9 সবই চলে। এই tight flag-ই N-এর চেয়ে বড় সংখ্যা ঠেকায়।
• sum — এ পর্যন্ত অঙ্কের যোগফল।

শুরুর শূন্যগুলো (leading zero) যোগফলে কিছু বদলায় না, তাই 7-কে আমরা “007” হিসেবে গুনি — সমস্যা নেই। (অঙ্ক 0-এর সংখ্যা গোনার প্রশ্নে অবশ্য আলাদা started flag লাগে।) N = 253, S = 7-এর হিসাব দেখুন — অর্থাৎ 0 থেকে 253-এর মধ্যে কয়টি সংখ্যার অঙ্ক-যোগফল 7:

খরচ. N-এ D টি অঙ্ক, যোগফল বড়জোর 9D. state D × 2 × (9D + 1), প্রতিটিতে ১০টি অঙ্ক — O(10·D·9D) = O(D²) ধাপ। N = 10¹⁸-এ D = 19: প্রায় 19 × 2 × 172 ≈ 6,500 state, ৬৫ হাজারের মতো ধাপ। 10¹⁸ টি সংখ্যার জায়গায় কয়েক হাজার state — digit DP-র জাদু এখানেই। tight = 1 state প্রতিটি pos-এ আসলে একটিই (N-এর prefix), তাই বেশিরভাগ কাজ free state-এ।

#include <cstring>
#include <iostream>
#include <string>
using namespace std;
string s;                                   // digits of N
int S;                                      // wanted digit sum
long long memo[20][2][170];
long long go(int pos, int tight, int sum) {
    if (sum > S) return 0;                  // already too big: prune
    if (pos == (int)s.size()) return sum == S;
    long long &r = memo[pos][tight][sum];
    if (r >= 0) return r;
    r = 0;
    int lim = tight ? s[pos] - '0' : 9;     // tight: may not exceed N's digit
    for (int dg = 0; dg <= lim; ++dg)
        r += go(pos + 1, tight && dg == lim, sum + dg);
    return r;
}
long long countUpTo(long long N) {          // how many x in [0, N] have digit sum S
    if (N < 0) return 0;
    s = to_string(N);
    memset(memo, -1, sizeof memo);          // tight states depend on N: clear
    return go(0, 1, 0);
}
int digitSum(long long x) { int t = 0; for (; x > 0; x /= 10) t += x % 10; return t; }
int main() {
    S = 7;
    cout << "[0, 253] sum 7: " << countUpTo(253) << '\n';
    long long L = 123, R = 4567; S = 15;
    int brute = 0;
    for (long long x = L; x <= R; ++x) brute += digitSum(x) == S;
    cout << "[123, 4567] sum 15: digit DP = " << countUpTo(R) - countUpTo(L - 1)
         << ", brute force = " << brute << '\n';
    S = 90;
    cout << "[1, 10^18] sum 90: " << countUpTo(1000000000000000000LL) - countUpTo(0) << '\n';
}

[0, 253] sum 7: 21
[123, 4567] sum 15: digit DP = 343, brute force = 343
[1, 10^18] sum 90: 24918647231083239

from functools import lru_cache

def count_upto(N, S):                       # how many x in [0, N] have digit sum S
    if N < 0: return 0
    s = str(N)                              # digits of N

    @lru_cache(maxsize=None)                # a fresh memo for every N
    def go(pos, tight, total):
        if total > S: return 0              # already too big: prune
        if pos == len(s): return int(total == S)
        lim = int(s[pos]) if tight else 9   # tight: may not exceed N's digit
        return sum(go(pos + 1, tight and dg == lim, total + dg)
                   for dg in range(lim + 1))
    return go(0, True, 0)

def digit_sum(x): return sum(map(int, str(x)))

print(f"[0, 253] sum 7: {count_upto(253, 7)}")
L, R, S = 123, 4567, 15
brute = sum(digit_sum(x) == S for x in range(L, R + 1))
print(f"[{L}, {R}] sum {S}: digit DP = {count_upto(R, S) - count_upto(L - 1, S)}"
      f", brute force = {brute}")
print(f"[1, 10^18] sum 90: {count_upto(10**18, 90) - count_upto(0, 90)}")

[0, 253] sum 7: 21
[123, 4567] sum 15: digit DP = 343, brute force = 343
[1, 10^18] sum 90: 24918647231083239

একই ছাঁচে আরও অনেক প্রশ্ন, শুধু state-এর তৃতীয় অংশ বদলায়: “4 নেই” — 4 বসানো নিষেধ, sum-এর দরকারই নেই; “7 দিয়ে বিভাজ্য” — sum-এর বদলে এ পর্যন্ত সংখ্যার mod 7; “পাশাপাশি দুটি অঙ্ক সমান নয়” — আগের অঙ্কটি মনে রাখা।

৬ · Tree DP — অফিসের party আর বসের সমস্যা

একটি কোম্পানির বার্ষিক party. প্রতিটি কর্মীর একটি “আনন্দ-মান” আছে — তিনি এলে party কতটা জমে। কিন্তু একটি শর্ত: কোনো কর্মী আর তাঁর সরাসরি বস একসাথে দাওয়াত পাবেন না (বস থাকলে কর্মী অস্বস্তিতে থাকেন)। মোট আনন্দ সর্বোচ্চ কত? কোম্পানির ক্রমবিন্যাস একটি rooted tree (পর্ব ২৬), আর আমরা খুঁজছি tree-র সর্বোচ্চ ওজনের maximum independent set — এমন node-এর সেট, যার কোনো দুটি edge দিয়ে সরাসরি যুক্ত নয়।

সাধারণ graph-এ এই সমস্যা NP-hard. কিন্তু tree-তে প্রতিটি node তার subtree-কে বাকি tree থেকে আলাদা করে — subtree-র ভেতরের সিদ্ধান্ত বাইরের সাথে শুধু একটি প্রশ্নে যুক্ত: subtree-র root নিজে দাওয়াত পেলেন কি না. তাই tree DP-র state:

in[v] = v-এর subtree-তে সর্বোচ্চ আনন্দ, যদি v দাওয়াত পান — তখন কোনো সন্তান নয়। out[v] = v দাওয়াত না পেলে — তখন প্রতিটি সন্তান স্বাধীনভাবে নিজের ভালোটি বেছে নেন। সন্তানের মান আগে লাগে, তাই হিসাব postorder-এ: আগে সন্তান, পরে বাবা। উত্তর max(in[root], out[root]). বন্ধনীতে প্রতিটি কর্মীর আনন্দ-মান:

Pseudocode — tree DP (0-based or 1-based, children known after rooting)
dfs(v):                                  // postorder: children first
    in[v] = w[v];  out[v] = 0;  size[v] = 1;  down[v] = 0
    best1 = best2 = 0                    // two longest downward edge-paths from children
    for each child c of v:
        dfs(c)
        in[v]  += out[c]
        out[v] += max(in[c], out[c])
        size[v] += size[c]               // subtree size
        h = down[c] + 1;  down[v] = max(down[v], h)
        if h > best1: best2 = best1; best1 = h  else if h > best2: best2 = h
    diameter = max(diameter, best1 + best2)   // longest path that bends at v

এক DFS-এ তিনটি tree DP একসাথে: subtree size — size[v] = 1 + Σ size[c]; diameter — প্রতিটি node-এ নিচে নামা দুটি সবচেয়ে লম্বা পথ জুড়ে বাঁকা পথ, আর সব node-এর মধ্যে সর্বোচ্চটি diameter. পর্ব ৪৮-এ (LCA আর tree-র কৌশল) diameter দেখেছিলেন দুইবার BFS দিয়ে; এই DP সংস্করণের সুবিধা হলো ঋণাত্মক edge-ওজনেও চলে (h-এ ওজন যোগ করুন আর best1, best2-কে 0-তে সীমিত রাখুন)। সবকিছু O(n) সময়ে, O(n) জায়গায়। বড় tree-তে (২ লাখ node-এর শিকল) recursive DFS stack ভরিয়ে ফেলতে পারে — BFS ক্রম বের করে তার উল্টো ক্রমে হিসাব করলেও একই postorder-এর কাজ হয়।

৭ · Rerooting — প্রতিটি node-কে root ধরে উত্তর

নতুন প্রশ্ন: একটি গ্রামের ৬টি বাড়ি রাস্তায় tree আকারে যুক্ত। একটি টিউবওয়েল কোন বাড়ির সামনে বসালে সব বাড়ি থেকে সেখানে যাওয়ার মোট দূরত্ব সবচেয়ে কম হয়? অর্থাৎ প্রতিটি node v-এর জন্য ans[v] = Σ_u dist(v, u). প্রতিটি node থেকে আলাদা BFS চালালে O(n²). Rerooting-এ দুটি DFS-এ O(n).

প্রথম DFS (root 1, নিচ থেকে ওপরে): size[v] আর ans[1] = সব node-এর depth-এর যোগফল। দ্বিতীয় DFS (ওপর থেকে নিচে): root-কে parent p থেকে সন্তান c-তে এক ধাপ সরালে c-র subtree-র size[c] টি node এক ধাপ কাছে আসে, আর বাকি n − size[c] টি এক ধাপ দূরে যায়:

সাধারণ ছাঁচ. Rerooting কাজ করে যখন “parent-এর দিকের অংশ”-এর উত্তর parent-এর পূর্ণ উত্তর থেকে c-র অবদান বাদ দিয়ে পাওয়া যায়। যোগফলে বাদ দেওয়া সহজ (বিয়োগ)। max-এর মতো কাজে বিয়োগ নেই — তখন প্রতিটি node-এ সন্তানদের prefix আর suffix max রেখে “c ছাড়া বাকিদের max” বের করতে হয়। এটি কনটেস্টের একটি প্রিয় কৌশল: “প্রতিটি node থেকে সবচেয়ে দূরের node”, “প্রতিটি node-কে root ধরলে কয়টি edge উল্টাতে হবে” — সবই এক ছাঁচ।

৮ · DP-র state কীভাবে বাছবেন — DAG, চেকলিস্ট আর কনটেস্টের সংকেত

সব DP আসলে DAG-এ পথ. প্রতিটি state একটি node, আর “এই state-এর উত্তর ওই state থেকে আসে” একটি edge. চক্র থাকলে চলে না — তাই state-গুলোর মধ্যে একটি ক্রম থাকতেই হবে: Held–Karp-এ mask বড় হয়, digit DP-তে pos বাড়ে, tree DP-তে subtree ছোট হয়। এটি একটি DAG, আর DP মানে সেই DAG-এর topological ক্রমে (পর্ব ৪২) সবচেয়ে ছোট বা লম্বা পথ, বা পথের সংখ্যা গোনা। Memoization সেই ক্রম নিজে খুঁজে নেয়; tabulation-এ আপনাকে ক্রমটি ঠিক করে দিতে হয়। মোট সময় = state-এর সংখ্যা × প্রতিটি state-এ transition-এর সংখ্যা।

DP state বাছাইয়ের চেকলিস্ট

1. ভবিষ্যতের জন্য অতীতের কী জানা দরকার? শুধু সেটুকু state-এ রাখুন। TSP-তে “ক্রম” নয়, “সেট আর এখনকার জায়গা”.
2. State কি যথেষ্ট? একই state-এ দুটি আলাদা অতীত থেকে এলে ভবিষ্যতের সেরা সিদ্ধান্ত কি একই? না হলে state-এ কিছু বাদ পড়েছে।
3. Transition লিখুন — শেষ সিদ্ধান্তটি কী? (TSP-তে শেষের আগের এলাকা, party-তে root দাওয়াত পেলেন কি না।)
4. ভিত্তি আর উত্তর কোন state-এ, আর হিসাবের ক্রম চক্রহীন কি না।
5. গুনে দেখুন: state × transition সময়সীমায় ধরে কি না, আর টেবিল মেমরিতে।

৯ · AI-এর যুগে উন্নত DP — state ঠিক, নাকি শুধু দেখতে ঠিক?

AI টুল bitmask বা digit DP-র কোড চেনা চেহারায় দ্রুত লিখে দেয়, কিন্তু উন্নত DP-তে ভুল থাকে state-এর সংজ্ঞায় — যা ছোট উদাহরণে ধরা পড়ে না। সাধারণ ভুলগুলো: Held–Karp-এ শুরুর এলাকাকে mask-এ না রাখা, ফলে হাব দুবার আসে; digit DP-তে tight state-ও memo করে পরের N-এ পুরোনো memo ব্যবহার করা; submask লুপকে O(4ⁿ) বা O(2ⁿ) বলা; tree DP-তে “একটি করে স্তর বাদ” ধরনের লোভী উত্তরকে সঠিক বলা; আর bitmask DP-কে n = 30-এ চালানোর পরামর্শ, যেখানে 2³⁰·30 ঘরের টেবিল মেমরিতেই ধরে না।

উন্নত DP যাচাইয়ের চেকলিস্ট

• State-এর সংজ্ঞা এক বাক্যে লিখেছি, আর ভিত্তি ও চূড়ান্ত উত্তর কোন ঘরে, জানি
• ছোট ইনপুটে brute force (সব permutation, সব সংখ্যা, সব subset) দিয়ে মিলিয়েছি — stress testing
• 2ⁿ·n-এর টেবিল কত MB, হিসাব করেছি; 1 << n-এর overflow আর bit-অপারেটরের বন্ধনী দেখেছি
• Digit DP-তে প্রতিটি নতুন N-এ memo মুছেছি, আর L = 0 বা L − 1 < 0 আলাদা করে দেখেছি
• Tree DP-তে edge case: এক node-এর tree, লম্বা শিকল (recursion-এর গভীরতা), তারকা-আকৃতির tree
• Complexity-র দাবি (বিশেষ করে 3ⁿ) নিজে গুনে যাচাই করেছি, AI-এর কথায় নয়