কনটেস্ট প্রোগ্রামিংয়ে C++ — STL দিয়ে দ্রুত আর নির্ভুল সমাধান

১ · কনটেস্ট প্রোগ্রামিং কী — আর C++ কেন সবার পছন্দ

একটি কনটেস্ট প্রোগ্রামিং সমস্যা হলো খুব নিখুঁতভাবে বলা একটি ধাঁধা। ইনপুট কেমন হবে, আউটপুট ঠিক কীভাবে ছাপতে হবে, সংখ্যাগুলো সর্বোচ্চ কত বড় হতে পারে, সময় কত সেকেন্ড, মেমরি কত — সব লেখা থাকে। আপনি একটি প্রোগ্রাম জমা দেন। একটি online judge সেটিকে গোপন অনেকগুলো টেস্টে চালায় আর ছোট একটি রায় দেয়, যাকে বলে verdict: AC (সব ঠিক), WA (কোথাও ভুল উত্তর), TLE (সময় পেরিয়েছে), RE (প্রোগ্রাম ভেঙে পড়েছে)।

তাই এখানে “কাজ করে” মানে তিনটি জিনিস একসাথে: সঠিক (প্রতিটি গোপন টেস্টে), দ্রুত (সময়সীমার ভেতরে), আর সাশ্রয়ী (মেমরির সীমার ভেতরে)। আর সবকিছু করতে হয় ঘড়ির বিরুদ্ধে — কনটেস্ট সাধারণত দুই থেকে পাঁচ ঘণ্টার।

কনটেস্টের জগৎ

বাংলাদেশে কনটেস্ট প্রোগ্রামিংয়ের ঐতিহ্য বেশ শক্ত। ঢাকায় বহু বছর ধরে ICPC-র একটি এশীয় আঞ্চলিক পর্ব (Dhaka Regional) হয়ে আসছে, আর দেশের বিশ্ববিদ্যালয়ের দলগুলো প্রায় নিয়মিতভাবে World Finals-এ যায়। এই সংস্কৃতি গড়ে উঠেছে শিক্ষক, কোচ আর প্রাক্তন প্রতিযোগীদের দীর্ঘ স্বেচ্ছাশ্রমে — যাঁরা ক্যাম্প চালান, সমস্যা লেখেন, নতুনদের হাতে ধরে শেখান।

C++ কেন কনটেস্টের সবচেয়ে জনপ্রিয় ভাষা

দুটি কারণ। প্রথমত গতি: C++ সরাসরি machine code-এ compile হয়, garbage collector নেই, তাই একই algorithm সাধারণত Python-এর চেয়ে অনেক গুণ আর Java-র চেয়েও কিছুটা দ্রুত চলে। সময়সীমা যখন টানটান, এই পার্থক্যই AC আর TLE-এর পার্থক্য। দ্বিতীয়ত STL: পর্ব ৩০–৩৫-এ যা শিখেছেন — vector, sort, map, set, priority_queue, lower_bound — সব হাতের কাছে, পরীক্ষিত আর দ্রুত। C-তে এগুলো নিজে লিখতে হতো, আর প্রতিটি হাতে লেখা heap বা balanced tree একটি নতুন বাগের সুযোগ।

২ · সমস্যা পড়া — constraints থেকে প্রয়োজনীয় complexity

নতুনরা সমস্যার গল্প পড়ে সরাসরি কোড লিখতে বসেন। অভিজ্ঞরা প্রথমে চোখ দেন নিচের ছোট লাইনটিতে: constraints. “1 ≤ n ≤ 2·10⁵, time limit 1 second” — এই লাইনটি আসলে বলে দেয়, কোন algorithm চলবে আর কোনটি চলবে না। কারণ সাধারণ একটি জাজ মেশিন এক সেকেন্ডে মোটামুটি ১০^৮-এর মতো সরল অপারেশন (যোগ, তুলনা, array পড়া) করতে পারে। এটি নিখুঁত সংখ্যা নয় — cache, মেমরির ধরন আর অপারেশনের জটিলতায় কয়েক গুণ এদিক-ওদিক হয় — কিন্তু সিদ্ধান্ত নেওয়ার জন্য যথেষ্ট ভালো অনুমান। Big-O-তে n বসিয়ে দেখুন, ফল ১০^৮-এর আশেপাশে বা নিচে কি না।

এখন একটি বাস্তব সমস্যায় পুরো সিদ্ধান্তটি ধাপে ধাপে দেখুন। সমস্যা: “n টি সংখ্যা দেওয়া আছে। q টি প্রশ্ন আসবে, প্রতিটিতে l আর r — l থেকে r পর্যন্ত সংখ্যাগুলোর যোগফল কত?” এটি বিখ্যাত range sum queries সমস্যা।

1 ≤ n, q ≤ 2·10^5
-10^9 ≤ a[i] ≤ 10^9
1 ≤ l ≤ r ≤ n
Time limit: 1 second
Memory limit: 256 MB

for each query (l, r):
    sum = 0
    for i = l .. r:  sum += a[i]

সবচেয়ে খারাপ: q × n = 2·10^5 × 2·10^5
                     = 4·10^10 অপারেশন

দরকার:  4·10^10
বাজেট:  1·10^8
অনুপাত: 400 গুণ বেশি  =>  নিশ্চিত TLE

n ≤ 2·10^5 মানে লক্ষ্য:
O(n log n) বা O(n + q)

একবার আগে থেকে হিসাব:  pre[i] = a[1] + ... + a[i]
তারপর প্রতি প্রশ্নে:     pre[r] - pre[l-1]

খরচ: n (তৈরি) + q (প্রশ্ন) = 4·10^5
বাজেটের 250 ভাগের 1 ভাগ  =>  নিশ্চিন্ত

সর্বোচ্চ যোগফল: 2·10^5 × 10^9 = 2·10^14
int-এর সীমা:    প্রায় 2.1·10^9     =>  overflow!
long long:      প্রায় 9.2·10^18    =>  নিরাপদ

সিদ্ধান্ত: prefix sum, long long-এ

৩ · একটি কনটেস্ট টেমপ্লেট — প্রতিটি লাইনের কারণ

অনেক প্রতিযোগী প্রতিটি সমস্যা একটি তৈরি টেমপ্লেট দিয়ে শুরু করেন। ইন্টারনেটে শত শত লাইনের macro-ভরা টেমপ্লেট পাবেন; সেগুলো কপি করবেন না। নিচের ছোট টেমপ্লেটটির প্রতিটি লাইন আপনি ব্যাখ্যা করতে পারবেন — সেটাই আসল কথা।

#include <bits/stdc++.h>      // শুধু কনটেস্টে: GCC-র "সব header একসাথে"
using namespace std;           // শুধু কনটেস্টে: std:: না লিখতে
using ll = long long;          // বড় যোগফল আর গুণফলের জন্য

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);           // প্রতিটি test case-এ নতুন — পুরোনো অবস্থা নেই
    for (auto& x : a) cin >> x;
    cout << accumulate(a.begin(), a.end(), 0LL) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;                  // একাধিক test case থাকলে
    while (t--) solve();
}

fast I/O — দুই লাইন, আর কেন কাজ করে

দশ লাখ সংখ্যা পড়তে হলে শুধু ইনপুট পড়াতেই সময়সীমা শেষ হয়ে যেতে পারে। ডিফল্টভাবে C++-এর cin/cout দুটি কারণে ধীর। প্রথমত, এরা C-র scanf/printf-এর সাথে “মিলিয়ে” চলে, যাতে কেউ দুই ধরনের I/O মেশালেও লেখার ক্রম ঠিক থাকে — এর জন্য C++ stream নিজের বড় buffer ব্যবহার করতে পারে না। sync_with_stdio(false) এই মেলানো বন্ধ করে, ফলে stream নিজের buffer পায় আর অনেক দ্রুত হয়। দাম: এরপর একই প্রোগ্রামে printf আর cout মেশানো যাবে না, মেশালে আউটপুটের ক্রম এলোমেলো হতে পারে।

দ্বিতীয়ত, ডিফল্টভাবে cin “বাঁধা” থাকে cout-এর সাথে: প্রতিবার কিছু পড়ার আগে cout-এর buffer খালি (flush) করা হয়, যাতে মানুষ প্রশ্নটি দেখে তারপর উত্তর টাইপ করতে পারে। কনটেস্টে কোনো মানুষ পর্দায় বসে নেই, তাই cin.tie(nullptr) দিয়ে বাঁধন খুলে দেওয়া হয়। এই দুই লাইন মিলে বড় ইনপুটে I/O কয়েক গুণ দ্রুত হতে পারে (বিস্তারিত পর্ব ০৭-এ)।

long long — overflow-এর বিরুদ্ধে প্রথম প্রতিরক্ষা

int সাধারণত ৩২-bit, সর্বোচ্চ প্রায় ২.১·১০^৯. কনটেস্টে সংখ্যা প্রায়ই ১০^৯ পর্যন্ত হয়, তাই দুটি যোগ করলেই সীমার কিনারায়, আর দুটি গুণ করলে নিশ্চিত signed overflow — যা C++-এ undefined behavior (পর্ব ৪৩)। using ll = long long; একটি type alias; long long কমপক্ষে ৬৪-bit, সর্বোচ্চ প্রায় ৯.২·১০^১৮. সবচেয়ে কুখ্যাত ফাঁদটি দেখুন:

int a = 1'000'000'000, b = 3;
ll wrong = a * b;              // গুণ হয় int-এ, overflow হয় আগে, তারপর ll-এ রাখা
ll right = 1LL * a * b;        // প্রথমেই ll, তাই গুণও ll-এ: 3000000000

ফলের ভ্যারিয়েবল ll হলেই চলে না — হিসাবটি কোন টাইপে হচ্ছে, সেটিই আসল। accumulate-এর শুরুর মানেও একই নিয়ম: 0 দিলে যোগফল int-এ, 0LL দিলে long long-এ (পর্ব ৩৩)।

একাধিক test case — প্রতিবার পরিষ্কার শুরু

আধুনিক কনটেস্টে প্রথম লাইনে প্রায়ই থাকে t — test case-এর সংখ্যা, কখনো ১০^৪ পর্যন্ত। দুটি নিয়ম। এক: প্রতিটি test case-এর ডেটা solve()-এর ভেতরে local ভ্যারিয়েবলে রাখুন, তাহলে আগের test case-এর মান কখনো পরেরটিতে ঢোকে না। global array ব্যবহার করলে প্রতিবার নিজে পরিষ্কার করতে হবে — আর সেটা ভুলে যাওয়া কনটেস্টের সবচেয়ে সাধারণ WA-গুলোর একটি। দুই: পুরো array পরিষ্কার নয়, শুধু ব্যবহৃত n টি ঘর। সমস্যা প্রায়ই বলে “সব test case মিলিয়ে n-এর যোগফল ২·১০^৫-এর বেশি নয়” — প্রতিবার ২·১০^৫ ঘরের array পরিষ্কার করলে ১০^৪ test case-এ ২·১০^৯ অপারেশন, অর্থাৎ TLE.

bits/stdc++.h আর using namespace std; — সৎ কথা

bits/stdc++.h C++ standard-এর কোনো header নয়। এটি GCC-র library (libstdc++)-র ভেতরের একটি ফাইল, যা প্রায় সব standard header একসাথে include করে। কনটেস্টে এটি গ্রহণযোগ্য, কারণ জাজ প্রায় সবসময় GCC, আর কোন header লাগবে তা ভাবার সময় বাঁচে। কিন্তু MSVC-তে এটি নেই, অনেক সিস্টেমের Clang/libc++-তেও স্বাভাবিকভাবে নেই, আর প্রতিটি ফাইলে পুরো library টেনে আনায় compile-এর সময় বাড়ে। using namespace std;-ও কনটেস্টে চলে, কিন্তু বড় প্রজেক্টে নামের সংঘাত ঘটায় (পর্ব ১১)। কনটেস্টেও এর ছোট্ট ফাঁদ আছে: count, next বা distance নামে নিজের global ভ্যারিয়েবল বানালে std-এর একই নামের ফাংশনের সাথে মিলে “ambiguous” error আসতে পারে।

৪ · STL-এর অস্ত্রাগার — কনটেস্টের সবচেয়ে কাজের টুল

পর্ব ৩০–৩৫-এ STL বিস্তারিত শিখেছেন। এখানে শুধু কনটেস্টের চোখে দেখা: কোনটি কখন, আর কোথায় পা পিছলায়।

sort, comparator আর pair-এর তুলনা

std::pair আর std::tuple নিজে থেকেই lexicographic ক্রমে তুলনা হয়: আগে প্রথম উপাদান, সমান হলে দ্বিতীয়টি। তাই “শেষ হওয়ার সময় অনুযায়ী সাজাও, সমান হলে শুরুর সময়” লিখতে আলাদা comparator লাগে না — pair-এ {end, start} রেখে সরাসরি sort করলেই হয়। ভিন্ন নিয়ম চাইলে comparator:

vector<pair<int, int>> v{{3, 9}, {1, 4}, {3, 2}};
sort(v.begin(), v.end());       // {1,4} {3,2} {3,9} — আগে first, তারপর second
sort(v.begin(), v.end(), [](auto& x, auto& y) {
    if (x.first != y.first) return x.first > y.first;   // first বড় থেকে ছোট
    return x.second < y.second;                          // সমান হলে second ছোট থেকে বড়
});

map, set আর unordered_map — anti-hash সতর্কতা

std::map আর std::set ভেতরে balanced tree, তাই প্রতিটি কাজ সবসময় O(log n) — কোনো ইনপুটেই খারাপ হয় না। std::unordered_map hash table, গড়ে O(1), কিন্তু সবচেয়ে খারাপ ক্ষেত্রে O(n). সাধারণ ডেটায় সেই খারাপ ক্ষেত্র প্রায় আসে না। সমস্যা হলো, কনটেস্ট সাধারণ ডেটা নয়।

GCC-তে পূর্ণসংখ্যার std::hash মূলত সংখ্যাটিকেই ফেরত দেয়, আর bucket-এর সংখ্যা কীভাবে বাড়ে তা-ও জানা। তাই কেউ চাইলে এমন হাজারো সংখ্যা বানাতে পারেন, যারা সবাই একই bucket-এ পড়ে — পর্ব ৩১-এর hash flooding. Codeforces-এর মতো যেসব প্ল্যাটফর্মে অন্য প্রতিযোগী আপনার কোডে hack করতে পারেন, বা পরে এমন টেস্ট যোগ হয়, সেখানে এমন anti-hash টেস্ট-এ সুন্দর একটি সমাধানও TLE হয়ে যায়। প্রতিরক্ষা দুটি:

• সহজ পথ: map ব্যবহার করুন। log n-এর বাড়তি খরচ সাধারণত সময়সীমায় ধরে যায়, আর নিশ্চয়তা পুরো।
• দ্রুত পথ: একটি custom hash — যেমন splitmix64-এর মতো একটি ভালো mixing ফাংশন, যার সাথে প্রোগ্রাম চালুর সময় ঘড়ি থেকে নেওয়া একটি এলোমেলো সংখ্যা মেশানো হয়। আক্রমণকারী আগে থেকে জানতে পারেন না কোন সংখ্যা কোন bucket-এ পড়বে।

struct SafeHash {                                   // splitmix64 + এলোমেলো seed
    static unsigned long long mix(unsigned long long x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(unsigned long long x) const {
        static const unsigned long long seed =
            chrono::steady_clock::now().time_since_epoch().count();
        return mix(x + seed);
    }
};
unordered_map<long long, int, SafeHash> cnt;

set-এর lower_bound — একই নাম, ভিন্ন খরচ

পর্ব ৩৩-এর std::lower_bound সাজানো vector-এ O(log n). কিন্তু set-এর iterator লাফ দিতে পারে না, এক এক ঘর হাঁটে — তাই std::lower_bound(s.begin(), s.end(), x) তুলনা O(log n) করলেও মোট সময় O(n). দুই লাখ প্রশ্নে সেটাই TLE. সমাধান: set-এর নিজের member — s.lower_bound(x), যা tree ধরে নামে, সত্যিকারের O(log n). এটি কনটেস্টের সবচেয়ে প্রচলিত “অদৃশ্য” TLE-গুলোর একটি।

priority_queue — Dijkstra-র এক ঝলক

std::priority_queue ডিফল্টে সবচেয়ে বড় উপাদানটি ওপরে রাখে (max-heap). সবচেয়ে ছোটটি চাইলে তৃতীয় template argument-এ greater<>. গ্রাফে সবচেয়ে ছোট পথ খোঁজার Dijkstra-র algorithm ঠিক এটিই ব্যবহার করে: “এখন পর্যন্ত সবচেয়ে কাছের যে জায়গাটির দূরত্ব চূড়ান্ত হয়নি, সেটি আগে।”

priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;  // ছোটটি ওপরে
pq.push({0, src});                       // {দূরত্ব, node}
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d != dist[u]) continue;          // পুরোনো, বাতিল হয়ে যাওয়া entry
    for (auto [v, w] : adj[u])
        if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); }
}

ছোট কিন্তু ধারালো

vector<int> p{3, 1, 2};
sort(p.begin(), p.end());                         // আগে সবচেয়ে ছোট বিন্যাস
do { /* 1 2 3, 1 3 2, 2 1 3, ... মোট 3! = 6 */ }
while (next_permutation(p.begin(), p.end()));     // শেষ বিন্যাসের পরে false

ll g = gcd(12LL, 18LL), l = lcm(4LL, 6LL);        // 6 আর 12 (C++17)
bitset<1000> seen;  seen[5] = 1;  seen.count();   // কয়টি 1
int ones = __builtin_popcount(13u);               // 13 = 1101, তাই 3
int ones2 = popcount(13u);                        // C++20-এর standard সংস্করণ, <bit>

next_permutation একটি range-কে অভিধানের ক্রমে পরের বিন্যাসে বদলায়, আর শেষ বিন্যাসের পরে false দিয়ে আবার প্রথমটিতে ফেরে — তাই সব বিন্যাস পেতে শুরুতে sort জরুরি। std::gcd আর std::lcm C++17-এর আগে ছিল না; পুরোনো কোডে GCC-র __gcd দেখবেন। std::bitset bit-গুলো ৬৪-bit শব্দে ভরে রাখে, তাই দুটি bitset-এর AND/OR/shift একসাথে ৬৪টি bool-এর কাজ করে। __builtin_popcount standard নয়, GCC আর Clang-এর নিজস্ব; C++20 থেকে বহনযোগ্য বিকল্প std::popcount (শুধু unsigned টাইপে)।

৫ · চেনা ছাঁচ ১ — prefix sum আর two pointers

কনটেস্টের হাজারো সমস্যা আসলে কয়েক ডজন চেনা ছাঁচের নতুন পোশাক। নতুন সমস্যা দেখে “এটি কোন ছাঁচ?” — এই প্রশ্নটিই অর্ধেক সমাধান। এই অংশ আর পরের অংশে সাতটি সবচেয়ে প্রচলিত ছাঁচ, প্রতিটির একটি ছোট উদাহরণসহ। (ছাঁচ চেনার সাধারণ পদ্ধতি C কোর্সের কনটেস্ট পর্বে আছে; এখানে জোর C++ আর STL-এ।)

ছাঁচ ১: prefix sum — একবার হিসাব, বারবার উত্তর

prefix sum-এর ভাবনা ২ নম্বর অংশে দেখেছেন। pre[i] = প্রথম i টি সংখ্যার যোগফল, আর pre[0] = 0. তাহলে l থেকে r পর্যন্ত যোগফল = pre[r] - pre[l-1], কারণ প্রথম r টির যোগফল থেকে প্রথম l−1 টির যোগফল বাদ দিলে ঠিক মাঝের অংশটুকু থাকে। ক্রিকেটের স্কোরবোর্ডের মতো: ১০ ওভার শেষে ৭২, ১৫ ওভার শেষে ১১০ — তাহলে ১১ থেকে ১৫ নম্বর ওভারে ৩৮ রান, প্রতিটি ওভার আলাদা না গুনেই।

1vector<ll> pre(n + 1, 0);       // a = 4 -2 7 1 52for (int i = 1; i <= n; ++i)3    pre[i] = pre[i - 1] + a[i];4// প্রশ্ন: l = 2, r = 55ll ans = pre[r] - pre[l - 1];

এবার পুরো সমাধানটি, কনটেস্টের ধরনে: একাধিক test case, fast I/O, long long. (এখানে আমরা std:: লিখেছি — কনটেস্টের কোডও এভাবে লেখা যায়।) দ্বিতীয় test case-টি ইচ্ছা করে বড় সংখ্যায়, overflow যাচাইয়ের জন্য:

#include <iostream>
#include <vector>
using ll = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--) {
        int n, q;
        std::cin >> n >> q;
        std::vector<ll> pre(n + 1, 0);    // প্রতিটি test case-এ নতুন
        for (int i = 1; i <= n; ++i) { ll x; std::cin >> x; pre[i] = pre[i - 1] + x; }
        while (q--) {
            int l, r;
            std::cin >> l >> r;
            std::cout << pre[r] - pre[l - 1] << '\n';
        }
    }
}

ছাঁচ ২: two pointers — দুই আঙুলের জানালা

প্রশ্ন: ধনাত্মক সংখ্যার একটি তালিকায় সবচেয়ে লম্বা পরপর অংশ কোনটি, যার যোগফল S-এর বেশি নয়? যেমন একটি দোকানের প্রতিদিনের খরচ, আর জানতে চান সর্বোচ্চ কতদিন টানা চালানো যায় বাজেট না পেরিয়ে। সব জোড়া (l, r) পরীক্ষা করলে O(n²)। two pointers কৌশলে দুটি আঙুল — l আর r — দুজনেই শুধু সামনে এগোয়: r নতুন সংখ্যা জানালায় ঢোকায়, আর যোগফল S পেরোলে l পুরোনো সংখ্যা বের করে দেয়। এমন চলমান জানালাকে বলে sliding window.

1int l = 0, best = 0; ll sum = 0;   // a = 2 1 3 2 4 1, S = 62for (int r = 0; r < n; ++r) {3    sum += a[r];4    while (sum > S) sum -= a[l++];5    best = max(best, r - l + 1);6}

৬ · চেনা ছাঁচ ২ — binary search on answer, greedy, BFS, DP, sieve

ছাঁচ ৩: binary search on answer — উত্তরটাই খুঁজুন

কখনো সরাসরি উত্তর বের করা কঠিন, কিন্তু “এই মানটি কি যথেষ্ট?” — এই হ্যাঁ/না প্রশ্নের উত্তর দেওয়া সহজ। আর উত্তরটি যদি monotonic হয় — কোনো মান যথেষ্ট হলে তার চেয়ে বড় সব মানও যথেষ্ট — তাহলে সম্ভাব্য উত্তরের পুরো পরিসরে binary search চালানো যায়। একে বলে binary search on answer.

উদাহরণ: একটি কুরিয়ার অফিসে ৬টি পার্সেলের ওজন 3 2 2 4 1 4, এই ক্রমেই পাঠাতে হবে, আর ৩ দিনের মধ্যে সব শেষ করতে হবে। প্রতিদিনের ভ্যানের সর্বনিম্ন ধারণক্ষমতা কত হলে চলবে? “ধারণক্ষমতা c হলে কয়দিন লাগে” — এটি greedy-ভাবে সহজে গোনা যায়: যতক্ষণ ধরে ততক্ষণ আজকের ভ্যানে তুলুন, না ধরলে পরের দিন। আর c বাড়ালে দিন কখনো বাড়ে না — monotonic.

1ll lo = 4, hi = 16;              // সবচেয়ে ভারী, মোট ওজন2while (lo < hi) {3    ll mid = lo + (hi - lo) / 2;4    if (days(mid) <= 3) hi = mid; else lo = mid + 1;5}   // উত্তর: lo

ছাঁচ ৪: greedy with sorting — সবচেয়ে কম বাস

সমস্যা: শিক্ষাসফরে কয়েকটি দল যাবে, প্রতিটি দলের সদস্যসংখ্যা জানা। প্রতিটি বাসে সর্বোচ্চ C জন ধরে, প্রতিটি দলকে একসাথে থাকতে হবে, আর নিয়ম অনুযায়ী এক বাসে সর্বোচ্চ দুটি দল। সবচেয়ে কম কয়টি বাস লাগবে? greedy ভাবনা: সবচেয়ে বড় দলটির জন্য একটি বাস লাগবেই। তার সাথে কাউকে বসানো গেলে সবচেয়ে ছোট দলটিকেই বসান — কারণ যে দলই বড়টির সাথে বসতে পারে, সবচেয়ে ছোটটিও পারে, আর ছোটটিকে এখন ব্যবহার করলে পরের জন্য বড়গুলো রইল না, ছোটগুলোই রইল। এমন যুক্তিকে বলে exchange argument: যেকোনো সর্বোত্তম সমাধানকে অদলবদল করে greedy-র সমাধানে আনা যায়, খারাপ না করে।

sort(g.begin(), g.end());                  // C = 10: 7 2 5 9 3 4 -> 2 3 4 5 7 9
int i = 0, j = n - 1, buses = 0;
while (i <= j) {
    if (i < j && g[i] + g[j] <= C) ++i;    // সবচেয়ে ছোটটি বড়টির সাথে যায়
    --j; ++buses;                          // সবচেয়ে বড়টি এই বাসে
}   // 9 একা, 7+2, 5+3, 4 একা  =>  4 বাস

greedy-র বিপদ হলো, সেটি প্রায়ই দেখতে ঠিক লাগে কিন্তু ভুল। তাই প্রমাণ — অন্তত exchange argument-এর মতো একটি যুক্তি — না পেলে greedy-কে stress test দিয়ে (৭ নম্বর অংশ) যাচাই করুন।

ছাঁচ ৫: BFS on a grid — গোলকধাঁধায় সবচেয়ে ছোট পথ

একটি গোলকধাঁধা: . মানে খোলা ঘর, # মানে দেয়াল। বাঁ-ওপরের কোণ থেকে ডান-নিচের কোণে যেতে সবচেয়ে কম কয় ধাপ লাগে (প্রতি ধাপে ওপর, নিচ, ডান বা বাঁয়ে এক ঘর)? BFS (breadth-first search) শুরুর ঘর থেকে ঢেউয়ের মতো ছড়ায়: আগে ১ ধাপ দূরের সব ঘর, তারপর ২ ধাপ দূরের সব, তারপর ৩... পুকুরে ঢিল ফেললে যেমন বৃত্ত ছড়ায়। একটি ঘরে প্রথমবার যখন পৌঁছায়, সেটিই তার সবচেয়ে ছোট দূরত্ব, কারণ প্রতিটি ধাপের খরচ সমান। এর জন্য দরকার একটি std::queue — যে আগে এসেছে, সে আগে যাবে।

#include <iostream>
#include <queue>
#include <string>
#include <vector>
int main() {
    int r, c; std::cin >> r >> c;
    std::vector<std::string> g(r); for (auto& row : g) std::cin >> row;
    std::vector<std::vector<int>> d(r, std::vector<int>(c, -1));   // -1 = এখনো যাইনি
    std::queue<std::pair<int, int>> q; q.push({0, 0}); d[0][0] = 0;
    const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int k = 0; k < 4; ++k) {      // চার দিকে এক ঘর করে
            int nx = x + dr[k], ny = y + dc[k];
            if (nx < 0 || ny < 0 || nx >= r || ny >= c       // গ্রিডের বাইরে,
                || g[nx][ny] == '#' || d[nx][ny] != -1) continue;  // দেয়াল, বা আগে দেখা
            d[nx][ny] = d[x][y] + 1; q.push({nx, ny});
        }
    }
    std::cout << d[r - 1][c - 1] << '\n';
}

ছাঁচ ৬: সরল 1D DP — greedy যেখানে হারে

৬ টাকা দিতে হবে, নোট আছে ১, ৩ আর ৪ টাকার (যত খুশি)। সবচেয়ে কম কয়টি নোট? greedy বলবে “সবচেয়ে বড়টি আগে”: ৪ + ১ + ১ = ৩টি নোট। কিন্তু ৩ + ৩ = ২টি। এখানে greedy হারে, দরকার dynamic programming: ছোট উপসমস্যার উত্তর একবার বের করে রেখে বড়টি গড়া। dp[x] = x টাকা দিতে সবচেয়ে কম নোট।

const int INF = 1e9;
vector<int> dp(X + 1, INF);  dp[0] = 0;          // 0 টাকায় 0 নোট
for (int x = 1; x <= X; ++x)
    for (int c : coins)                             // শেষ নোটটি c হলে?
        if (c <= x && dp[x - c] != INF) dp[x] = min(dp[x], dp[x - c] + 1);
// coins = {1, 3, 4}, X = 6:  dp = 0 1 2 1 1 2 2  =>  উত্তর 2

DP-র আসল প্রশ্ন কোড নয়, অবস্থা (state) আর রূপান্তর: “dp[x] কী বোঝায়, আর সেটি কোন ছোট dp থেকে আসে?” এই দুটি এক বাক্যে বলতে পারলে কোড প্রায় নিজেই লেখা হয়ে যায়। খরচ O(X × নোটের ধরন).

ছাঁচ ৭: sieve — মৌলিক সংখ্যা একসাথে

১০^৭ পর্যন্ত সব মৌলিক সংখ্যা দরকার হলে প্রতিটি সংখ্যা আলাদা করে পরীক্ষা না করে Sieve of Eratosthenes: প্রতিটি মৌলিক সংখ্যার সব গুণিতক কেটে দিন, খরচ O(n log log n). পর্ব ৩৯-এ দেখেছেন কীভাবে এটি constexpr দিয়ে compile-এর সময়েই চালানো যায়। কনটেস্টে সাধারণত vector<bool> বা bitset দিয়ে লেখা হয়, যাতে প্রতিটি সংখ্যার জন্য মাত্র একটি bit লাগে — ১০^৭ সংখ্যায় মোটে প্রায় ১.২৫ MB.

৭ · কনটেস্টে ডিবাগিং — stress testing আর WA-র চেনা কারণ

WA পেয়েছেন, কিন্তু নমুনা তো মিলছে। জাজ বলবে না কোন টেস্টে ভুল। কোড বারবার পড়ে ভুল খোঁজা ধীর, আর নিজের কোডে নিজের ভুল চোখে পড়ে কম। এর চেয়ে কার্যকর পদ্ধতি stress testing — যন্ত্রকে দিয়ে ভুল খোঁজানো। চারটি অংশ:

1. আসল সমাধান — দ্রুত, কিন্তু সন্দেহজনক।
2. একটি brute force সমাধান — ধীর, কিন্তু এত সরল যে ভুলের সুযোগ প্রায় নেই (যেমন range sum-এর জন্য প্রতি প্রশ্নে সাধারণ লুপ)।
3. একটি generator — একটি seed নিয়ে ছোট এলোমেলো ইনপুট বানায় (n ≤ ৮, সংখ্যা ≤ ১০)। ছোট, যাতে ভুল ধরা পড়লে হাতে বোঝা যায়।
4. একটি লুপ — হাজারবার generator চালায়, দুই সমাধানের আউটপুট মেলায়, প্রথম অমিলেই থেমে সেই ইনপুটটি দেখায়।

// gen.cpp — seed কমান্ড লাইন থেকে, তাই প্রতিবার ভিন্ন কিন্তু আবার ঘটানো যায়
int main(int argc, char* argv[]) {
    std::mt19937 rng(std::stoi(argv[1]));
    int n = rng() % 8 + 1;
    std::cout << n << '\n';
    for (int i = 0; i < n; ++i) std::cout << static_cast<int>(rng() % 21) - 10 << ' ';
    std::cout << '\n';
}

for i in $(seq 1 1000); do
  ./gen $i > in.txt
  ./sol < in.txt > a.txt;  ./brute < in.txt > b.txt
  cmp -s a.txt b.txt || { echo "mismatch, seed $i"; cat in.txt; break; }
done

generator-এ নির্দিষ্ট seed-এর std::mt19937, যাতে যে seed-এ ভুল ধরা পড়ল, সেটি দিয়ে একই ইনপুট আবার বানানো যায়। পুরো পদ্ধতি — কীভাবে ভুল ইনপুট আরও ছোট করবেন, কেন এটি মানুষের চোখের চেয়ে ভালো — C কোর্সের কনটেস্ট পর্বে বিস্তারিত; আর পর্ব ৪৮-এর টেস্টিংয়ের সাথে এর মিল লক্ষ করুন — এটি আসলে ছোট আকারের property-based testing.

WA-র চেনা কারণ — জমা দেওয়ার আগে একবার দেখুন

৮ · অনুশীলনের কৌশল আর কনটেস্টের নীতি

কীভাবে উন্নতি হয়

• rating-এর মই বেয়ে ওঠা: Codeforces-এ প্রতিটি সমস্যার একটি কঠিনতার রেটিং থাকে। নিজের বর্তমান rating-এর চেয়ে একটু (মোটামুটি ১০০–৩০০) বেশি কঠিন সমস্যা নিয়মিত করুন — খুব সহজ সমস্যায় আরাম, খুব কঠিনে হতাশা; শেখা হয় মাঝখানে। AtCoder-এর Beginner Contest-এর আগের সমস্যাগুলো শুরুর জন্য চমৎকার সিঁড়ি।
• upsolving: কনটেস্ট শেষে যে সমস্যা পারেননি, সেটি পরে সমাধান করা। বেশিরভাগ উন্নতি এখানেই হয়, কনটেস্টের সময়ে নয়। নিয়ম করুন: প্রতিটি কনটেস্টের পরে অন্তত একটি না-পারা সমস্যা।
• editorial পড়ার নিয়ম: অন্তত ৩০–৬০ মিনিট নিজে লড়াই করুন। তারপর editorial-এর শুধু প্রথম ইঙ্গিত পড়ে আবার চেষ্টা করুন। পুরো সমাধান পড়লে বন্ধ করে নিজে লিখুন — কপি করে নয়। শেষে লিখে রাখুন: “কোন ধারণাটি আমার মাথায় আসেনি, আর পরেরবার কোন লক্ষণ দেখে আসবে?”
• বিষয় ধরে গভীর চর্চা: একটি ছাঁচ (যেমন binary search on answer) নিয়ে টানা ১০–১৫টি সমস্যা। CSES Problem Set এর জন্য খুব ভালোভাবে সাজানো।

কনটেস্টের নীতি

কনটেস্টের মূল্য একটাই — এটি আপনার নিজের দক্ষতা মাপে। সেই মাপ মিথ্যা হলে rating-এর কোনো অর্থ থাকে না, আর বাকি প্রতিযোগীদের প্রতি অন্যায় হয়।

• plagiarism নয়। কনটেস্ট চলাকালীন অন্যের কোড নেওয়া, বন্ধুর সাথে সমাধান ভাগ করা, বা কোথাও প্রকাশিত সমাধান জমা দেওয়া — প্ল্যাটফর্মগুলো কোড-মিলের যন্ত্র দিয়ে এটি ধরে, আর শাস্তি হিসেবে ফল বাতিল থেকে অ্যাকাউন্ট বন্ধ পর্যন্ত হতে পারে।
• AI-এর নিয়ম আগে পড়ুন। AI এখন অনেক কনটেস্ট-সমস্যা নিজেই সমাধান করতে পারে, তাই অনেক প্ল্যাটফর্ম কনটেস্ট চলাকালীন AI দিয়ে সমাধান লেখানো সীমিত বা নিষিদ্ধ করেছে। নিয়ম প্ল্যাটফর্ম ভেদে আলাদা, আর সময়ের সাথে বদলায় — তাই প্রতিটি কনটেস্টের আগে সেই কনটেস্টের নিয়মটি নিজে পড়ুন। ICPC-র মতো সরাসরি উপস্থিতির কনটেস্টে ইন্টারনেটই থাকে না।
• নিজের আগে লেখা কোড (যেমন নিজের টেমপ্লেট বা লাইব্রেরি) ব্যবহার সাধারণত বৈধ — কিন্তু সেটিও নিয়মে দেখে নিন। ICPC-তে সাধারণত নির্দিষ্ট পাতার একটি ছাপানো নোট (team reference document) নেওয়া যায়।

৯ · AI-এর যুগে — নমুনায় পাস, গোপন টেস্টে ফেল

AI-কে একটি কনটেস্ট সমস্যা দিলে প্রায়ই এমন কোড আসে, যা নমুনা ইনপুটে নিখুঁত উত্তর দেয়। ঠিক এখানেই ফাঁদ: নমুনা ছোট, আর গোপন টেস্ট বড় ও নিষ্ঠুর। AI-এর সাধারণ ভুলগুলো প্রায় সবই এই দুই জগতের ফাঁকে পড়ে:

শেষ সারিটি সবচেয়ে সূক্ষ্ম। AI বিশাল পরিমাণ পুরোনো সমস্যা দেখে শিখেছে, তাই নতুন সমস্যাটি কোনো পুরোনো সমস্যার মতো দেখালে সে প্রায়ই পুরোনোটির সমাধান দেয় — একটি শর্তের পার্থক্য খেয়াল না করে।

AI-এর সবচেয়ে ভালো ব্যবহার কনটেস্টের পরে, শেখার জন্য — যদি সেই প্ল্যাটফর্মের নিয়ম তা অনুমতি দেয়। কনটেস্ট শেষে editorial বুঝতে না পারলে AI-কে একজন ধৈর্যশীল শিক্ষক হিসেবে ব্যবহার করুন — সমাধানদাতা হিসেবে নয়:

AI-এর কনটেস্ট-কোড যাচাইয়ের চেকলিস্ট

• কনটেস্টের নিয়মে AI-এর ব্যবহার অনুমোদিত কি না, নিজে পড়ে নিশ্চিত হয়েছি — না হলে কনটেস্ট চলাকালীন ব্যবহার করিনি
• n-এর সর্বোচ্চ মান বসিয়ে অপারেশন গুনেছি — ১০^৮-এর আশেপাশে বা নিচে
• সবচেয়ে বড় সম্ভাব্য যোগফল/গুণফল হিসাব করেছি, আর সেখানে ll আছে
• প্রতিটি test case-এর অবস্থা নতুন করে শুরু হয়, আর পুরো ইনপুট পড়া হয়
• greedy বা অন্য “চালাক” সমাধান হলে brute force দিয়ে ছোট এলোমেলো টেস্টে মিলিয়েছি
• সমাধানটি আমি নিজের ভাষায় ব্যাখ্যা করতে পারি — না পারলে সেটি এখনো আমার শেখা হয়নি