কনটেস্ট প্রোগ্রামিং — সময়ের চাপে সঠিক সমাধান

১ · প্রোগ্রামিং কনটেস্ট আসলে কী

বোর্ড পরীক্ষার হলের কথা মনে করুন। নির্দিষ্ট সময়, কয়েকটি প্রশ্ন, আর খাতা জমা দেওয়ার পর একজন পরীক্ষক নম্বর দেন। প্রোগ্রামিং কনটেস্টও প্রায় তাই — শুধু পরীক্ষক একজন মানুষ নন, একটি প্রোগ্রাম। আর নম্বর আসে কয়েক মাস পরে নয়, কয়েক সেকেন্ডে।

Competitive programming-এ আপনাকে কয়েকটি সমস্যা দেওয়া হয়। প্রতিটির জন্য একটি প্রোগ্রাম লিখে জমা দিতে হয়। প্রোগ্রামটি stdin থেকে ইনপুট পড়বে, উত্তর লিখবে, এবং নির্দিষ্ট সময় ও মেমরির মধ্যে শেষ করবে। প্রতিটি সমস্যার বিবরণে সাধারণত পাঁচটি অংশ থাকে:

জমা দেওয়ার পর জাজ আপনার কোড compile করে, তারপর আগে থেকে তৈরি করা কয়েক ডজন বা কয়েকশো গোপন test case-এ চালায়। প্রতিটির আউটপুট সঠিক উত্তরের সাথে মেলায়। সব মিললে আপনি পান সবুজ সংকেত। একটি না মিললেই লাল।

বাংলাদেশ ও বিশ্বের কনটেস্টের জগৎ

বিশ্ববিদ্যালয়ের ছাত্রছাত্রীদের সবচেয়ে বড় মঞ্চ হলো ICPC. তিনজনের একটি দল, একটি কম্পিউটার, পাঁচ ঘণ্টা আর দশটির মতো সমস্যা — এটাই এর চিরচেনা রূপ। প্রথমে আঞ্চলিক পর্ব (regional), সেখান থেকে বাছাই করা দলগুলো যায় World Finals-এ। ঢাকায় বহু বছর ধরে ICPC-র একটি এশীয় আঞ্চলিক পর্ব আয়োজিত হয়ে আসছে, আর বাংলাদেশের বিশ্ববিদ্যালয়ের দলগুলো প্রায় নিয়মিতভাবেই World Finals-এ অংশ নেয়।

দেশের ভেতরে আছে জাতীয় পর্যায়ের NCPC (National Collegiate Programming Contest) আর বিভিন্ন বিশ্ববিদ্যালয়ের আয়োজনে হয় IUPC (Inter University Programming Contest) নামের আন্তঃবিশ্ববিদ্যালয় কনটেস্ট। স্কুল-কলেজের শিক্ষার্থীদের জন্য আছে ইনফরমেটিক্স অলিম্পিয়াড, যেখান থেকে আন্তর্জাতিক অলিম্পিয়াড IOI-এর দল বাছাই হয়।

২ · Verdict — জাজের ছোট রায়ে বড় তথ্য

জাজ আপনাকে কখনো বলে না ভুলটা কোথায়। সে শুধু একটি ছোট verdict দেয় — দুই-তিন অক্ষরের একটি রায়। ডাক্তারের রিপোর্টের মতো ভাবুন: “জ্বর আছে” শুনে আপনি জানেন না রোগটা কী, কিন্তু কোন দিকে খুঁজতে হবে তা বুঝে যান। প্রতিটি verdict-ও তেমনি খোঁজার দিক দেখিয়ে দেয়।

একটি সূক্ষ্ম কথা খেয়াল করুন। অনেক জাজ verdict-এর সাথে বলে দেয় কোন টেস্টে আটকেছে — যেমন “Wrong answer on test 7”. প্রথম কয়েকটি টেস্ট সাধারণত নমুনা। তাই test 1-এ WA মানে নমুনাতেই ভুল — জমা দেওয়ার আগে নিজে চালিয়ে দেখেননি। আর অনেক পরের টেস্টে WA প্রায়ই বড় সংখ্যার overflow বা কোনো বিরল edge case-এর দিকে ইঙ্গিত করে।

৩ · Constraints পড়ে অ্যালগরিদম বাছাই

কনটেস্টের সবচেয়ে শক্তিশালী কৌশলটি অনেকেই জানেন না: constraints আপনাকে সমাধানের ইঙ্গিত দিয়ে দেয়। সমস্যা-লেখক জানেন কোন গতির সমাধান তিনি চান। সেই অনুযায়ী তিনি n-এর সীমা বেঁধে দেন। আপনি উল্টো দিক থেকে হিসাব করলেই বুঝবেন কোন ধরনের অ্যালগরিদম খুঁজতে হবে।

হিসাবের ভিত্তি একটি মোটা দাগের নিয়ম: সাধারণ একটি জাজ-কম্পিউটার এক সেকেন্ডে মোটামুটি ১০^৮টি সহজ কাজ (যোগ, তুলনা, array থেকে পড়া) করতে পারে। এটি নিখুঁত নয় — কাজের ধরন, cache আর compiler-এর ওপর নির্ভর করে কয়েক গুণ কম-বেশি হয়। কিন্তু অনুমানের জন্য যথেষ্ট। পর্ব ৩৯-এ শেখা time complexity-র এখানেই আসল ব্যবহার।

টেবিলটি মুখস্থ করার জিনিস নয় — নিজেই বের করা যায়। n = ১০^৫ হলে n² = ১০^১০, অর্থাৎ প্রায় ১০০ সেকেন্ড। সময়সীমা ১ সেকেন্ড হলে তা নিশ্চিত TLE. অথচ n log n হলে মাত্র ১৭ লাখের মতো কাজ — চোখের পলকে শেষ। নিচের ডায়াগ্রামে একটি আসল সমস্যায় এই হিসাবটি ধাপে ধাপে দেখুন:

একটি দোকানে n টি জিনিস, প্রতিটির দাম দেওয়া আছে।
q জন ক্রেতা আসবে; প্রত্যেকের কাছে x টাকা।
প্রত্যেকের জন্য বলুন: কয়টি জিনিসের দাম x বা তার কম?

Constraints: 1 <= n, q <= 200000;  1 <= price, x <= 10^9
Time limit: 1 second

for each query x:            /* q বার */
    count = 0
    for each price p:        /* n বার */
        if p <= x: count++

মোট কাজ = n × q = 2e5 × 2e5 = 4e10

4e10 / 1e8  = প্রায় 400 সেকেন্ড   → TLE নিশ্চিত

লক্ষ্য: মোট কাজ 1e7-এর কাছাকাছি বা কম
n log n = 2e5 × 18 ≈ 3.6e6      → আরামে চলবে

১. দামগুলো একবার সাজান      O(n log n)   — পর্ব ৪০
২. প্রতিটি x-এর জন্য binary search:
   x-এর চেয়ে বড় প্রথম দাম কোথায়?   O(log n) — পর্ব ৪১
   সেই অবস্থানই হলো উত্তর

মোট = (n + q) × log n ≈ 7e6

দাম ও x <= 1e9      → int-এ ধরে (int-এর সীমা প্রায় 2.1e9)
উত্তর <= n = 2e5    → int যথেষ্ট
ইনপুট ≈ 4e5 সংখ্যা  → scanf যথেষ্ট দ্রুত
array: 2e5 × 4 byte = 0.8 MB → global রাখুন

পরিকল্পনা তৈরি — এবার কোড লেখার পালা

৪ · সমস্যার ভেতরের চেনা ছাঁচ

অভিজ্ঞরা প্রতিটি সমস্যা শূন্য থেকে ভাবেন না; খোঁজেন — “এই সমস্যাটি আমার চেনা কোন সমস্যার ছদ্মবেশ?” পর্ব ০২-এ শেখা pattern recognition-এর এটাই সবচেয়ে কাজের রূপ। দাবা খেলোয়াড় যেমন হাজারো অবস্থান দেখে এক নজরে চাল বোঝেন, প্রোগ্রামারও শত শত সমস্যা সমাধান করে ছাঁচ চিনতে শেখেন।

গত কয়েকটি পর্বে আপনি যে কৌশলগুলো শিখেছেন, সেগুলোকে চেনার কিছু সংকেত নিচে দেওয়া হলো:

৫ · যে ফাঁদে সবাই অন্তত একবার পড়ে

কনটেস্টে বেশিরভাগ WA আসে কঠিন অ্যালগরিদমের ভুল থেকে নয় — আসে ছোট, প্রায় হাস্যকর ভুল থেকে। ভালো খবর হলো, এই তালিকা ছোট।

এবার সবচেয়ে চতুর ফাঁদটি ধাপে ধাপে দেখুন। প্রোগ্রামটি প্রতিটি test case-এর সংখ্যাগুলোর যোগফল ছাপে। ইনপুটে দুটি test case থাকবে: প্রথমটিতে 1 2 3, যার উত্তর 6, আর দ্বিতীয়টিতে 10 20, যার উত্তর হওয়া উচিত ৩০। প্রথম test case ঠিকঠাক চলবে — দেখুন দ্বিতীয়টিতে কী হয়।

1#include <stdio.h>2long long sum = 0;   /* outside the loop! */3int main(void) {4    int t, n, x;5    scanf("%d", &t);6    while (t--) {7        scanf("%d", &n);8        for (int i = 0; i < n; i++) {9            scanf("%d", &x); sum += x;10        }11        printf("%lld\n", sum);12    }13}

এই শিক্ষাগুলো একসাথে করে একটি নির্ভরযোগ্য কাঠামো বানানো যায়, যা প্রায় প্রতিটি multi-test সমস্যায় কাজে লাগে। নিচের প্রোগ্রামটি প্রথমে T পড়ে, তারপর প্রতিটি test case-এ n টি সংখ্যা পড়ে যোগফল ও সর্বোচ্চ মান ছাপে। ইনপুটে ইচ্ছা করে তিনটি ১০^৯ রাখা হয়েছে, যাদের যোগফল int-এ ধরত না:

#include <stdio.h>

int main(void) {
    int t, n;
    long long x;
    if (scanf("%d", &t) != 1) return 1;
    for (int tc = 1; tc <= t; tc++) {
        if (scanf("%d", &n) != 1) return 1;
        long long sum = 0, mx = 0;          /* reset for EVERY test case */
        for (int i = 0; i < n; i++) {
            if (scanf("%lld", &x) != 1) return 1;
            sum += x;
            if (i == 0 || x > mx) mx = x;   /* first value starts the max */
        }
        printf("Case %d: sum=%lld max=%lld\n", tc, sum, mx);
    }
    return 0;
}

৬ · Fast I/O — যখন ইনপুট পড়াই ধীর

কখনো কখনো অ্যালগরিদম ঠিক থাকলেও TLE আসে, কারণ ইনপুট পড়তেই সময় শেষ। প্রতিটি সংখ্যা পড়তে scanf format string বিশ্লেষণ করে, তারপর অক্ষর থেকে সংখ্যা বানায় — এক-একবারে খরচ সামান্য, কিন্তু ১০ লাখ বারে টের পাওয়া যায়।

প্রথম কথা: বেশিরভাগ সমস্যায় scanf আর printf যথেষ্ট দ্রুত। সমস্যা হয় শুধু ইনপুট সত্যিই বিশাল হলে, অথবা নিজের অজান্তে আউটপুট ধীর করে ফেললে। তখনই কাজে আসে fast I/O কৌশল।

static long long read_ll(void) {
    int c = getchar(), neg = 0;
    long long x = 0;
    while (c != EOF && c != '-' && (c < '0' || c > '9')) c = getchar();
    if (c == '-') { neg = 1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); }
    return neg ? -x : x;
}

৭ · Stress testing — চোখে না খুঁজে যন্ত্র দিয়ে ভুল খোঁজা

WA পেলেন, নমুনা মিলছে, কোড দশবার পড়লেন — ভুল চোখে পড়ছে না। এখানে অভিজ্ঞরা যে কৌশল ব্যবহার করেন, তার নাম stress testing.

ভাবনাটি সহজ। তিনটি জিনিস লাগে:

• একটি brute force সমাধান — ধীর, কিন্তু এত সরল যে ভুল হওয়ার সুযোগ প্রায় নেই। যেমন সব জোড়া পরীক্ষা করা।
• আপনার দ্রুত সমাধান — যেটি জমা দিয়েছিলেন এবং যেটিতে কোথাও ভুল লুকিয়ে আছে।
• একটি এলোমেলো ইনপুট তৈরির প্রোগ্রাম — ছোট ছোট, নানা রকম ইনপুট বানায়।

তারপর একটি লুপ: ইনপুট বানানো, দুই সমাধানে চালানো, উত্তর মেলানো — হাজার বার। উত্তর না মিললেই থেমে সেই ছোট ইনপুটটি দেখানো। তার debugging অনেক সহজ।

একটি বাস্তব ধাঁচের গল্প দিয়ে পুরো যাত্রাটি দেখুন। সমস্যা: n টি সংখ্যা (প্রতিটি ১০^৯ পর্যন্ত) আর q টি প্রশ্ন; প্রতিটি প্রশ্নে l থেকে r পর্যন্ত সংখ্যাগুলোর যোগফল বলতে হবে।

Test 1 ... passed
Test 2 ... passed
...
Wrong answer on test 9

int pre[200001];          /* pre[i] = a[1] + ... + a[i] */
...
pre[i] = pre[i - 1] + a[i];
...
printf("%d\n", pre[r] - pre[l - 1]);

যুক্তি ঠিক আছে, নমুনাও মিলছে…

for each query (l, r):
    long long s = 0;
    for (i = l; i <= r; i++) s += a[i];
    printf("%lld\n", s);

O(n × q) — জমা দিলে TLE, কিন্তু উত্তর নিশ্চিত সঠিক

test 1 ... same
test 2 ... same
...
test 1000 ... same
সব মিলছে! তাহলে ভুলটা ছোট সংখ্যায় নেই।
→ constraints আবার পড়ি: মান 10^9 পর্যন্ত…

Mismatch on test 3
input:  n=3  a = 1000000000 1000000000 1000000000
        query: l=1 r=3
brute:  3000000000
fast:   -1294967296

long long pre[200001];
...
printf("%lld\n", pre[r] - pre[l - 1]);

Accepted

এবার সেই লুপটির ভেতরটা দেখুন। কনটেস্টে সাধারণত তিনটি আলাদা প্রোগ্রাম (gen, brute, fast) বানিয়ে একটি ছোট shell script দিয়ে চালানো হয়। প্রতিটি ধাপে কোন লাইন চলছে আর ফাইলগুলোতে কী আছে, খেয়াল করুন:

1for i in $(seq 1 1000); do2  ./gen $i > in.txt3  ./brute < in.txt > b.txt4  ./fast  < in.txt > f.txt5  if ! cmp -s b.txt f.txt; then6    echo "Mismatch on $i"; cat in.txt; break7  fi8done

shell script ছাড়াও পুরো ব্যাপারটি একটি প্রোগ্রামের ভেতরেই করা যায়। নিচের প্রোগ্রামে brute, fast আর এলোমেলো ইনপুট — তিনটিই একসাথে। Fast ফাংশনে উপরের ভুলটিই রাখা আছে। চালিয়ে দেখুন stress test কত দ্রুত সেটি ধরে:

#include <stdio.h>
#include <stdlib.h>
int brute(const int *a, int n) {              /* every pair: O(n^2), surely right */
    int best = 0;
    for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++)
        if (a[i] * a[j] > best) best = a[i] * a[j];
    return best;
}
int fast(const int *a, int n) {               /* two largest: O(n), has a bug */
    int i1 = 0, i2 = 0;
    for (int i = 1; i < n; i++) if (a[i] > a[i1]) i1 = i;
    for (int i = 0; i < n; i++) if (i != i1 && a[i] > a[i2]) i2 = i;
    return a[i1] * a[i2];
}
int main(void) {
    int a[3], t;
    srand(42);                                /* fixed seed: same tests every run */
    for (t = 1; t <= 1000; t++) {
        for (int i = 0; i < 3; i++) a[i] = rand() % 10;
        if (brute(a, 3) != fast(a, 3)) break;
    }
    if (t > 1000) printf("All 1000 tests passed\n");
    else printf("Test %d FAILED: a = %d %d %d, brute=%d fast=%d\n", t, a[0], a[1], a[2], brute(a, 3), fast(a, 3));
    return 0;
}

৮ · উন্নতির পদ্ধতি — অনুশীলন, upsolving আর দলগত খেলা

কনটেস্টে ভালো করার কোনো গোপন রহস্য নেই — আছে একটি অনুশীলনের পদ্ধতি। একজন ব্যাটসম্যান শুধু ম্যাচ খেলে উন্নতি করেন না; কোন বলে আউট হয়েছিলেন, তা নিয়ে নেটে আলাদা করে কাজ করেন। প্রোগ্রামিংয়েও তাই।

ICPC — তিনজন, একটি কম্পিউটার

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

৯ · AI-এর যুগে কনটেস্ট — নিয়ম, সততা আর শেখার সঙ্গী

এখনকার AI মডেলগুলো অনেক কনটেস্ট-সমস্যা সমাধান করতে পারে। তবু মনে রাখুন, কনটেস্ট হলো আপনার চিন্তার মাপকাঠি। ক্রিকেটে বোলিং মেশিন মানুষের চেয়ে নিখুঁত বল করে, তবু কেউ বোলিং মেশিন দিয়ে বিশ্বকাপ খেলায় না।

তবে কনটেস্টের পরে AI একজন অসাধারণ শিক্ষক। নিজে সৎভাবে চেষ্টা করে editorial পড়েছেন, কিন্তু একটি ধাপ বুঝছেন না — তখন AI-কে প্রশ্ন করুন। শর্ত একটাই: উত্তর নয়, বোঝাপড়া চান।

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

AI প্রায়ই নমুনায় ঠিক উত্তর দেয়, কিন্তু সীমার কাছে ভুল করে। অনুশীলনে বা চাকরিতে AI-এর লেখা অ্যালগরিদম যাচাইয়ে কনটেস্টের এই অভ্যাসগুলোই কাজে লাগে।

• Constraints-এর সর্বোচ্চ n-এ এর গতি কত, নিজে হিসাব করেছি — শুধু AI-এর দাবি মেনে নিইনি
• সব গুণফল ও যোগফল long long-এ ধরে কি না দেখেছি, আর %lld ঠিক জায়গায় আছে
• Multi-test হলে প্রতিটি test case-এর শুরুতে সব অবস্থা reset হচ্ছে
• একটি brute force লিখে এলোমেলো ছোট ও বড় ইনপুটে stress test চালিয়েছি
• সমাধানের প্রতিটি ধাপ কেন কাজ করে, নিজের ভাষায় বলতে পারি

১০ · মডিউল ৬-এর সমাপ্তি — আপনার অ্যালগরিদমের টুলবক্স

এই পর্ব দিয়ে মডিউল ৬ শেষ হলো। ছয়টি পর্বে আপনি এমন একটি টুলবক্স হাতে পেয়েছেন, যা কনটেস্টে, চাকরির ইন্টারভিউতে আর বাস্তব সফটওয়্যারে — তিন জায়গাতেই কাজে লাগে। একবার পেছনে তাকিয়ে দেখি: