ক্যাপস্টোন — একটি কঠিন সমস্যার সমাধান শুরু থেকে শেষ

১ · সমস্যাটি পড়া — ঢাকার ইলেকট্রিক ডেলিভারি ভ্যান আর তার সীমা

এই পর্বটি একটু আলাদা। নতুন কোনো ডেটা স্ট্রাকচার শিখব না; বরং একটিমাত্র কঠিন সমস্যা নিয়ে একজন অভিজ্ঞ প্রোগ্রামার বা কনটেস্ট্যান্ট যেভাবে ভাবেন, ঠিক সেভাবে শুরু থেকে শেষ পর্যন্ত হাঁটব — পড়া, হিসাব, ভুল পথ, মূল ধারণা, প্রমাণ, কোড আর যাচাই। কোর্সের আগের পর্বগুলোর অনেক কৌশল এখানে একসাথে কাজে লাগবে।

একটি কুরিয়ার কোম্পানি ঢাকায় ব্যাটারিচালিত ডেলিভারি ভ্যান চালায়। শহরে n টি এলাকা, আর m টি দুই-মুখী রাস্তা। রাস্তা i পার হতে ব্যাটারির w_i একক চার্জ খরচ হয়। প্রথম k টি এলাকায় (১ থেকে k) চার্জিং স্টেশন আছে; সেখানে পৌঁছালে ব্যাটারি পুরো ভরে নেওয়া যায়। যাত্রার কোনো মুহূর্তে চার্জ শূন্যের নিচে নামতে পারবে না। কোম্পানি বিভিন্ন ধারণক্ষমতার (capacity) ব্যাটারি কিনতে পারে, তাই q টি প্রশ্ন আসে: “স্টেশন a থেকে পুরো চার্জ নিয়ে রওনা দিয়ে স্টেশন b-তে পৌঁছাতে ব্যাটারির ধারণক্ষমতা c অন্তত কত হতে হবে?”

নমুনা হিসেবে ছয়টি এলাকা: মিরপুর (১), মতিঝিল (২) আর উত্তরা (৩) স্টেশন (বন্ধনীতে চিহ্নিত); ফার্মগেট (৪), তেজগাঁও (৫), গুলশান (৬) সাধারণ এলাকা। সংখ্যাগুলো চার্জ খরচ (বোঝার জন্য বানানো, আসল নয়)।

[Uttara]──────────── 20 ────────────[Mirpur]
    │                                 │   │
    6                                 4   │
    │                                 │   │
 Gulshan ──2── Tejgaon ──3──── Farmgate   12
                  │               │       │
                  2               5       │
                  │               │       │
                  └───────── [Motijheel]──┘

প্রথম উত্তরটি দেখুন। মিরপুর থেকে মতিঝিলের সরাসরি রাস্তায় 12 লাগে, কিন্তু ফার্মগেট হয়ে 4 + 5 = 9. দ্বিতীয়টি আরও মজার: মিরপুর থেকে উত্তরার যেকোনো পথে মোট খরচ অন্তত 15, তবু উত্তর 10 — কারণ পথে মতিঝিলে একবার ঘুরে চার্জ নেওয়া যায়। এই “ঘুরে চার্জ নেওয়া”-ই সমস্যাটিকে কঠিন করেছে, আর এটিই শেষে সমাধানের চাবি হবে।

সীমা থেকে complexity-র বাজেট

অভিজ্ঞ সমাধানকারী কোড লেখার আগে constraints পড়েন, কারণ সীমাই বলে দেয় কোন অ্যালগরিদম চলবে। মোটা দাগের একটি নিয়ম: আধুনিক কম্পিউটারে C++ এক সেকেন্ডে মোটামুটি 10⁸-এর কাছাকাছি সরল কাজ করে (ক্যাশ আর ধ্রুবকের ওপর নির্ভর করে কয়েক গুণ কম-বেশি)। Python সাধারণত এর কয়েক দশ ভাগের এক ভাগ। তাই time limit ১–২ সেকেন্ড হলে:

আমাদের সমস্যায় মোট ইনপুট প্রায় n + m + q ≈ 7 × 10⁵. অর্থাৎ বাজেট মোটামুটি “প্রতিটি জিনিসের জন্য কয়েকটি log” — O((n + m + q) log n) ≈ 10⁷-এর ঘরে। প্রতিটি প্রশ্নে পুরো গ্রাফ ঘাঁটা (q × m ≈ 9 × 10¹⁰) বাদ। দ্বিতীয় তথ্যটি সংখ্যার আকার নিয়ে: একটি পথে 10⁵ টি রাস্তা থাকতে পারে, প্রতিটি 10⁹ পর্যন্ত — উত্তর 10¹⁴-এর কাছাকাছি হতে পারে। তাই int নয়, long long; নইলে overflow.

২ · আগে brute force — সঠিক, কিন্তু ধীর

দ্রুত সমাধানের আগে একটি brute force চাই — যা দেখেই বিশ্বাস হয় যে ঠিক। এর তিনটি কাজ: ছোট উদাহরণে উত্তর দিয়ে সমস্যা বুঝতে সাহায্য করা, পর্যবেক্ষণের কাঁচামাল দেওয়া, আর শেষে দ্রুত সমাধানকে যাচাই করা।

প্রথম চিন্তা — অনুকরণ। একটি নির্দিষ্ট c-এর জন্য ভ্যানটি চালিয়ে দেখি: প্রতিটি এলাকায় “সবচেয়ে বেশি কত চার্জ নিয়ে পৌঁছানো যায়” মনে রাখি, আর পরিবর্তন থামা পর্যন্ত সব রাস্তা ঘুরে মান বাড়াই। c বাড়লে সম্ভাব্যতা কখনো কমে না — বড় ব্যাটারি ছোট ব্যাটারির সব কাজ পারে। এটি একটি monotonic predicate, তাই পর্ব ১৯-এর উত্তরের ওপর binary search চলে: প্রতিটি প্রশ্নে log(10¹⁴) ≈ 47 বার feasibility check. কিন্তু প্রতিটি check-ই বহুবার পুরো গ্রাফ ঘোরে — q টি প্রশ্নে অসম্ভব রকম ধীর।

দ্বিতীয় চিন্তা — স্টেশন থেকে স্টেশনে লাফ। যেকোনো যাত্রাকে স্টেশনগুলোতে কেটে ফেলুন: প্রতিটি টুকরো এক স্টেশন থেকে পরের স্টেশন, মাঝে চার্জ নেওয়ার সুযোগ নেই। s থেকে t-তে এক লাফে যেতে লাগে ঠিক D[s][t] চার্জ — দুটির মধ্যে সবচেয়ে ছোট পথ। তাই উত্তর হলো স্টেশনগুলোর একটি “লাফের গ্রাফে” এমন পথ, যার সবচেয়ে বড় লাফটি যত ছোট সম্ভব। একে বলে minimax path. বাস্তবায়ন: পর্ব ৪৪-এর Floyd-Warshall দিয়ে D, তারপর একই ছাঁচে “যোগ”-এর বদলে “max” নিয়ে আরেকবার:

খরচ O(n³ + k³) সময়, O(n²) জায়গা — n = 10⁵-এ 10¹⁵ কাজ, আর 10¹⁰ ঘরের টেবিল। k টি Dijkstra চালিয়ে k² টি লাফ বানালেও k = 10⁵ হলে 10¹⁰ জোড়া। তবু এই brute force অমূল্য: সরল, আর দ্রুত সমাধানের চেয়ে সম্পূর্ণ আলাদা যুক্তিতে দাঁড়িয়ে — অংশ ৭-এ এটিই হবে আমাদের বিচারক।

৩ · পর্যবেক্ষণ আর মূল ধারণা — নিকটতম স্টেশনটিই সব বলে দেয়

সমস্যার কঠিন অংশ হলো “অবস্থা”: একটি এলাকায় আমরা কত চার্জ নিয়ে আছি, তা নির্ভর করে কোন পথে এসেছি তার ওপর। চার্জ 10¹⁴ পর্যন্ত যেকোনো সংখ্যা হতে পারে, তাই (এলাকা, চার্জ) জোড়ায় পর্ব ৪৩-এর state-space খোঁজও অসম্ভব। দরকার এমন একটি পর্যবেক্ষণ, যা অবস্থাকে একটিমাত্র সংখ্যায় নামিয়ে আনে। ধরুন d[v] = v থেকে নিকটতম যেকোনো স্টেশনে যেতে যত চার্জ লাগে (স্টেশনে d = 0).

1. ওপরের সীমা: v-তে চার্জ কখনো c − d[v]-এর বেশি হতে পারে না। কারণ শেষবার চার্জ নেওয়ার পর একটি স্টেশন থেকে v পর্যন্ত এসেছি, আর সেই পথ অন্তত d[v] লম্বা।
2. নিচের সীমা: v ছেড়ে যাওয়ার পর কোনো না কোনো স্টেশনে পৌঁছাতেই হবে (যাত্রা শেষ হয় b-তে, যেটি স্টেশন)। মাঝে চার্জের সুযোগ নেই, তাই v-তে অন্তত d[v] চার্জ থাকতেই হবে।
3. ঘুরে আসার কৌশল: v-তে অন্তত d[v] থাকলে নিকটতম স্টেশনে গিয়ে পুরো চার্জ নিয়ে ফিরে আসা যায় — ফেরার পর ঠিক c − d[v]. অর্থাৎ বৈধ যাত্রায় v-তে থাকলে আমরা সবসময় সর্বোচ্চ সম্ভব চার্জ c − d[v] ধরে নিতে পারি। পথের ইতিহাস আর লাগে না।

তিনটি মিলিয়ে: u-তে c − d[u] চার্জ নিয়ে রাস্তা (u, v, w) পার হলে থাকে c − d[u] − w, আর v-তে দরকার অন্তত d[v]. তাই

শর্তটি শুধু রাস্তাটির নিজের ওপর নির্ভর করে — কোন পথে এসেছি তার ওপর নয়। নিচের ডায়াগ্রামে নমুনার দ্বিতীয় প্রশ্ন (মিরপুর → উত্তরা, c = 10) চালিয়ে দেখুন। নমুনায় d: মিরপুর, মতিঝিল, উত্তরা 0; ফার্মগেট 4; তেজগাঁও 2 (মতিঝিল কাছে); গুলশান 4 (তেজগাঁও হয়ে মতিঝিল)।

এখন সমস্যাটি সম্পূর্ণ নতুন চেহারা নিয়েছে: প্রতিটি রাস্তাকে ওজন W দিন; এমন সবচেয়ে ছোট c বের করুন, যাতে শুধু W ≤ c রাস্তা দিয়ে a থেকে b যাওয়া যায়। ব্যাটারি, চার্জ, ঘুরে আসা — কিছুই আর নেই। এটি একটি reduction: অপরিচিত সমস্যাকে পরিচিত সমস্যায় রূপান্তর। আর পর্ব ৪৫ থেকে আমরা জানি, undirected গ্রাফে minimax path একটি minimum spanning tree-তে থাকে, Kruskal-এর মতো হালকা থেকে ভারী ক্রমে edge জুড়লে a আর b যে মুহূর্তে এক দলে আসে, সেই edge-এর ওজনই উত্তর।

৪ · ডেটা স্ট্রাকচার বাছাই, অ্যালগরিদম আর শুদ্ধতার প্রমাণ

বাকি প্রশ্ন একটাই: q টি প্রশ্নের উত্তর একসাথে কীভাবে? সব প্রশ্ন শুরুতেই জানা, আর উত্তর যেকোনো ক্রমে দেওয়া যায় — তাই সমাধানটি offline হতে পারে। রাস্তাগুলো W-এর ছোট থেকে বড় ক্রমে DSU-তে জুড়তে থাকি। প্রতিটি দলের সাথে একটি তালিকা রাখি — “যেসব প্রশ্নের অন্তত একটি প্রান্ত এই দলে, কিন্তু উত্তর এখনো মেলেনি”. দুটি দল মিললে ছোট তালিকাটি ঘুরে দেখি কোন প্রশ্নের দুই প্রান্ত এখন এক দলে, তারপর ছোটটিকে বড়টিতে ঢেলে দিই — পর্ব ৩৩-এর small-to-large.

অ্যালগরিদম আর তিনটি lemma

Pseudocode — battery capacity queries (0-based areas, stations are 0..k-1)

d = multiSourceDijkstra(sources = {0, ..., k-1})       // d[v] = charge to the nearest station
for each road (u, v, w):   W = d[u] + w + d[v]
sort roads by W (ascending)
DSU with every area alone;  ans[i] = 0 if a_i == b_i else -1
pend[x] = list of query ids with an endpoint at x
for each road (u, v) in sorted order, with weight W:
    A = find(u);  B = find(v);  if A == B: continue
    union(A, B) by size, new root R; S = the smaller of the two pending lists
    for each query id i in S:
        if ans[i] == -1 and find(a_i) == find(b_i): ans[i] = W
    append S to the other (bigger) list, which now belongs to R

শুদ্ধতা তিনটি lemma-য় ভাগ করি — বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত প্রশ্নে ঠিক এভাবে লিখলে পরীক্ষক প্রতিটি ধাপ মিলিয়ে নিতে পারেন।

1. Lemma ১ (প্রয়োজনীয়তা). ধারণক্ষমতা c-তে যেকোনো বৈধ যাত্রা শুধু W ≤ c রাস্তা ব্যবহার করে। প্রমাণ: যাত্রায় রাস্তা (u, v, w) পার হওয়ার ঠিক আগে চার্জ x. অংশ ৩-এর ওপরের সীমায় x ≤ c − d[u]; নিচের সীমায় x − w ≥ d[v]. মিলিয়ে d[u] + w + d[v] ≤ c. ∎
2. Lemma ২ (যথেষ্টতা). a থেকে b পর্যন্ত এমন একটি পথ থাকলে যার সব রাস্তার W ≤ c, তাহলে c-তে যাত্রা সম্ভব। প্রমাণ (পথের দৈর্ঘ্যে induction): invariant — পথের প্রতিটি vertex u-তে চার্জ ঠিক c − d[u]. a-তে সত্য (d[a] = 0, চার্জ c). রাস্তা (u, v, w) পার হলে থাকে c − d[u] − w ≥ d[v] ≥ 0 — চার্জ কখনো ঋণাত্মক হয়নি, আর নিকটতম স্টেশনে ঘুরে এসে v-তে c − d[v] পাওয়া যায়। b-তে পৌঁছালেই শেষ। ∎
3. Lemma ৩ (offline DSU). W-এর ক্রমে রাস্তা জোড়ার সময় প্রশ্ন i-এর উত্তর সেই রাস্তার W, যার union a_i আর b_i-কে প্রথমবার এক দলে আনে — আর অ্যালগরিদম ঠিক তখনই উত্তর লেখে। প্রমাণ: Kruskal-এর মতো, W ≤ x-এর সব রাস্তা জোড়ার পর DSU-র দলগুলো ঠিক G_≤x-এর component. a, b প্রথম যে x-এ এক component-এ আসে, সেটিই সবচেয়ে ছোট বৈধ c (Lemma ১ ও ২). তালিকার invariant: প্রতিটি root-এর তালিকায় সেই দলে প্রান্ত আছে এমন প্রতিটি অমীমাংসিত প্রশ্ন থাকে। যে প্রশ্ন এই union-এ প্রথম মেটে, তার এক প্রান্ত এক দলে, অন্যটি অন্য দলে — তাই সে দুটি তালিকাতেই আছে, বিশেষ করে ছোটটিতে; ছোট তালিকা ঘুরলেই সে ধরা পড়ে। ∎

Lemma ১ আর ২ মিলে বলে: উত্তর = W-ওজনে a থেকে b-এর minimax path-এর মান। এবার নমুনায় পুরো অ্যালগরিদম দেখুন। W-এর সাজানো ক্রম: মতিঝিল–তেজগাঁও 4, মিরপুর–ফার্মগেট 8, তেজগাঁও–গুলশান 8, ফার্মগেট–মতিঝিল 9, ফার্মগেট–তেজগাঁও 9, গুলশান–উত্তরা 10, মিরপুর–মতিঝিল 12, উত্তরা–মিরপুর 20. প্রশ্ন: q1 (Mir, Mot), q2 (Mir, Utt), q3 (Mot, Utt), q4 (Utt, Utt), q5 (Utt, Mir).

৫ · Complexity — সময় আর মেমরি

Small-to-large-এর হিসাব. তালিকাগুলোতে মোট 2q টি প্রবেশ, আর কোনোটি কখনো মোছা হয় না। একটি প্রবেশ সরে শুধু ছোট তালিকা থেকে বড়টিতে; নতুন তালিকার আকার তাই আগের তালিকার অন্তত দ্বিগুণ। আকার 2q ছাড়াতে পারে না, তাই প্রতিটি প্রবেশ সর্বোচ্চ log₂(2q) বার সরে — মোট O(q log q) সরানো, প্রতিটিতে দুটি find. এটি পর্ব ৬০-এর aggregate amortized analysis-এর একটি চমৎকার উদাহরণ: কোনো একটি union-এ অনেক কাজ হতে পারে, কিন্তু সব মিলিয়ে সীমিত।

মোট: O((n + m) log n + m log m + q log q · α(n)) সময়, আর O(n + m + q) মেমরি — adjacency list-এ 2m, সাজানো রাস্তা m, তালিকায় 2q, আর d, par, sz-এ n টি করে ঘর। সর্বোচ্চ ইনপুটে আনুমানিক কাজ: 7 × 10⁵ × 17 + 3 × 10⁵ × 18 + 6 × 10⁵ × 19 ≈ 2.9 × 10⁷ — দুই সেকেন্ডের সীমার অনেক নিচে। মেমরি কয়েক দশ MB.

৬ · বাস্তবায়ন — C++ আর Python

নিচের প্রোগ্রাম কনটেস্টের মতো ইনপুট পড়ে। “চালান” চাপলে অংশ ১-এর নমুনা ইনপুটটি নিজে থেকেই দেওয়া হয়:

6 8 3 5
1 4 4
4 2 5
1 2 12
4 5 3
5 6 2
6 3 6
2 5 2
3 1 20
1 2
1 3
2 3
3 3
3 1

#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);                 // fast I/O
    int n, m, k, q; cin >> n >> m >> k >> q;
    vector<tuple<int, int, ll>> es(m);
    vector<vector<pair<int, ll>>> adj(n);
    for (auto& [u, v, w] : es) { cin >> u >> v >> w; --u; --v; adj[u].push_back({v, w}); adj[v].push_back({u, w}); }
    // 1) multi-source Dijkstra: d[v] = charge needed to reach the nearest station (areas 0..k-1)
    vector<ll> d(n, 1LL << 60);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    for (int s = 0; s < k; ++s) { d[s] = 0; pq.push({0, s}); }
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du != d[u]) continue;                                    // stale pair
        for (auto [v, w] : adj[u]) if (du + w < d[v]) { d[v] = du + w; pq.push({d[v], v}); }
    }
    // 2) key insight: road (u, v, w) is usable with battery c  <=>  d[u] + w + d[v] <= c
    vector<tuple<ll, int, int>> E; for (auto [u, v, w] : es) E.push_back({d[u] + w + d[v], u, v});
    sort(E.begin(), E.end());
    // 3) offline DSU over roads in increasing order; pending queries merged small-to-large
    vector<int> par(n), sz(n, 1), qa(q), qb(q); iota(par.begin(), par.end(), 0);
    vector<ll> ans(q, -1); vector<vector<int>> pend(n);
    for (int i = 0; i < q; ++i) {
        cin >> qa[i] >> qb[i]; --qa[i]; --qb[i];
        if (qa[i] == qb[i]) ans[i] = 0; else { pend[qa[i]].push_back(i); pend[qb[i]].push_back(i); }
    }
    auto find = [&](int x) { while (par[x] != x) x = par[x] = par[par[x]]; return x; };   // path halving
    for (auto [c, u, v] : E) {
        int a = find(u), b = find(v); if (a == b) continue;
        if (sz[a] < sz[b]) swap(a, b);
        par[b] = a; sz[a] += sz[b];                                    // union by size
        if (pend[a].size() < pend[b].size()) swap(pend[a], pend[b]);
        for (int i : pend[b]) {                                        // walk the SMALLER list
            if (ans[i] < 0 && find(qa[i]) == find(qb[i])) ans[i] = c;
            pend[a].push_back(i);
        }
        vector<int>().swap(pend[b]);                                   // free its memory
    }
    for (ll x : ans) cout << x << '\n';
}

9
10
10
0
10

import sys, heapq
def main():
    it = iter(sys.stdin.buffer.read().split())
    n, m, k, q = (int(next(it)) for _ in range(4))
    es = [(int(next(it)) - 1, int(next(it)) - 1, int(next(it))) for _ in range(m)]
    adj = [[] for _ in range(n)]
    for u, v, w in es: adj[u].append((v, w)); adj[v].append((u, w))
    # 1) multi-source Dijkstra: d[v] = charge needed to reach the nearest station
    d = [0] * k + [float("inf")] * (n - k)
    pq = [(0, s) for s in range(k)]
    while pq:
        du, u = heapq.heappop(pq)
        if du != d[u]: continue                # stale pair
        for v, w in adj[u]:
            if du + w < d[v]: d[v] = du + w; heapq.heappush(pq, (d[v], v))
    # 2) key insight: road (u, v, w) is usable with battery c  <=>  d[u] + w + d[v] <= c
    E = sorted((d[u] + w + d[v], u, v) for u, v, w in es)
    # 3) offline DSU over edges in increasing order; pending query lists merged small-to-large
    par, sz = list(range(n)), [1] * n
    qa, qb, ans, pend = [0] * q, [0] * q, [-1] * q, [[] for _ in range(n)]
    for i in range(q):
        qa[i], qb[i] = int(next(it)) - 1, int(next(it)) - 1
        if qa[i] == qb[i]: ans[i] = 0
        else: pend[qa[i]].append(i); pend[qb[i]].append(i)
    def find(x):
        while par[x] != x:
            par[x] = par[par[x]]               # path halving
            x = par[x]
        return x
    for c, u, v in E:
        a, b = find(u), find(v)
        if a == b: continue
        if sz[a] < sz[b]: a, b = b, a
        par[b] = a; sz[a] += sz[b]             # union by size
        if len(pend[a]) < len(pend[b]): pend[a], pend[b] = pend[b], pend[a]
        for i in pend[b]:                      # move the SMALLER list
            if ans[i] < 0 and find(qa[i]) == find(qb[i]): ans[i] = c
            pend[a].append(i)
        pend[b] = []
    print("\n".join(map(str, ans)))

main()

9
10
10
0
10

৭ · টেস্টিং আর পারফরম্যান্স — edge case, checker, stress test আর সময় মাপা

নমুনা মিলেছে — কিন্তু নমুনা মেলা মানে প্রমাণ নয়। কোড আর প্রমাণের মাঝে প্রায়ই ছোট ফাঁক থাকে: একটি <-এর জায়গায় ≤, ভুল প্রান্তে find, শূন্য-ভিত্তিক সূচকের ভুল। তিন স্তরে যাচাই করি।

স্তর ১ — হাতে বানানো edge case

• a = b: উত্তর 0 — কোনো রাস্তাই লাগে না। কোডে আলাদা করে ধরা হয়েছে।
• k = 1: একটিই স্টেশন, তাই সব প্রশ্ন a = b — সব উত্তর 0.
• সব এলাকাই স্টেশন (k = n): সব d = 0, W = w — সমস্যাটি হয়ে যায় সাধারণ minimax path, MST-এর সরাসরি প্রয়োগ।
• একই জোড়ায় একাধিক রাস্তা, আর self-loop: self-loop দুই প্রান্ত একই দলে বলে বাদ পড়ে; parallel edges-এর হালকাটি আগে আসে।
• লম্বা শিকল, বড় ওজন: 10⁵ টি এলাকা এক সারিতে, প্রতিটি রাস্তা 10⁹, স্টেশন শুধু দুই প্রান্তে — d প্রায় 5 × 10¹³, তাই int-এ overflow ধরা পড়বে।

স্তর ২ ও ৩ — checker আর stress test

Stress testing-এর ছাঁচ সরল: একটি test generator হাজার হাজার ছোট এলোমেলো ইনপুট বানায়, প্রতিটিতে দ্রুত সমাধান আর brute force চলে, উত্তর না মিললেই থেমে ইনপুটটি ছাপে। ছোট ইনপুট (n ≤ 7) ইচ্ছাকৃত: brute force সেখানে তাৎক্ষণিক, আর ভুল ধরা পড়লে ইনপুটটি হাতে trace করা যায়। জেনারেটর একটি নিজে লেখা PRNG — একটি 64-bit linear congruential generator, নির্দিষ্ট seed 2026. এতে দুটি সুবিধা: প্রতিবার হুবহু একই ১০০০টি টেস্ট (reproducibility), আর C++ ও Python একই সংখ্যার ধারা পায়। এলোমেলো tree আগে বানিয়ে তারপর বাড়তি রাস্তা জোড়া হয়, তাই গ্রাফ সবসময় connected; বাড়তি রাস্তায় self-loop আর parallel edge আপনা থেকেই আসে।

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
unsigned long long st = 2026;                       // fixed seed: the same tests on every run
int rnd(int lo, int hi) {                           // 64-bit LCG, identical to the Python version
    st = st * 6364136223846793005ULL + 1442695040888963407ULL;
    return lo + (int)((st >> 33) % (unsigned long long)(hi - lo + 1));
}
vector<ll> fast(int n, int k, const auto& es, const auto& qs) {   // the final solution
    vector<vector<pair<int, ll>>> adj(n);
    for (auto [u, v, w] : es) { adj[u].push_back({v, w}); adj[v].push_back({u, w}); }
    vector<ll> d(n, 1LL << 60);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    for (int s = 0; s < k; ++s) { d[s] = 0; pq.push({0, s}); }
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du == d[u]) for (auto [v, w] : adj[u]) if (du + w < d[v]) { d[v] = du + w; pq.push({d[v], v}); }
    }
    vector<tuple<ll, int, int>> E; for (auto [u, v, w] : es) E.push_back({d[u] + w + d[v], u, v});
    sort(E.begin(), E.end());
    vector<int> par(n), sz(n, 1); vector<ll> ans; vector<vector<int>> pend(n);
    iota(par.begin(), par.end(), 0);
    for (auto [a, b] : qs) { pend[a].push_back(ans.size()); pend[b].push_back(ans.size()); ans.push_back(a == b ? 0 : -1); }
    auto find = [&](int x) { while (par[x] != x) x = par[x] = par[par[x]]; return x; };
    for (auto [c, u, v] : E) {
        int a = find(u), b = find(v); if (a == b) continue;
        if (sz[a] < sz[b]) swap(a, b);
        par[b] = a; sz[a] += sz[b];
        if (pend[a].size() < pend[b].size()) swap(pend[a], pend[b]);
        for (int i : pend[b]) if (ans[i] < 0 && find(qs[i].first) == find(qs[i].second)) ans[i] = c;
        pend[a].insert(pend[a].end(), pend[b].begin(), pend[b].end()); pend[b].clear();
    }
    return ans;
}
vector<ll> brute(int n, int k, const auto& es, const auto& qs) {  // other idea: Floyd-Warshall,
    vector<vector<ll>> D(n, vector<ll>(n, 1LL << 60));               // then minimax station hops
    for (int i = 0; i < n; ++i) D[i][i] = 0;
    for (auto [u, v, w] : es) D[u][v] = D[v][u] = min(D[u][v], w);
    for (int l = 0; l < n; ++l) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) D[i][j] = min(D[i][j], D[i][l] + D[l][j]);
    for (int l = 0; l < k; ++l) for (int i = 0; i < k; ++i) for (int j = 0; j < k; ++j) D[i][j] = min(D[i][j], max(D[i][l], D[l][j]));
    vector<ll> ans; for (auto [a, b] : qs) ans.push_back(D[a][b]);
    return ans;
}
int main() {
    int checked = 0;
    for (int t = 0; t < 1000; ++t) {
        int n = rnd(2, 7), k = rnd(1, n);                           // areas 0..k-1 are stations
        vector<tuple<int, int, ll>> es; vector<pair<int, int>> qs;
        for (int v = 1; v < n; ++v) es.push_back({rnd(0, v - 1), v, rnd(1, 9)});   // random tree
        for (int e = rnd(0, n); e > 0; --e) es.push_back({rnd(0, n - 1), rnd(0, n - 1), rnd(1, 9)});
        for (int e = rnd(1, 5); e > 0; --e) qs.push_back({rnd(0, k - 1), rnd(0, k - 1)});
        if (fast(n, k, es, qs) != brute(n, k, es, qs)) { printf("MISMATCH in test %d\n", t); return 1; }
        checked += (int)qs.size();
    }
    printf("all 1000 tests passed (%d queries checked)\n", checked);
}

all 1000 tests passed (3072 queries checked)

import heapq
st = 2026                                           # fixed seed: the same tests on every run
def rnd(lo, hi):                                    # 64-bit LCG, identical to the C++ version
    global st; st = (st * 6364136223846793005 + 1442695040888963407) % 2**64
    return lo + (st >> 33) % (hi - lo + 1)

def fast(n, k, es, qs):                             # Dijkstra + reweight + offline DSU, small-to-large
    adj = [[] for _ in range(n)]
    for u, v, w in es: adj[u].append((v, w)); adj[v].append((u, w))
    d, pq = [0] * k + [10**18] * (n - k), [(0, s) for s in range(k)]
    while pq:
        du, u = heapq.heappop(pq)
        for v, w in (adj[u] if du == d[u] else []):
            if du + w < d[v]: d[v] = du + w; heapq.heappush(pq, (d[v], v))
    par, sz, ans = list(range(n)), [1] * n, [0 if a == b else -1 for a, b in qs]
    pend = [[i for i, ab in enumerate(qs) if x in ab] for x in range(n)]
    def find(x):
        while par[x] != x: par[x] = par[par[x]]; x = par[x]
        return x
    for c, u, v in sorted((d[u] + w + d[v], u, v) for u, v, w in es):
        a, b = sorted((find(u), find(v)), key=lambda r: -sz[r])     # a = the bigger tree
        if a == b: continue
        par[b] = a; sz[a] += sz[b]
        if len(pend[a]) < len(pend[b]): pend[a], pend[b] = pend[b], pend[a]
        for i in pend[b]:
            if ans[i] < 0 and find(qs[i][0]) == find(qs[i][1]): ans[i] = c
        pend[a] += pend[b]; pend[b] = []
    return ans

def brute(n, k, es, qs):                            # other idea: Floyd-Warshall, then minimax hops
    D = [[0 if i == j else 10**18 for j in range(n)] for i in range(n)]
    for u, v, w in es: D[u][v] = D[v][u] = min(D[u][v], w)
    for l in range(n): D = [[min(D[i][j], D[i][l] + D[l][j]) for j in range(n)] for i in range(n)]
    S = [row[:k] for row in D[:k]]                  # station graph: a hop s -> t needs charge D[s][t]
    for l in range(k): S = [[min(S[i][j], max(S[i][l], S[l][j])) for j in range(k)] for i in range(k)]
    return [S[a][b] for a, b in qs]

checked = 0
for t in range(1000):
    n = rnd(2, 7); k = rnd(1, n)                    # areas 0..k-1 are charging stations
    es = [(rnd(0, v - 1), v, rnd(1, 9)) for v in range(1, n)]        # random tree: connected
    es += [(rnd(0, n - 1), rnd(0, n - 1), rnd(1, 9)) for _ in range(rnd(0, n))]   # extra roads
    qs = [(rnd(0, k - 1), rnd(0, k - 1)) for _ in range(rnd(1, 5))]
    if fast(n, k, es, qs) != brute(n, k, es, qs): print("MISMATCH in test", t, es, qs); break
    checked += len(qs)
else: print(f"all 1000 tests passed ({checked} queries checked)")

all 1000 tests passed (3072 queries checked)

পারফরম্যান্স — কাজ গোনা আর দ্রুত I/O

অংশ ৫-এর হিসাবে প্রায় 3 × 10⁷ মৌলিক কাজ। C++-এ এটি এক সেকেন্ডের অনেক কম হওয়ার কথা। একটি এলোমেলো বড় ইনপুটে (n = 10⁵, m = q = 2 × 10⁵, k = 1000) Python সংস্করণে সাধারণ ল্যাপটপে মোটামুটি এক সেকেন্ডের ঘরে সময় লাগার কথা (মেশিনভেদে কম-বেশি) — সীমার ভেতরে, তবে C++-এর তুলনায় নিরাপত্তার ব্যবধান কম। লক্ষ করার বিষয়, এমন সমস্যায় সময়ের বড় অংশ যায় ইনপুট পড়তেই: সর্বোচ্চ সীমায় প্রায় 1.5 × 10⁶ টি সংখ্যা।

• C++: fast I/O — ios::sync_with_stdio(false); cin.tie(nullptr); আর endl-এর বদলে '\n' (endl প্রতিবার buffer খালি করে)। এই দুই লাইন ছাড়া লাখো সংখ্যায় cin কয়েক গুণ ধীর হতে পারে।
• Python: লাইন ধরে input() নয়, একবারে sys.stdin.buffer.read().split(); আউটপুট একটি "\n".join-এ। heap-এ tuple, আর গ্লোবাল নামের বদলে ফাংশনের লোকাল নাম।
• মেমরি: vector<vector<int>>-এ লক্ষাধিক ছোট vector — প্রতিটির নিজস্ব খরচ আছে; খালি হওয়া তালিকার মেমরি ফেরত দিলে সর্বোচ্চ ব্যবহার কমে।
• সবচেয়ে খারাপ আকৃতি: শুধু এলোমেলো নয়, শিকল-গ্রাফ (Dijkstra-য় অনেক relax), তারকা-গ্রাফ, সব প্রশ্ন একই জোড়ায় — প্রতিটিতে আলাদা করে সময় মাপুন।

৮ · ভিন্ন রূপ আর বিস্তার — সমস্যা বদলালে কী হয়

একটি সমাধান সত্যিই বুঝেছেন কি না, তার ভালো পরীক্ষা হলো সমস্যা একটু বদলে দেখা — কোন অংশ টেকে, কোনটি ভাঙে।

৯ · কোর্সের রোডম্যাপ — নয়টি মডিউল, আর এরপর কোথায়

এই একটি সমস্যার সমাধানে কোর্সের প্রায় প্রতিটি মডিউল কোথাও না কোথাও কাজে লেগেছে। পুরো পথটি একবার ফিরে দেখা যাক:

এরপর কী? বিশ্ববিদ্যালয় বা চাকরির পরীক্ষার প্রস্তুতি নিলে পর্ব ৬৮–৭০ (হাতে trace, MCQ, প্রমাণসহ লিখিত প্রশ্ন)। কোডিং ইন্টারভিউর জন্য পর্ব ৭১ — সেখানে প্যাটার্ন চিনে দ্রুত সমাধানে পৌঁছানোর অনুশীলন। ICPC বা অনলাইন কনটেস্টের জন্য পর্ব ৭২-এর সমস্যা সেট, তারপর নিয়মিত Codeforces, AtCoder বা Toph-এর মতো online judge-এ সমস্যা সমাধান। একটি কার্যকর অভ্যাস: প্রতিটি কঠিন সমস্যায় এই পর্বের ছয় ধাপ — সীমা, brute force, পর্যবেক্ষণ, প্রমাণ, কোড, stress test — খাতায় লিখে ফেলুন। কয়েক মাসে দেখবেন “মূল ধারণা” খুঁজে পাওয়ার গতি অনেক বেড়েছে।

১০ · AI-এর যুগে — সমাধান লেখায় নয়, যাচাইয়ে AI

এমন সমস্যা AI-কে দিলে প্রায়ই দ্রুত একটি আত্মবিশ্বাসী উত্তর আসে — কখনো ঠিক, কখনো সূক্ষ্মভাবে ভুল। সবচেয়ে বিপজ্জনক হলো সেই ভুল, যা নমুনা ইনপুটে ধরা পড়ে না। এই পর্বের সমস্যায় আমরা যেসব ভুল দেখেছি বা হতে পারে:

AI-এর সাহায্যে লেখা সমাধান যাচাইয়ের চেকলিস্ট

• সীমা থেকে বাজেট হিসাব করে মিলিয়েছি যে দাবি করা complexity সময়সীমার ভেতরে
• মূল ধারণার প্রমাণ নিজে লিখেছি — প্রয়োজনীয়তা আর যথেষ্টতা দুই দিকই
• AI-এর দেওয়া brute force নিজে পড়ে নিশ্চিত হয়েছি যে সেটি সরল আর আলাদা যুক্তির
• নির্দিষ্ট seed-এ অন্তত ১০০০টি ছোট টেস্টে stress test পাস করেছে, আর একটি ইচ্ছাকৃত ভুল সেটি ধরেছে
• edge case (a = b, k = 1, k = n, self-loop, parallel road, বড় ওজন) আলাদা করে চালিয়েছি
• সবচেয়ে বড় আর সবচেয়ে খারাপ আকৃতির ইনপুটে সময় আর মেমরি মেপেছি