কনটেস্টের অনুশীলন — ICPC-ধাঁচের সমস্যা সেট

১ · কনটেস্টের দুনিয়া — দলগত ICPC আর ব্যক্তিগত অনলাইন রাউন্ড

Competitive programming মানে নির্দিষ্ট সময়ের মধ্যে কয়েকটি অ্যালগরিদম-নির্ভর সমস্যা সঠিক আর যথেষ্ট দ্রুতভাবে সমাধান করা। আপনি কোড জমা দেন, আর একটি online judge সেটি গোপন টেস্ট ইনপুটে চালিয়ে রায় দেয়। এখানে কেউ আপনার কোডের সৌন্দর্য দেখে না, দেখে শুধু তিনটি জিনিস: উত্তর ঠিক কি না, সময়ের ভেতরে কি না, আর মেমরির ভেতরে কি না। পুরো কোর্সে যা শিখেছেন — complexity, ডেটা স্ট্রাকচার, প্রমাণ — এখানে সবই চাপের মধ্যে পরীক্ষা হয়।

ICPC-ধাঁচের দলগত কনটেস্ট

ICPC (International Collegiate Programming Contest) বিশ্ববিদ্যালয়ের শিক্ষার্থীদের সবচেয়ে পরিচিত দলগত প্রোগ্রামিং প্রতিযোগিতা। বাংলাদেশে এর আঞ্চলিক পর্বের পাশাপাশি NCPC, IUPC-র মতো অনেক কনটেস্ট একই ধাঁচে হয়। নিয়ম জায়গাভেদে একটু আলাদা হতে পারে, তবে মূল কাঠামো সাধারণত এমন:

• তিনজনের দল, একটি কম্পিউটার। তিনজন মাথা কিন্তু একটি কিবোর্ড। তাই কে কখন টাইপ করবে, কে কাগজে ভাববে — এটিই দলের সবচেয়ে বড় সিদ্ধান্ত (অংশ ৭)।
• সাধারণত পাঁচ ঘণ্টা, দশ-বারোটির মতো সমস্যা। সমস্যাগুলো A, B, C… নামে থাকে, কিন্তু কঠিনতার ক্রমে সাজানো থাকে এমন কোনো নিশ্চয়তা নেই।
• র‍্যাংক প্রথমে সমাধান করা সমস্যার সংখ্যায়। সমান হলে কম মোট penalty time যার, সে এগিয়ে।
• Penalty-র হিসাব: প্রতিটি সমাধান করা সমস্যার জন্য কনটেস্ট শুরু থেকে সেটি accepted হওয়া পর্যন্ত মিনিট, আর সেই সমস্যায় আগের প্রতিটি ভুল জমার জন্য বাড়তি সময় (প্রচলিত নিয়মে ২০ মিনিট)। যে সমস্যা শেষ পর্যন্ত সমাধান হয়নি, তার ভুল জমা কোনো penalty যোগ করে না।
• Scoreboard freeze: শেষ অংশে (প্রায়ই শেষ এক ঘণ্টা) স্কোরবোর্ড থেমে যায়। আপনি নিজের রায় জানেন, অন্যদের নতুন সমাধান জানেন না। চূড়ান্ত ফল পরে একসাথে প্রকাশ হয় — এজন্য শেষ ঘণ্টায় “আমরা কোথায় আছি” না ভেবে যত বেশি সম্ভব সমাধানের দিকে মন দিতে হয়।
• ইন্টারনেট ছাড়া। on-site কনটেস্টে সাধারণত ইন্টারনেট বা AI ব্যবহারের সুযোগ নেই; অনেক জায়গায় ছাপানো কাগজের নোট (team notebook) নেওয়া যায়, আর কোড প্রিন্ট করার ব্যবস্থা থাকে। কোন জিনিস নেওয়া যাবে, তা প্রতিটি কনটেস্টের নিয়মে লেখা থাকে — আগে পড়ে নিন।

ব্যক্তিগত অনলাইন রাউন্ড

Codeforces, AtCoder বা বাংলাদেশি প্ল্যাটফর্ম Toph-এর মতো জায়গায় নিয়মিত অনলাইন কনটেস্ট হয়। এগুলো সাধারণত ব্যক্তিগত, দুই-আড়াই ঘণ্টার, আর বাসা থেকেই দেওয়া যায়। প্ল্যাটফর্মভেদে নিয়ম আলাদা — কোথাও ICPC-র মতো penalty, কোথাও সময়ের সাথে কমতে থাকা নম্বর, কোথাও কনটেস্ট চলাকালে শুধু কয়েকটি প্রাথমিক টেস্ট (pretest) আর শেষে পুরো টেস্ট। তাই প্রতিটি প্ল্যাটফর্মের নিয়মের পাতা একবার পড়ে নিন।

বেশিরভাগ প্ল্যাটফর্মে প্রতিটি রেটেড কনটেস্টের পর একটি rating বাড়ে বা কমে — প্রত্যাশার চেয়ে ভালো করলে বাড়ে। রেটিং দক্ষতার একটি মোটা দাগের মাপ, কিন্তু একদিনের খারাপ কনটেস্ট নিয়ে মন খারাপ করার কিছু নেই; দীর্ঘ সময়ের প্রবণতাই আসল। অনলাইন রাউন্ডের সবচেয়ে বড় উপহার হলো কনটেস্টের পরের editorial — সমস্যা-নির্মাতাদের লেখা সমাধান-ব্যাখ্যা। অংশ ৮-এ দেখব, শেখা আসলে ঘটে কনটেস্টের পরে।

২ · Judge-এর রায় — AC, WA, TLE, MLE, RE, CE মানে কী

প্রতিটি জমার পর judge একটি verdict দেয়। সাধারণত টেস্টগুলো ক্রমে চলে আর প্রথম যে টেস্টে সমস্যা হয়, সেটির রায় দেখানো হয়। তাই “WA on test 1” আর “WA on test 37” খুব আলাদা খবর: প্রথমটি মানে নমুনাতেই ভুল (বা আউটপুটের বিন্যাস ভুল), দ্বিতীয়টি মানে মূল ধারণা প্রায় ঠিক, কিন্তু কোনো বিশেষ ক্ষেত্র বাদ পড়েছে।

কিছু judge-এ আরও রায় থাকে — যেমন Presentation Error (উত্তর ঠিক, কিন্তু স্পেস বা নতুন লাইনের বিন্যাস ভুল), বা interactive সমস্যায় Idleness Limit. আজকাল বেশিরভাগ judge বাড়তি স্পেস উপেক্ষা করে, তবু বিবরণে যেভাবে চাওয়া হয়েছে ঠিক সেভাবে ছাপানো নিরাপদ। একটি গুরুত্বপূর্ণ সতর্কতা: C++-এ undefined behavior (যেমন সীমার বাইরে লেখা) সবসময় RE দেয় না — কখনো চুপচাপ অন্য ভেরিয়েবল নষ্ট করে WA দেয়। তাই WA পেলে সীমার বাইরের access-ও সন্দেহের তালিকায় রাখুন।

নিচের ডায়াগ্রামে একটি রায় পেলে কোন ক্রমে প্রশ্ন করবেন, তা দেখুন। ক্রমটি গুরুত্বপূর্ণ: আগে সস্তা পরীক্ষা (compile হয় কি না), শেষে দামি পরীক্ষা (ধারণাটাই ভুল কি না)।

1. Language: C++ (GNU C++17/20/23?) ঠিক বাছা হয়েছে?
2. লোকাল compiler-এ -Wall দিয়ে compile করেছি?
3. অপ্রচলিত header বা ফাংশন (conio.h, getch) আছে?
4. ভুল ফাইল জমা দিইনি তো?

1. অ্যারের আকার সর্বোচ্চ n-এর চেয়ে ছোট? (a[n] না a[n+1]?)
2. কোথাও শূন্য দিয়ে ভাগ বা mod?
3. recursion-এর গভীরতা 10^5-10^6 হতে পারে?
4. খালি stack/queue থেকে top() বা pop()?
5. main() শেষে return 0?

1. সর্বোচ্চ সীমায় মোট কাজ কত? (10^8-এর বেশি?)
2. fast I/O আছে? endl-এর বদলে '\n'?
3. T টি টেস্টে প্রতিবার পুরো MAX আকারের অ্যারে মুছছি?
4. কোনো লুপ শেষই হয় না এমন ইনপুট আছে?
5. Dijkstra-য় পুরোনো (stale) entry বাদ দিচ্ছি?

1. টেবিলের আকার x প্রতি ঘরের বাইট = কত MB?
   (5000 x 5000 long long = 200 MB!)
2. DP-তে শুধু আগের সারি লাগে? (rolling array)
3. ফাংশনে বড় vector মান হিসেবে (কপি) পাঠাচ্ছি?
4. BFS-এ একই ঘর বারবার queue-তে ঢুকছে?

1. overflow: int-এ 2.1 x 10^9 পেরোয় এমন গুণ বা যোগ?
2. একাধিক টেস্ট: আগের টেস্টের ডেটা মুছেছি?
3. edge case: n = 1, সব সমান, উত্তর 0 বা -1?
4. আউটপুটের বিন্যাস: প্রতি লাইনে একটি? YES না Yes?
5. তারপরও না মিললে: brute force + stress test (অংশ ৮)
6. শেষে সন্দেহ ধারণাতেই: greedy-র প্রমাণ আছে?

1. দলের খাতায় লিখুন: কোন সমস্যা, কত মিনিটে।
2. স্কোরবোর্ড দেখে পরের সমস্যা বাছুন।
3. কনটেস্টের পরে: কোডটি পরিষ্কার করে
   নিজের লাইব্রেরিতে রাখুন।

৩ · সীমা পড়ে লক্ষ্য ঠিক করা — complexity টেবিল, fast I/O আর C++ template

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

টেবিলটি উল্টো দিকেও কাজ করে, আর সেটাই আসল কৌশল: n ≤ 18 দেখলেই মাথায় আসা উচিত “সম্ভবত subset বা bitmask”; n ≤ 10¹⁸ দেখলে “লুপ চলবে না, সূত্র বা log”. একই সাথে সংখ্যার আকারও দেখুন: মান 10⁹ পর্যন্ত আর সেগুলোর যোগ বা গুণ লাগলে long long. আর মোট ইনপুটের আকার দেখুন — “সব টেস্ট মিলিয়ে n-এর যোগফল ≤ 2 × 10⁵” ধরনের বাক্য বলে দেয়, প্রতিটি টেস্টে O(n log n) নিরাপদ, কিন্তু প্রতিটি টেস্টে 10⁶ আকারের অ্যারে মোছা নয়।

দ্রুত ইনপুট-আউটপুট

লাখ লাখ সংখ্যা পড়তে-লিখতে সময়ের বড় অংশ যেতে পারে। C++-এ fast I/O-এর দুই লাইন — ios::sync_with_stdio(false); (C-এর printf/scanf-এর সাথে সমন্বয় বন্ধ, তাই cin/cout নিজের buffer ব্যবহার করে) আর cin.tie(nullptr); (প্রতিটি cin-এর আগে cout খালি করা বন্ধ)। এর পর একই প্রোগ্রামে cin আর scanf মেশাবেন না। আর endl নয়, '\n' — কারণ endl প্রতিবার buffer খালি করে (flush), দশ লাখ লাইনে যা বড় খরচ। Python-এ লাইন ধরে input()-এর বদলে একবারে sys.stdin.buffer.read().split(), আর আউটপুট একটি "\n".join(...)-এ।

একটি পরিষ্কার C++ contest template

অনেকে কনটেস্টে লম্বা macro-ভরা template ব্যবহার করেন। শুরুতে তার দরকার নেই — ছোট, পড়া যায় এমন template-এ ভুল কম, আর দলের অন্য সদস্যও কোড পড়তে পারেন। নিচের template-টি এই পাতার প্রথম সমস্যার (A) সমাধানসহ; প্রতিটি লাইনের ব্যাখ্যা নিচে।

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    ll n, a, b;
    cin >> n >> a >> b;
    ll x = a / gcd(a, b);                       // lcm(a, b) = x * b, which may overflow
    ll both = (x > n / b) ? 0 : n / (x * b);    // lcm > n: no number <= n has both gifts
    cout << n / a + n / b - both << '\n';       // inclusion-exclusion
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

1. #include <bits/stdc++.h> — GCC-র একটি সুবিধাজনক header, যা প্রায় সব standard header একসাথে আনে। কনটেস্টে প্রচলিত, কারণ judge-এ প্রায় সবসময় GCC. পেশাদার কোডে এটি ব্যবহার করবেন না — এটি standard নয়, আর compile ধীর করে। কিছু অনলাইন compiler-এ <cassert>-এর মতো দু-একটি header আলাদা করে লাগতে পারে।
2. using namespace std; — প্রতিবার std:: লেখা থেকে মুক্তি। কনটেস্টে ঠিক আছে; শুধু নিজের ভেরিয়েবলের নাম count, find বা gcd-এর মতো লাইব্রেরির নামের সাথে মিলে গেলে বিভ্রান্তি হতে পারে।
3. using ll = long long; — একমাত্র “সংক্ষেপ”, কারণ long long বারবার লাগে। অনেকে #define int long long লেখেন; আমরা এড়িয়ে যাই, কারণ এতে সব int চুপচাপ বদলে যায়, মেমরি দ্বিগুণ হয়, আর main-কে signed main লিখতে হয় — নতুনদের জন্য বিভ্রান্তিকর।
4. void solve() — একটি টেস্টের পুরো কাজ এক ফাংশনে। এর প্রধান সুবিধা: ভেরিয়েবলগুলো ফাংশনের ভেতরে লোকাল, তাই প্রতিটি টেস্টে নিজে থেকেই নতুন করে তৈরি হয় — আগের টেস্টের ডেটা পরের টেস্টে ঢোকার ভুল (অংশ ৪) প্রায় অসম্ভব।
5. ios::sync_with_stdio(false); cin.tie(nullptr); — fast I/O, ওপরে ব্যাখ্যা করা হয়েছে। main-এর একেবারে শুরুতে, কোনো পড়া-লেখার আগে।
6. int t = 1; cin >> t; — একাধিক টেস্ট কেস-এর সমস্যায় প্রথমে T. একটিমাত্র টেস্টের সমস্যায় শুধু cin >> t; লাইনটি মুছে দিন — t = 1 থেকে যায়, বাকি সব একই।
7. while (t--) solve(); — T বার solve(). শেষে return 0; — কিছু judge শূন্য ছাড়া exit code পেলে RE দেয়।

আরেকটি অভ্যাস: লোকাল কম্পিউটারে g++ -std=c++20 -O2 -Wall -Wextra -fsanitize=address,undefined দিয়ে compile করে নমুনা চালান (sanitizer Linux আর macOS-এ সহজে চলে)। Sanitizer সীমার বাইরের access আর signed overflow-এর মতো undefined behavior চালানোর সময় ধরিয়ে দেয় — যে ভুলগুলো judge-এ রহস্যময় WA হয়ে দেখা দিত।

৪ · যে বাগগুলো বারবার ফিরে আসে — overflow, না-মোছা ডেটা, off-by-one আর recursion-এর গভীরতা

কনটেস্টে হারানো বেশিরভাগ মিনিট “কঠিন” ভুলে যায় না, যায় কয়েকটি পরিচিত ভুলে। এগুলোর একটি তালিকা মুখস্থ রাখুন, আর জমা দেওয়ার আগে এক নজর দেখে নিন।

আরও কয়েকটি পরিচিত মুখ: সমস্যা বলে “উত্তর 10⁹ + 7 দিয়ে mod করে” — আর আপনি বিয়োগের পর ঋণাত্মক মান ছাপালেন ((a - b) % M C++-এ ঋণাত্মক হতে পারে, ঠিক রূপ ((a - b) % M + M) % M); দশমিক সংখ্যা == দিয়ে তুলনা; “কোনো উত্তর না থাকলে -1” অংশটি ভুলে যাওয়া; আর একই সমস্যার দুই অংশে একই ভেরিয়েবলের নাম ব্যবহার। এগুলোর প্রতিটির জন্য একটি ছোট নিয়ম রাখুন, আর অংশ ৮-এর stress test দিয়ে বাকিগুলো ধরুন।

৫ · সমস্যা সেট, প্রথম ভাগ — A থেকে E

এবার আসল কাজ। নিচের দশটি সমস্যা একটি ছোট ICPC-ধাঁচের সেট হিসেবে সাজানো, সহজ থেকে কঠিন ক্রমে, আর প্রতিটি কোর্সের কোনো একটি মডিউলের এক বা একাধিক কৌশল চায়। আসল কনটেস্টে কোনো সমস্যার গায়ে “এটি DSU-র সমস্যা” লেখা থাকে না — তাই নিচের তালিকাটি শুধু পড়া শেষে মেলানোর জন্য; চাইলে না দেখে শুরু করুন।

প্রতিটি সমস্যার সময়সীমা ১ সেকেন্ড আর মেমরি ২৫৬ MB, অন্য কিছু বলা না থাকলে। গল্পের নাম, জায়গা আর সংখ্যা বোঝার জন্য বানানো।

সমস্যা A · মেট্রো রেলের উপহার (সহজ)

Input
3
10 2 3
1000000000000000000 1000000000000000000 999999999999999999
15 5 5

Output
7
2
3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    ll n, a, b;
    cin >> n >> a >> b;
    ll x = a / gcd(a, b);                       // lcm(a, b) = x * b, which may overflow
    ll both = (x > n / b) ? 0 : n / (x * b);    // lcm > n: no number <= n has both gifts
    cout << n / a + n / b - both << '\n';       // inclusion-exclusion
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

7
2
3

import sys
from math import gcd

def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    for i in range(t):
        n, a, b = (int(x) for x in data[1 + 3 * i: 4 + 3 * i])
        lcm = a // gcd(a, b) * b          # Python integers never overflow
        out.append(n // a + n // b - n // lcm)
    print("\n".join(map(str, out)))

main()

7
2
3

সমস্যা B · নৌকায় নদী পার (সহজ)

Input
5 100
60 40 70 30 90

Output
3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll C;
    cin >> n >> C;
    vector<ll> w(n);
    for (auto& x : w) cin >> x;
    sort(w.begin(), w.end());
    int i = 0, j = n - 1, boats = 0;
    while (i <= j) {                    // j = heaviest person still on the bank
        if (i < j && w[i] + w[j] <= C)  // the lightest one can go with him
            ++i;
        --j;                            // the heaviest always leaves now
        ++boats;
    }
    cout << boats << '\n';
}

3

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, C = int(data[0]), int(data[1])
    w = sorted(map(int, data[2:2 + n]))
    i, j, boats = 0, n - 1, 0
    while i <= j:                      # j = heaviest person still on the bank
        if i < j and w[i] + w[j] <= C:
            i += 1                     # the lightest one goes with him
        j -= 1
        boats += 1
    print(boats)

main()

3

সমস্যা C · খাতা দেখার ভাগ (সহজ–মাঝারি)

Input
7 3
10 20 30 40 50 60 70

Output
110

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;
    auto need = [&](ll X) {             // examiners needed if nobody checks more than X
        int cnt = 1;
        ll cur = 0;
        for (ll x : a) {
            if (cur + x > X) { ++cnt; cur = 0; }
            cur += x;
        }
        return cnt;
    };
    ll lo = *max_element(a.begin(), a.end());
    ll hi = accumulate(a.begin(), a.end(), 0LL);
    while (lo < hi) {                   // smallest X with need(X) <= k
        ll mid = lo + (hi - lo) / 2;
        if (need(mid) <= k) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << '\n';
}

110

সমস্যা D · কোচিং রুমের ভিড় (মাঝারি)

Input
10 4 2 3
1 4
3 7
6 10
4 5
1 10
5 9
8 10

Output
5
3
0

vector<int> D(N + 2, 0), P(N + 1, 0);
for (int j = 0; j < m; ++j) { int l, r; cin >> l >> r; D[l]++; D[r + 1]--; }
int cur = 0;
for (int i = 1; i <= N; ++i) { cur += D[i]; P[i] = P[i - 1] + (cur >= K); }
while (q--) { int x, y; cin >> x >> y; cout << P[y] - P[x - 1] << '\n'; }

সমস্যা E · জলাবদ্ধ শহর (মাঝারি)

Input
4 7
S......
+##W##+
+#####E
+++++++

Output
10

#include <bits/stdc++.h>
using namespace std;

int main() {
    int R, C;
    cin >> R >> C;
    vector<string> g(R);
    for (auto& row : g) cin >> row;
    const int INF = INT_MAX, dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    vector<vector<int>> wt(R, vector<int>(C, INF)), d(R, vector<int>(C, -1));
    queue<pair<int, int>> q;
    for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j)
        if (g[i][j] == 'W') { wt[i][j] = 0; q.push({i, j}); }
    while (!q.empty()) {                          // BFS 1: water, from every source together
        auto [i, j] = q.front(); q.pop();
        for (int k = 0; k < 4; ++k) {
            int x = i + dr[k], y = j + dc[k];
            if (x < 0 || y < 0 || x >= R || y >= C || g[x][y] == '#' || g[x][y] == '+' || wt[x][y] != INF) continue;
            wt[x][y] = wt[i][j] + 1; q.push({x, y});
        }
    }
    for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j)
        if (g[i][j] == 'S') { d[i][j] = 0; q.push({i, j}); }
    while (!q.empty()) {                          // BFS 2: Rafi, only into cells still dry
        auto [i, j] = q.front(); q.pop();
        if (g[i][j] == 'E') { cout << d[i][j] << '\n'; return 0; }
        for (int k = 0; k < 4; ++k) {
            int x = i + dr[k], y = j + dc[k];
            if (x < 0 || y < 0 || x >= R || y >= C || g[x][y] == '#' || d[x][y] != -1) continue;
            if (d[i][j] + 1 < wt[x][y]) { d[x][y] = d[i][j] + 1; q.push({x, y}); }
        }
    }
    cout << -1 << '\n';
}

10

৬ · সমস্যা সেট, দ্বিতীয় ভাগ — F থেকে J

এখান থেকে সমস্যাগুলোয় একটি করে “চাবি” লুকানো থাকে — সঠিক ডেটা স্ট্রাকচার, বা অবস্থার (state) সঠিক সংজ্ঞা। চাবিটি পেলে কোড প্রায়ই ছোট; না পেলে কোনো optimization কাজে আসে না।

সমস্যা F · গ্রামে বিদ্যুতের লাইন (মাঝারি)

Input
6 5
1 2
3 4
2 3
1 4
5 6

Output
5 2
4 2
3 4
3 4
2 4

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> par(n + 1), sz(n + 1, 1);
    iota(par.begin(), par.end(), 0);
    auto find = [&](int x) {
        while (par[x] != x) x = par[x] = par[par[x]];   // path halving, no recursion
        return x;
    };
    int comps = n, biggest = 1;
    while (q--) {
        int u, v;
        cin >> u >> v;
        int a = find(u), b = find(v);
        if (a != b) {
            if (sz[a] < sz[b]) swap(a, b);              // union by size
            par[b] = a;
            sz[a] += sz[b];
            --comps;
            biggest = max(biggest, sz[a]);
        }
        cout << comps << ' ' << biggest << '\n';
    }
}

5 2
4 2
3 4
3 4
2 4

সমস্যা G · এক রাস্তায় অর্ধেক ভাড়া (মাঝারি–কঠিন)

Input
5 6
1 2 10
2 5 10
1 3 4
3 4 4
4 5 9
3 5 20

Output
12

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, ll>>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v; ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    const ll INF = LLONG_MAX;
    vector<array<ll, 2>> d(n + 1, {INF, INF});      // d[v][c]: c = 1 if the coupon is used
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
    d[1][0] = 0;
    pq.push({0, 1, 0});
    auto relax = [&](int v, int c, ll nd) {
        if (nd < d[v][c]) { d[v][c] = nd; pq.push({nd, v, c}); }
    };
    while (!pq.empty()) {
        auto [du, u, c] = pq.top(); pq.pop();
        if (du != d[u][c]) continue;                 // stale entry
        for (auto [v, w] : adj[u]) {
            relax(v, c, du + w);                     // pay full fare
            if (c == 0) relax(v, 1, du + w / 2);     // use the coupon on this road
        }
    }
    ll ans = min(d[n][0], d[n][1]);
    cout << (ans == INF ? -1 : ans) << '\n';
}

12

সমস্যা H · ফ্রিল্যান্সারের কাজ বাছাই (মাঝারি–কঠিন)

Input
5
1 3 50
2 5 20
4 6 70
6 7 60
8 9 30

Output
150

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<array<ll, 3>> job(n);                     // {end, start, pay}
    for (auto& [e, s, p] : job) cin >> s >> e >> p;
    sort(job.begin(), job.end());                    // by end day
    vector<ll> ends(n), dp(n + 1, 0);                // dp[i] = best using the first i jobs
    for (int i = 0; i < n; ++i) ends[i] = job[i][0];
    for (int i = 1; i <= n; ++i) {
        auto [e, s, p] = job[i - 1];
        // jobs that finish before day s are exactly the first k ones
        int k = lower_bound(ends.begin(), ends.begin() + (i - 1), s) - ends.begin();
        dp[i] = max(dp[i - 1], dp[k] + p);           // skip job i, or take it
    }
    cout << dp[n] << '\n';
}

150

সমস্যা I · গুদামের সর্বনিম্ন মজুত (কঠিন)

Input
6 6
5 3 3 8 3 9
2 1 6
1 3 1
2 2 4
2 4 6
1 5 8
2 4 6

Output
3 3
1 1
3 1
8 2

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;                            // {minimum, how many times}

P combine(P a, P b) {
    if (a.first != b.first) return min(a, b);
    return {a.first, a.second + b.second};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<P> t(2 * n);                              // iterative segment tree, leaves at n..2n-1
    for (int i = 0; i < n; ++i) { cin >> t[n + i].first; t[n + i].second = 1; }
    for (int i = n - 1; i >= 1; --i) t[i] = combine(t[2 * i], t[2 * i + 1]);
    while (q--) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) {                             // stock of shop x becomes y
            int i = n + x - 1;
            t[i] = {y, 1};
            for (i /= 2; i >= 1; i /= 2) t[i] = combine(t[2 * i], t[2 * i + 1]);
        } else {                                     // query on shops x..y
            P res = {INT_MAX, 0};
            for (int l = n + x - 1, r = n + y; l < r; l /= 2, r /= 2) {
                if (l & 1) res = combine(res, t[l++]);
                if (r & 1) res = combine(res, t[--r]);
            }
            cout << res.first << ' ' << res.second << '\n';
        }
    }
}

3 3
1 1
3 1
8 2

সমস্যা J · ডেলিভারি রাইডারের পথ (কঠিন)

Input
4
0 4 9 3
4 0 2 7
9 2 0 5
3 7 5 0

Output
10

const int INF = 1e9;
vector<vector<int>> dp(1 << n, vector<int>(n, INF));
dp[1][0] = 0;                                    // only the warehouse visited, standing there
for (int mask = 1; mask < (1 << n); ++mask)
    for (int v = 0; v < n; ++v) {
        if (dp[mask][v] == INF) continue;
        for (int u = 0; u < n; ++u)
            if (!(mask >> u & 1))
                dp[mask | 1 << u][u] = min(dp[mask | 1 << u][u], dp[mask][v] + d[v][u]);
    }
cout << *min_element(dp[(1 << n) - 1].begin(), dp[(1 << n) - 1].end()) << '\n';

৭ · দলের কৌশল — পাঁচ ঘণ্টা, তিনজন, একটি কম্পিউটার

একই দক্ষতার দুটি দলের ফল প্রায়ই আলাদা হয় শুধু কৌশলের কারণে। কয়েকটি নিয়ম, যা বেশিরভাগ অভিজ্ঞ দল কোনো না কোনো রূপে মানে:

• প্রথম ১৫–২০ মিনিটে সব সমস্যা পড়া। সমস্যাগুলো তিন ভাগে ভাগ করে প্রত্যেকে পড়ুন, আর দলের খাতায় প্রতিটির এক লাইনের সারাংশ, সীমা আর আনুমানিক কঠিনতা লিখুন। সবচেয়ে সহজটি যে চিনবেন, তিনি সাথে সাথে কম্পিউটারে।
• কঠিনতা অনুযায়ী সাজানো, আর স্কোরবোর্ড পড়া। সমস্যার ক্রম কঠিনতার ক্রম নয়। কনটেস্ট চলাকালে স্কোরবোর্ডে দেখুন অনেক দল কোনটি সমাধান করছে — সেটি সম্ভবত সহজ। ফ্রিজের পর এই তথ্য আর আসে না, তাই তার আগেই পরিকল্পনা ঠিক করুন।
• কম্পিউটার কখনো খালি নয়, কখনো চিন্তার জায়গাও নয়। কোড কাগজে প্রায় তৈরি হলে তবেই কিবোর্ডে। কেউ টাইপ করার সময় বাকি দুজন পরের সমস্যা ভাবেন বা হাতে নমুনা মেলান।
• WA পেলে প্রিন্ট করে সরে যান। কম্পিউটারের সামনে বসে ডিবাগ করা মানে অন্য সবার সময় আটকে রাখা। কোড প্রিন্ট করুন (বা স্ক্রিনের ছবি খাতায় তুলুন), কম্পিউটার ছেড়ে দিন, আর কাগজে খুঁজুন — ভালো হয় আরেকজনকে নিয়ে জোড়ায় ডিবাগ: আপনি লাইন ধরে জোরে ব্যাখ্যা করবেন, তিনি প্রশ্ন করবেন। নিজের কোডে যে ভুল চোখে পড়ে না, অন্যের চোখে প্রায়ই সেকেন্ডে পড়ে।
• আটকে গেলে ছেড়ে দেওয়ার সাহস। একটি সমস্যায় ৪০–৫০ মিনিট কোনো অগ্রগতি না হলে দলে কথা বলুন — হয় অন্যজন নতুন চোখে দেখুন, নয়তো অন্য সমস্যায় যান।
• শেষ ঘণ্টায় একটি লক্ষ্য. দুটি আধা-সমাধানের চেয়ে একটি সম্পূর্ণ সমাধান ভালো। ফ্রিজের পর সবাই মিলে যে সমস্যাটি সবচেয়ে কাছে, সেটিতে।

নিচে একটি কাল্পনিক দলের (রাফি, নীলা, তানভীর) পাঁচ ঘণ্টা দেখুন — এই পাতার সমস্যা সেটেই। প্রতিটি ধাপে penalty-র হিসাবটি মিলিয়ে নিন।

এই হিসাব থেকে একটি শিক্ষা: সমাধানের সময়ের যোগফলই penalty-র বড় অংশ, তাই সহজ সমস্যা আগে করা প্রায় সবসময় ভালো — একটি সমস্যায় যত মিনিট লাগে, তা তার পরে সমাধান হওয়া প্রতিটি সমস্যার AC-মুহূর্তে যোগ হয়ে যায়। ছোট কাজ আগে সারলে সেই ছোট সময়টুকুই পরের সবগুলোতে যোগ হয়, লম্বা কাজ আগে করলে লম্বা সময়টা। আর প্রতিটি ভুল জমা ২০ মিনিট — তাই জমার আগে অংশ ৪-এর ৩০ সেকেন্ডের চেকলিস্ট আসলে সময় বাঁচায়।

৮ · অনুশীলনের পরিকল্পনা — upsolving, virtual contest, বিষয়ের মই আর stress testing

কনটেস্টে আপনি যা জানেন তা দেখান; শেখেন কনটেস্টের পরে. নিয়মিত উন্নতির জন্য চারটি অভ্যাস:

1. Upsolving. প্রতিটি কনটেস্টের পর অন্তত পরের এক-দুটি সমস্যা, যা পারেননি, শেষ করুন — আগে নিজে, তারপর editorial-এর একটি ইঙ্গিত, তারপর পুরো ব্যাখ্যা। editorial পড়ে বুঝে নিজে কোড লিখুন, কপি নয়। শেষে খাতায় তিন লাইন: কোন পর্যবেক্ষণ মিস করেছিলাম, কোন সংকেত দেখে পরের বার চিনব, কোন ভুল কোডে ঢুকেছিল।
2. Virtual contest. পুরোনো একটি কনটেস্ট আসল সময় ধরে দিন, যেন সত্যিই চলছে — মাঝে editorial বা অন্য কিছু দেখবেন না। দলগতভাবে করলে একটি কম্পিউটারের নিয়মও মানুন। এটিই চাপের মধ্যে সিদ্ধান্ত নেওয়ার একমাত্র অনুশীলন।
3. বিষয়ের মই (topic ladder). নিজের স্তরের একটু ওপরের সমস্যা বেছে বিষয় ধরে ধরে এগোন। নিচের টেবিলটি এই কোর্সের পর্বের সাথে মিলিয়ে একটি ক্রম:
4. নিজের ভুলের খাতা আর লাইব্রেরি. একই ভুল দ্বিতীয়বার করলে খাতায় লাল দাগ। আর প্রতিটি পরীক্ষিত কোড (DSU, segment tree…) একটি ফোল্ডারে — পরে team notebook এখান থেকেই।

Stress testing — যখন WA আসে কিন্তু কারণ খুঁজে পান না

পর্ব ৬৭-এর ক্যাপস্টোনে পুরো পদ্ধতিটি দেখেছেন; এখানে কনটেস্টের ছোট রূপ। Stress testing-এর চারটি অংশ: (১) একটি সরল, নিশ্চিতভাবে সঠিক brute force — ধীর হলেও চলবে; (২) একটি test generator, যা নির্দিষ্ট seed থেকে খুব ছোট এলোমেলো ইনপুট বানায়; (৩) একটি লুপ, যা দুটি সমাধান চালিয়ে উত্তর মেলায়; (৪) অমিল পেলে সবচেয়ে ছোট ইনপুটটি ছাপানো, যাতে হাতে trace করা যায়। ICPC-তে ইন্টারনেট নেই, কিন্তু কম্পিউটার আছে — দশ মিনিটে লেখা একটি stress test প্রায়ই এক ঘণ্টার অন্ধ খোঁজ বাঁচায়।

নিচের প্রোগ্রামটি সমস্যা B-এর greedy-কে একটি brute force দিয়ে যাচাই করে: brute force প্রতিটি মানুষের জন্য সব বিকল্প (একা, অথবা প্রতিটি সম্ভাব্য সঙ্গী) চেষ্টা করে — কোনো সাজানো বা greedy যুক্তি ব্যবহার না করে।

#include <bits/stdc++.h>
using namespace std;

int greedy(vector<int> w, int C) {                   // the solution we want to trust
    sort(w.begin(), w.end());
    int i = 0, j = (int)w.size() - 1, boats = 0;
    while (i <= j) { if (i < j && w[i] + w[j] <= C) ++i; --j; ++boats; }
    return boats;
}
int brute(vector<int> w, int C) {                    // try every way: alone, or with someone
    if (w.empty()) return 0;
    int f = w.back(); w.pop_back();
    int best = 1 + brute(w, C);
    for (size_t k = 0; k < w.size(); ++k)
        if (f + w[k] <= C) {
            vector<int> rest = w;
            rest.erase(rest.begin() + k);
            best = min(best, 1 + brute(rest, C));
        }
    return best;
}
int main() {
    mt19937 rng(2026);                               // fixed seed: the same tests every run
    for (int t = 1; t <= 2000; ++t) {
        int n = rng() % 8 + 1, C = rng() % 20 + 1;
        vector<int> w(n);
        for (int& x : w) x = rng() % C + 1;          // 1..C, everyone fits alone
        if (greedy(w, C) != brute(w, C)) {
            printf("MISMATCH on test %d, C = %d\n", t, C);
            return 0;
        }
    }
    printf("all 2000 random tests passed\n");
}

all 2000 random tests passed

৯ · AI-এর যুগে — অনুশীলনে সহকারী, কনটেস্টে নিয়ম মানা

আগে নিয়ম: on-site ICPC-ধাঁচের কনটেস্টে ইন্টারনেট আর AI ব্যবহারের সুযোগ সাধারণত থাকে না। অনেক অনলাইন প্ল্যাটফর্মও রেটেড রাউন্ড চলাকালে AI দিয়ে সমাধান লেখানো নিষেধ বা কঠোরভাবে সীমিত করেছে — আর নিয়ম বদলায়, তাই প্রতিটি প্ল্যাটফর্মের সর্বশেষ নিয়ম নিজে পড়ে নিন। নিয়ম ভাঙা শুধু অন্যায় নয়, নিজের প্রস্তুতিকেও ফাঁকি: আসল ICPC-র মঞ্চে AI থাকবে না।

কিন্তু অনুশীলনে — কনটেস্টের বাইরে, upsolving-এর সময় — AI একটি শক্তিশালী সহকারী হতে পারে, যদি তাকে উত্তর লেখার বদলে আপনার চিন্তা পরীক্ষার কাজ দেন। মনে রাখবেন, AI প্রায়ই আত্মবিশ্বাসের সাথে ভুল complexity বলে, off-by-one-এ ভুল করে, প্রমাণহীন greedy দেয় (সমস্যা B-এর মতো সমস্যায় “সবচেয়ে ভারী দুজনকে একসাথে” ধরনের ভুল নিয়ম), আর সমস্যা A-র মতো overflow প্রায়ই ভুলে যায়।

AI-এর সাহায্য নেওয়ার পর নিজেকে যাচাইয়ের চেকলিস্ট

• যে কনটেস্টে AI নিষেধ, সেখানে ব্যবহার করিনি; শুধু কনটেস্ট শেষে upsolving-এ নিয়েছি
• AI-এর বলা complexity সীমা ধরে নিজে গুনে মিলিয়েছি
• greedy বা DP-র প্রমাণ নিজের ভাষায় খাতায় লিখতে পারি
• নমুনা আর অন্তত তিনটি নিজের edge case হাতে trace করেছি (n = 1, সব সমান, সর্বোচ্চ মান)
• brute force-এর সাথে নির্দিষ্ট seed-এ stress test চালিয়েছি, আর একটি ইচ্ছাকৃত ভুল সেটি ধরেছে
• এক দিন পরে AI ছাড়া একই সমস্যা শূন্য থেকে আবার সমাধান করতে পেরেছি

১০ · কোর্স সমাপ্তি — ৭২টি পর্বের পরে আপনি কোথায়

এটি নয়টি মডিউল আর ৭২টি পর্বের এই কোর্সের শেষ পর্ব। একবার পেছনে তাকান। পর্ব ০১-এ প্রশ্ন ছিল, “DSA কেন?” পর্ব ০৩-এ loop invariant দিয়ে প্রমাণ করতে শিখেছিলেন, পর্ব ০৪-এ Big-O দিয়ে বৃদ্ধির হার মাপতে। আজ আপনি একটি অচেনা সমস্যার সীমা পড়ে লক্ষ্য complexity ঠিক করতে পারেন, সঠিক ডেটা স্ট্রাকচার বেছে নিতে পারেন, সমাধানটি প্রমাণ করতে পারেন, আর brute force দিয়ে নিজের কোড যাচাই করতে পারেন। আন্তরিক অভিনন্দন — এটি সত্যিই বড় অর্জন।

এখন আপনি যা পারেন

• বিশ্লেষণের ভিত্তি (পর্ব ১–৯): Big-O, Ω, Θ; best, worst আর average case; loop invariant আর induction দিয়ে প্রমাণ; recursion, recurrence আর master theorem.
• লিনিয়ার স্ট্রাকচার (পর্ব ১০–১৭): array, string, linked list, stack, queue, STL ও Python-এর কালেকশন, two pointer আর prefix sum.
• সার্চিং ও সর্টিং (পর্ব ১৮–২৫): binary search ও উত্তরের ওপর binary search, merge sort, quick sort, heap, linear-time sort আর তুলনা-সর্টের নিম্নসীমা।
• ট্রি, হ্যাশ ও DSU (পর্ব ২৬–৩৩): BST, AVL, red-black, B-tree, trie, hash table আর union-find.
• রেঞ্জ কোয়েরি (পর্ব ৩৪–৩৮): segment tree, lazy propagation, Fenwick tree, sparse table, treap আর skip list.
• গ্রাফ (পর্ব ৩৯–৪৮): BFS, DFS, topological sort, Dijkstra, Bellman-Ford, Floyd-Warshall, MST, SCC, network flow আর LCA.
• ডিজাইন কৌশল (পর্ব ৪৯–৫৯): divide and conquer, greedy ও exchange argument, Huffman, DP-র সব রূপ, backtracking, branch and bound আর string অ্যালগরিদম।
• উন্নত তত্ত্ব (পর্ব ৬০–৬৭): amortized ও randomized বিশ্লেষণ, number theory, geometry, P বনাম NP, NP-hard সমস্যার মোকাবিলা, approximation আর ক্যাপস্টোন।
• প্রস্তুতি (পর্ব ৬৮–৭২): dry-run, MCQ, লিখিত ও ভাইভা, কোডিং ইন্টারভিউ আর এই পর্বের কনটেস্ট।

এরপর কোন পথে