অ্যালগরিদম ও কনটেস্টে Java — সেকেন্ড না বছর, সিদ্ধান্ত পদ্ধতিতে

১ · অ্যালগরিদম মানে রেসিপি — একই সমস্যা, সেকেন্ড না বছর

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

একটি বাস্তব প্রশ্ন ভাবুন। একটি অনলাইন দোকানের এক বছরের প্রতিদিনের বিক্রির হিসাব আছে, আর ম্যানেজার দিনভর জিজ্ঞেস করছেন: “১২ থেকে ৪৫ নম্বর দিনে মোট বিক্রি কত?”, “২০০ থেকে ৩০০?” — এমন দুই লাখ প্রশ্ন। প্রথম পদ্ধতি: প্রতিটি প্রশ্নে সেই দিনগুলো লুপ চালিয়ে যোগ করা। দ্বিতীয় পদ্ধতি: একবার একটি চলমান যোগফলের তালিকা বানিয়ে প্রতিটি প্রশ্নের উত্তর একটি বিয়োগে দেওয়া (অংশ ৩-এ দেখবেন)। দিন দুই লাখ আর প্রশ্নও দুই লাখ হলে প্রথম পদ্ধতিতে প্রায় ৪ × ১০^১০ যোগ — কয়েক মিনিট; দ্বিতীয়টিতে কয়েক লাখ — চোখের পলক। ভাষা, কম্পিউটার, প্রোগ্রামার একই; পার্থক্য শুধু পদ্ধতিতে।

Big-O — কাজ কীভাবে বাড়ে

পর্ব ৩০–৩২-এ Big-O চিহ্নগুলো দেখেছেন। মূল কথা আবার মনে করি: Big-O সেকেন্ড মাপে না, মাপে ইনপুটের আকার n বাড়লে কাজের পরিমাণ কোন হারে বাড়ে। ধ্রুবক গুণক আর ছোট পদ বাদ দেওয়া হয়, কারণ n বড় হলে বৃদ্ধির ধরনটাই সব ঠিক করে দেয়। একে বলে time complexity. n = ১০^৫ হলে ছবিটা এমন:

কনটেস্ট আর ইন্টারভিউতে সবচেয়ে কাজের আন্দাজ: সাধারণ একটি কম্পিউটার এক সেকেন্ডে মোটামুটি ১০^৮-এর কাছাকাছি সরল কাজ করে (যোগ, তুলনা, array-এর ঘর পড়া)। এটা মোটা দাগের হিসাব — CPU, cache, ভাষা আর কাজের ধরন অনুযায়ী কয়েক গুণ এদিক-ওদিক হয়। Java-তে JVM চালু হওয়ার একটি স্থির সময়ও যোগ হয়। তবু এই আন্দাজ দিয়েই কোড লেখার আগে বলা যায় একটি পদ্ধতি চলবে কি না।

constraints পড়ে পদ্ধতি বেছে নেওয়া

প্রতিটি কনটেস্ট-সমস্যার নিচে ইনপুটের সীমা (constraints) লেখা থাকে — যেমন “1 ≤ n ≤ 2·10⁵”. অভিজ্ঞ প্রতিযোগীরা এটা আগে পড়েন, কারণ সীমাই প্রায় বলে দেয় কোন পদ্ধতি লাগবে:

এই কৌশলের পুরো নাম competitive programming: নির্দিষ্ট সময় আর মেমরির সীমায় স্পষ্টভাবে বলা সমস্যার সমাধান জমা দেওয়া, আর একটি online judge গোপন টেস্টে সেটা চালিয়ে রায় দেয়। কোডিং ইন্টারভিউও এই দক্ষতাই পরীক্ষা করে। Java কনটেস্টের পুরোপুরি স্বীকৃত ভাষা; শুধু কয়েকটি পারফরম্যান্স-অভ্যাস শিখে নিতে হয়।

২ · কনটেস্টে Java — দ্রুত ইনপুট-আউটপুট আর একটি টেমপ্লেট

পর্ব ০৯-এ Scanner দিয়ে ইনপুট পড়েছেন — শেখার জন্য চমৎকার। কিন্তু দশ লাখ সংখ্যা পড়তে হলে সেটা ধীর, কারণ Scanner প্রতিটি token চিনতে regular expression ব্যবহার করে আর অনেক যাচাই করে। অনেক সময় সঠিক অ্যালগরিদমও শুধু ইনপুট পড়তে গিয়েই সময়সীমা পেরিয়ে যায় — রায় আসে TLE.

• ইনপুট: BufferedReader পুরো লাইন একবারে পড়ে (readLine()), আর StringTokenizer লাইনটিকে ফাঁকা জায়গায় ভেঙে token দেয়; তারপর Integer.parseInt. StringTokenizer পুরোনো (legacy) class — Java-র documentation সাধারণ কোডে split ব্যবহার করতে বলে — কিন্তু এটা হালকা আর দ্রুত বলে কনটেস্টে খুব প্রচলিত। আরও দ্রুত চাইলে অনেকে DataInputStream থেকে বাইট পড়ে নিজেই সংখ্যা বানানোর একটি ছোট reader লেখেন।
• আউটপুট: লাখ লাইন ছাপতে প্রতিবার System.out.println ডাকা ধীর, কারণ System.out সাধারণত প্রতিটি লাইনের পর flush করে — প্রতিবার অপারেটিং সিস্টেমের কাছে ছোট একটি লেখা পাঠায়। তার বদলে StringBuilder-এ সব জমান, অথবা PrintWriter (ভেতরে BufferedWriter) ব্যবহার করুন, আর শেষে একবার flush. flush ভুলে গেলে কিছুই ছাপা না হতে পারে — কনটেস্টে খুব পরিচিত “আমার আউটপুট কই গেল” মুহূর্ত।

এই দুটি মিলিয়ে একটি টেমপ্লেট, যা অনেক Java প্রতিযোগী প্রতিটি সমস্যার শুরুতে বসান:

import java.io.*;
import java.util.*;

public class Main {                    // judge-এ public চলে; আমাদের runner-এ public বাদ
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
    static int nextInt() throws IOException { return Integer.parseInt(next()); }
    static long nextLong() throws IOException { return Long.parseLong(next()); }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        int t = nextInt();                 // কতগুলো test case
        while (t-- > 0) solve(out);
        out.flush();                       // শেষে একবার
    }
    static void solve(PrintWriter out) throws IOException {
        // এখানে আসল সমাধান
    }
}

next()-এর while লুপটি খেয়াল করুন: বর্তমান লাইনের token শেষ হলে পরের লাইন পড়ে। তাই সংখ্যাগুলো এক লাইনে থাকুক বা আলাদা লাইনে — কিছু যায় আসে না। Codeforces, AtCoder-এর মতো judge-এ সাধারণত public class Main লেখা হয় (অনেক judge-এ class-এর নাম Main হওয়া বাধ্যতামূলক; প্রতিটি প্ল্যাটফর্মের নির্দেশনা দেখে নিন)। এই কোর্সের ব্রাউজার-runner ফাইলের নাম আলাদা রাখে বলে এখানে চালানো কোডে class Main লেখা হয় public ছাড়া — পর্ব ০৪-এ যেমন বলা হয়েছিল।

Java-র চেনা কনটেস্ট-ফাঁদ

সঠিক অ্যালগরিদম লিখেও Java-তে কয়েকটি জায়গায় উত্তর ভুল (WA) বা সময় পার (TLE) হয়। এগুলো আগে থেকে চিনে রাখুন:

1. int overflow. int-এর সীমা প্রায় ২.১ × ১০^৯. int a = 100000, b = 100000; হলে a * b ছাপে 1410065408 — দশ বিলিয়ন নয়। long c = a * b; লিখলেও একই ফল, কারণ গুণটা আগে int-এ হয়। ঠিক উপায় (long) a * b → 10000000000 (তিনটিই চালিয়ে যাচাই করা)। যোগফল, গুণফল আর দূরত্বে শুরু থেকেই long নিন। পর্ব ০৬ আর ০৭-এ এর বিস্তারিত।
2. Integer-এ ==. List<Integer>-এর দুটি উপাদান == দিয়ে তুলনা করলে মান নয়, object-এর ঠিকানা তুলনা হয় (reference equality). ১২৭-এর মতো ছোট সংখ্যায় Java-র Integer cache-এর কারণে true আসে, কিন্তু ১০০০ আর ১০০০-এ false (যাচাই করা)। equals ব্যবহার করুন, বা int-এ নামিয়ে তুলনা করুন। পর্ব ০৬ দেখুন।
3. গভীর recursion-এ StackOverflowError. প্রতিটি method-ডাক call stack-এ একটি ফ্রেম নেয় (পর্ব ১২)। একটি শিকলের মতো গ্রাফে দশ লাখ গভীর DFS বা দশ লাখ ধাপের recursion সাধারণ thread-এর stack ভরিয়ে ফেলে।
4. Arrays.sort(int[])-এর worst case. primitive array-এ Java Dual-Pivot Quicksort ব্যবহার করে (পর্ব ৩৩)। পুরোনো JDK-তে (যেমন বহু বছর judge-এ থাকা Java 8) ইচ্ছে করে বানানো adversarial input-এ এটা O(n^২)-এর দিকে যেতে পারত, আর Codeforces-এর মতো প্ল্যাটফর্মে অন্যের সমাধান “hack” করতে এমন anti-quicksort টেস্ট ব্যবহার হতো। JDK 14-এ বাস্তবায়নটি নতুন করে লেখা হয়, আর সাধারণভাবে বলা হয় যে তাতে recursion অস্বাভাবিক গভীর হলে heap sort-এ সরে যাওয়ার ব্যবস্থা যোগ হয়েছে — ফলে ঝুঁকি অনেক কমেছে। তবু judge কোন JDK চালায় জানা না থাকলে নিরাপদ অভ্যাস: sort-এর আগে array এলোমেলো (shuffle) করা, অথবা Integer[] বা ArrayList sort করা — object-এর sort হলো TimSort, যার worst case নিশ্চিতভাবে O(n log n), যদিও boxing-এর খরচ আছে।
5. HashMap আর anti-hash টেস্ট. অনেক key একই bucket-এ ফেলার মতো করে বানানো টেস্টে HashMap ধীর হয়ে যায় (hash flooding). Java 8 থেকে বড় bucket একটি গাছে রূপান্তরিত হয়, তাই ক্ষতি সীমিত, কিন্তু ধীরগতি থেকেই যায়। মানের পরিসর ছোট হলে int[] দিয়ে গণনা প্রায়ই দ্রুততর।
6. Boxing-এর খরচ. ArrayList<Integer>, HashMap<Integer, Integer>-এর প্রতিটি সংখ্যা একটি আলাদা object — মেমরি বেশি, cache-এ ছড়ানো, garbage collector-এর কাজ বাড়ে। দশ লাখ সংখ্যার জন্য সম্ভব হলে int[] আর long[].

সমাধান দুটি। প্রথমটি পরিষ্কার: recursion-কে একটি নিজের ArrayDeque stack দিয়ে iterative করুন (অংশ ৭-এর DFS). দ্বিতীয়টি কনটেস্টের পরিচিত কৌশল: বড় stack দিয়ে একটি নতুন thread চালানো। Thread-এর constructor-এ চতুর্থ argument হলো চাওয়া stack-এর আকার (বাইটে), যা JVM একটি ইঙ্গিত হিসেবে নেয়:

class Main {
    static long sum(int n) { return n == 0 ? 0 : n + sum(n - 1); }
    public static void main(String[] args) throws InterruptedException {
        Thread t = new Thread(null, () -> System.out.println(sum(1_000_000)), "solver", 1L << 28);
        t.start();                          // ২৫৬ MB stack চেয়ে নতুন thread
        t.join();                           // ছাপে 500000500000
        System.out.println(sum(1_000_000)); // main thread-এ: StackOverflowError
    }
}

500000500000
Exception in thread "main" java.lang.StackOverflowError
	at Main.sum(Main.java:2)
	at Main.sum(Main.java:2)
	... (একই লাইন হাজার হাজার বার)

একই method, একই দশ লাখ গভীরতা: বড় stack-এর thread-এ উত্তর এল, সাধারণ main thread-এ StackOverflowError (Wandbox-এর OpenJDK 21-এ চালিয়ে যাচাই করা; সেখানে ফাইলের নাম আলাদা দেখায়, আর stack-এর আকার যন্ত্রভেদে আলাদা হতে পারে)। তবে মনে রাখবেন, stack-এর আকার JVM-এর কাছে অনুরোধ মাত্র, আর judge-এর মেমরি-সীমাও আছে — iterative সমাধানই বেশি নির্ভরযোগ্য।

৩ · ছাঁচ ১ — prefix sum আর two pointers

Prefix sum — রেঞ্জের যোগফল এক বিয়োগে

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

1long[] pre = new long[n + 1];  // pre[0] = 02for (int i = 1; i <= n; i++)3    pre[i] = pre[i - 1] + a[i];4// প্রশ্ন: দিন l থেকে r5sum = pre[r] - pre[l - 1];

এবার অংশ ২-এর টেমপ্লেটে বসিয়ে চালিয়ে দেখুন। ইনপুটের প্রথম লাইনে দিনের সংখ্যা আর প্রশ্নের সংখ্যা, তারপর বিক্রি, তারপর প্রতিটি প্রশ্নের l আর r:

import java.io.*;
import java.util.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
    static int nextInt() throws IOException { return Integer.parseInt(next()); }

    public static void main(String[] args) throws IOException {
        int n = nextInt(), q = nextInt();
        long[] pre = new long[n + 1];                 // pre[i] = প্রথম i দিনের মোট
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + nextInt();
        StringBuilder out = new StringBuilder();
        while (q-- > 0) {
            int l = nextInt(), r = nextInt();
            out.append(pre[r] - pre[l - 1]).append('\n');   // প্রতিটি প্রশ্ন O(1)
        }
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        pw.print(out);
        pw.flush();                                   // শেষে একবার
    }
}

Two pointers আর sliding window

আরেকটি প্রশ্ন: “সবচেয়ে বেশি কত দিন পরপর এমন আছে, যেখানে মোট বিক্রি ১৫ হাজারের বেশি নয়?” প্রতিটি শুরু আর প্রতিটি শেষ জোড়া দেখলে O(n^২). Two pointers কৌশলে দুটি index — l আর r — একটি “জানালা” ধরে রাখে। r ডানে এগিয়ে নতুন দিন যোগ করে; যোগফল সীমা ছাড়ালে l ডানে সরে পুরোনো দিন বাদ দেয়। দুটি pointer-ই শুধু সামনে যায়, প্রত্যেকে সর্বোচ্চ n ধাপ — মোট O(n). চলমান এই জানালার নাম sliding window.

int best = 0, l = 0; long sum = 0;
for (int r = 0; r < a.length; r++) {
    sum += a[r];                          // ডানে নতুন দিন
    while (sum > limit) sum -= a[l++];    // সীমা ছাড়ালে বাঁ থেকে বাদ
    best = Math.max(best, r - l + 1);
}

a = {5, 3, 8, 2, 7, 4}, limit = 15 হলে best হয় 3 (যেমন ৩ + ৮ + ২ = ১৩), চালিয়ে যাচাই করা। এই কৌশল কাজ করে কারণ সব মান ধনাত্মক: জানালা বড় করলে যোগফল শুধু বাড়ে, ছোট করলে শুধু কমে। ঋণাত্মক মান থাকলে এই একমুখী যুক্তি ভেঙে যায়। আরেকটি রূপ: সাজানো দামের তালিকায় এমন দুটি জিনিস খোঁজা যাদের দাম মিলে ঠিক বাজেট — এক pointer শুরুতে, আরেকটি শেষে; যোগফল কম হলে বাঁ pointer ডানে, বেশি হলে ডান pointer বাঁয়ে। প্রতি ধাপে একটি সম্ভাবনা বাদ যায়, তাই O(n). স্থির আকারের জানালার সর্বোচ্চ মান খোঁজার Deque-কৌশল পর্ব ৩২-এ দেখেছেন।

৪ · ছাঁচ ২ — উত্তরের ওপর binary search আর greedy

উত্তরের ওপর binary search

পর্ব ১৩-এ binary search দেখেছেন: সাজানো array-এ একটি মান খুঁজতে প্রতিবার অর্ধেক বাদ। এর একটি শক্তিশালী রূপ আছে, যেখানে আমরা array-তে নয়, সম্ভাব্য উত্তরের পরিসরে খুঁজি — binary search on the answer.

একটি বাস্তব সমস্যা: একটি গুদাম থেকে ৭টি চালান ক্রম মেনে পাঠাতে হবে, ওজন (টনে) ৪, ৮, ৩, ৬, ৫, ৭, ২. প্রতিদিন একটি ট্রাক একবার যায়; ক্রম ভাঙা যাবে না। ৩ দিনে সব পাঠাতে ট্রাকের ক্ষমতা সবচেয়ে কম কত হলে চলে? সরাসরি “সেরা উত্তর” বের করা কঠিন। কিন্তু উল্টো প্রশ্নটা সহজ: “ক্ষমতা X হলে ৩ দিনে হবে কি?” — চালানগুলো ক্রমে ট্রাকে তুলুন, না ধরলে পরের দিন নতুন ট্রাক; দিন গুনুন। এটা O(n).

মূল পর্যবেক্ষণ হলো একঘেয়েমি (monotonicity): ক্ষমতা ১৪-তে হলে ১৫, ১৬-তেও হবে; ১৩-তে না হলে ১২-তেও হবে না। তাই সম্ভাব্য উত্তরের সারি দেখতে এমন — ✘ ✘ ✘ … ✘ ✔ ✔ ✔ … — আর আমাদের খুঁজতে হবে প্রথম ✔. সবচেয়ে ভারী চালান (৮) ধরতে হবেই, তাই নিচের সীমা ৮; সব একদিনে নিলে মোট ৩৫, তাই ওপরের সীমা ৩৫.

1lo = max(w) = 8;  hi = sum(w) = 35;2while (lo < hi) {3    mid = lo + (hi - lo) / 2;4    if (canShip(mid)) hi = mid;5    else lo = mid + 1;6}   // উত্তর = lo

import java.util.StringTokenizer;

class Main {
    static int[] w;
    static boolean canShip(long cap, int days) {      // এই ক্ষমতায় days দিনে হবে?
        int used = 1; long load = 0;
        for (int x : w) {
            if (load + x > cap) { used++; load = 0; }  // আজ আর ধরবে না, কাল নতুন ট্রাক
            load += x; }
        return used <= days;
    }
    public static void main(String[] args) throws Exception {
        StringTokenizer in = new StringTokenizer(new String(System.in.readAllBytes()));
        int n = Integer.parseInt(in.nextToken()), days = Integer.parseInt(in.nextToken());
        w = new int[n];
        long lo = 0, hi = 0;
        for (int i = 0; i < n; i++) {
            w[i] = Integer.parseInt(in.nextToken());
            lo = Math.max(lo, w[i]); hi += w[i];       // উত্তর এই দুইয়ের মাঝে
        }
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            boolean ok = canShip(mid, days);  System.out.println("check(" + mid + ") = " + ok);
            if (ok) hi = mid; else lo = mid + 1;
        }
        System.out.println("সর্বনিম্ন ক্ষমতা: " + lo + " টন");
    }
}

Greedy — প্রতি ধাপে এখনকার সেরা

Greedy পদ্ধতি প্রতিটি ধাপে সেই মুহূর্তের সবচেয়ে ভালো দেখানো সিদ্ধান্ত নেয়, আর কখনো ফিরে তাকায় না। দোকানদার ১৮৮৮ টাকা ফেরত দিতে চান, সবচেয়ে কম নোট-কয়েনে। সরলতার জন্য ধরুন নোট-কয়েন ১, ২, ৫, ১০, ২০, ৫০, ১০০, ৫০০, ১০০০ টাকা (বাংলাদেশের বেশি প্রচলিতগুলো; ২০০ টাকার নোট এখানে বাদ রাখা হয়েছে)। স্বাভাবিক কৌশল: যত বড় নোট দেওয়া যায় দিন, তারপর বাকিটার জন্য আবার একই কাজ।

int[] notes = {1000, 500, 100, 50, 20, 10, 5, 2, 1};
int amount = 1888, count = 0;
for (int nt : notes) {
    count += amount / nt;        // এই নোট কয়টি দেওয়া যায়
    amount %= nt;                // বাকি টাকা
}
// count = 11: 1000x1 500x1 100x3 50x1 20x1 10x1 5x1 2x1 1x1

ফল ১১টি নোট (যাচাই করা)। এই নোট-ব্যবস্থায় greedy সবসময় সেরা উত্তর দেয় — এমন ব্যবস্থাকে বলে “canonical”, আর বেশিরভাগ দেশের মুদ্রা এভাবেই নকশা করা। কিন্তু সাবধান: greedy সব জায়গায় ঠিক নয়। ধরুন কোনো দেশে কয়েন ১, ৩ আর ৪. ৬ টাকা দিতে greedy নেবে ৪ + ১ + ১ = ৩টি কয়েন, অথচ ৩ + ৩ = ২টিই যথেষ্ট (যাচাই করা)। প্রথম ধাপের “সেরা” সিদ্ধান্ত পরে ক্ষতি করল। তাই greedy লেখার আগে একটি ছোট প্রমাণ বা অন্তত একটি পাল্টা-উদাহরণ খোঁজা জরুরি।

একটি ক্লাসিক জায়গা যেখানে greedy প্রমাণসহ সঠিক: activity selection — একটি অডিটোরিয়ামে না মিলিয়ে সবচেয়ে বেশি অনুষ্ঠান রাখতে অনুষ্ঠানগুলো শেষ হওয়ার সময় অনুযায়ী sort করে যেটা আগে শেষ হয় সেটা নিন, কারণ সে বাকিদের জন্য সবচেয়ে বেশি সময় ছেড়ে দেয়। অনেক greedy সমস্যার আসল কাজ হলো “কোন ক্রমে sort করব”.

৫ · ছাঁচ ৩ — hashing, recursion আর backtracking

Hashing দিয়ে গণনা

“কোন শহর থেকে কতগুলো অর্ডার এসেছে?”, “কোন সংখ্যা সবচেয়ে বেশিবার আছে?”, “আগে দেখেছি কি?” — এমন প্রশ্নে HashMap গড়ে O(1)-এ কাজ করে (পর্ব ৩১)। গণনার সবচেয়ে পরিষ্কার লেখা merge:

Map<String, Integer> freq = new TreeMap<>();       // ছাপার ক্রম নির্দিষ্ট রাখতে TreeMap
for (String city : "dhaka khulna dhaka sylhet dhaka khulna".split(" "))
    freq.merge(city, 1, Integer::sum);                // না থাকলে 1, থাকলে +1
System.out.println(freq);                             // {dhaka=3, khulna=2, sylhet=1}

গতি দরকার হলে HashMap নিন (গড়ে O(1)), নির্দিষ্ট ক্রম দরকার হলে TreeMap (O(log n), সাজানো)। আর key যদি ০ থেকে ১০^৬-এর মতো ছোট পরিসরের পূর্ণসংখ্যা হয়, একটি int[] count HashMap-এর চেয়ে অনেক দ্রুত — boxing নেই, hashing নেই।

Recursion থেকে backtracking

পর্ব ১২-এ recursion দেখেছেন: একটি method সমস্যাকে ছোট করে নিজেকে ডাকে, আর base case-এ থামে। Backtracking হলো recursion দিয়ে সব সম্ভাবনা গুছিয়ে খোঁজা: একটি সিদ্ধান্ত নাও, বাকিটা recursion-কে দাও, ফিরে এসে সিদ্ধান্তটি উল্টে দাও, তারপর পরের বিকল্প। গোলকধাঁধায় হাঁটার মতো — কানাগলিতে পৌঁছালে শেষ মোড়ে ফিরে অন্য পথ। একটি তালিকার সব subset বানানো এর সবচেয়ে সরল রূপ: প্রতিটি উপাদানে দুটি পথ — “নেব না” বা “নেব”.

static void subsets(int[] a, int i, Deque<Integer> cur, List<List<Integer>> all) {
    if (i == a.length) { all.add(new ArrayList<>(cur)); return; }   // base case: একটি subset তৈরি
    subsets(a, i + 1, cur, all);                 // a[i] নেব না
    cur.addLast(a[i]);                           // সিদ্ধান্ত: নেব
    subsets(a, i + 1, cur, all);
    cur.removeLast();                            // ফিরে এসে সিদ্ধান্ত উল্টানো
}
// {1, 2, 3} → [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

n টি উপাদানে 2ⁿটি subset — তাই অংশ ১-এর টেবিল অনুযায়ী এটা শুধু n ২০-এর আশেপাশে পর্যন্ত চলে। new ArrayList<>(cur) লক্ষ করুন: cur নিজেকে যোগ করলে সব জায়গায় একই object যেত, আর শেষে সব খালি দেখাত — backtracking-এর খুব পরিচিত bug. N-Queens, Sudoku সমাধান, সব বিন্যাস (permutation) — সবই এই ছাঁচ, শুধু “এই সিদ্ধান্ত বৈধ কি না” যাচাই যোগ হয়, যাতে অবৈধ পথ শুরুতেই কেটে দেওয়া যায় (pruning).

৬ · ছাঁচ ৪ — dynamic programming: একবার হিসাব, বারবার ব্যবহার

Fibonacci সংখ্যা ভাবুন: fib(n) = fib(n-1) + fib(n-2). সরাসরি recursion লিখলে fib(50) হিসাব করতে fib(48) দুইবার, fib(47) তিনবার, fib(46) পাঁচবার… হিসাব হয় — ডাকের সংখ্যা বাড়ে প্রায় সূচকীয় হারে, আর সাধারণ কম্পিউটারে উত্তর আসতে বহু মিনিট লেগে যায়। অথচ আলাদা উপ-সমস্যা মাত্র ৫১টি! সমাধান: প্রতিটি উত্তর প্রথমবার হিসাব করে একটি টেবিলে লিখে রাখা, পরের বার টেবিল থেকে পড়া। একে বলে memoization.

static long[] memo = new long[91];
static long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];           // আগেই জানা
    return memo[n] = fib(n - 1) + fib(n - 2);   // প্রথমবার: হিসাব করে লিখে রাখা
}
// fib(50) = 12586269025, fib(90) = 2880067194370816120 — মুহূর্তে

এটাই dynamic programming (DP)-এর হৃদয়: বড় সমস্যার উত্তর ছোট উপ-সমস্যার উত্তর দিয়ে গড়া যায়, আর একই উপ-সমস্যা বারবার আসে — তাই প্রতিটি একবারই সমাধান করো। দুটি লেখার ধরন: top-down (recursion + memo, যেমন ওপরে) আর bottom-up (ছোট থেকে বড় ক্রমে একটি লুপে টেবিল ভরা)। Bottom-up-এ recursion নেই, তাই StackOverflowError-এর ঝুঁকিও নেই — Java-তে কনটেস্টে এটা বড় সুবিধা। (খেয়াল করুন fib(90): প্রায় ২.৯ × ১০^১৮, long-এর সীমার কাছাকাছি; fib(93) আর long-এ ধরে না।)

কয়েন দিয়ে টাকা দেওয়ার কয়টি উপায় — coin change DP

এবার greedy-র উল্টো ধরনের প্রশ্ন: ১, ২ আর ৫ টাকার কয়েন দিয়ে ৬ টাকা কতভাবে দেওয়া যায় (ক্রম গোনা হবে না)? ways[s] = s টাকা বানানোর উপায়ের সংখ্যা। কয়েনগুলো একটি একটি করে “চালু” করি: প্রতিটি কয়েন c-এর জন্য, s টাকা বানানোর নতুন উপায় = আগের উপায় + (s − c টাকা বানানোর উপায়, তারপর একটি c যোগ)। কয়েন বাইরের লুপে থাকায় একই সংমিশ্রণ দুইবার গোনা হয় না।

1long[] ways = new long[amount + 1];2ways[0] = 1;            // শূন্য টাকা: একটিই উপায়3for (int c : coins)4    for (int s = c; s <= amount; s++)5        ways[s] += ways[s - c];

একটি সূক্ষ্ম পার্থক্য খেয়াল করুন: লুপ দুটির ক্রম উল্টালে (বাইরে টাকা, ভেতরে কয়েন) ক্রমসহ উপায় গোনা হয় — ১+২ আর ২+১ আলাদা ধরা হয়। DP-তে “অবস্থা কী, আর কোন ক্রমে ভরব” — এই দুটি প্রশ্নের উত্তরই আসল নকশা। একই ছাঁচে আসে 0/1 knapsack (প্রতিটি জিনিস একবারই নেওয়া যায় — তখন s-এর লুপ উল্টো দিকে, বড় থেকে ছোট চালাতে হয়), সবচেয়ে কম কয়েনে টাকা দেওয়া (যেখানে greedy ব্যর্থ, সেখানে DP সঠিক), আর দুটি লেখার মধ্যে মিল খোঁজা।

৭ · গ্রাফ — adjacency list, BFS, DFS আর Dijkstra

একটি graph হলো কিছু বিন্দু (node) আর তাদের সংযোগ (edge) — ঢাকার থানা আর তাদের মধ্যে বাস-রুট, মানুষ আর বন্ধুত্ব। কনটেস্টে graph রাখার সবচেয়ে প্রচলিত উপায় adjacency list: প্রতিটি node-এর জন্য তার প্রতিবেশীদের একটি তালিকা — List<List<Integer>>. n × n টেবিল (adjacency matrix)-এর বদলে এতে মেমরি লাগে শুধু node আর edge-এর সংখ্যার সমানুপাতে, তাই দুই লাখ node-এর graph-ও রাখা যায়। দূরত্ব বা ভাড়ার মতো ওজন থাকলে প্রতিটি প্রতিবেশীর সাথে ওজনও রাখুন — যেমন List<List<int[]>>, যেখানে int[]{প্রতিবেশী, ওজন}.

BFS আর DFS — queue বনাম stack

পর্ব ৩২-এ গ্রিডে BFS দেখেছেন: একটি queue দিয়ে স্তরে স্তরে ছড়ানো, তাই প্রতিটি ধাপের দাম সমান হলে সবচেয়ে কম ধাপের পথ দেয় — যেমন “মিরপুর থেকে মতিঝিল সবচেয়ে কম কয়টি বাস বদলে”. Queue-এর জায়গায় stack বসালে পাওয়া যায় DFS (Depth-First Search): একটি পথ ধরে যত গভীরে যাওয়া যায় যাওয়া, আটকে গেলে পিছিয়ে অন্য পথ। DFS দিয়ে বোঝা যায় দুটি জায়গা যুক্ত কি না, graph কয়টি বিচ্ছিন্ন টুকরোয় ভাগ, বা কোথাও চক্র (cycle) আছে কি না। Recursion দিয়ে DFS লেখা সবচেয়ে ছোট, কিন্তু অংশ ২-এর StackOverflowError-এর ঝুঁকি আছে; তাই Java-তে iterative রূপটি জানা জরুরি:

boolean[] seen = new boolean[n];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
while (!stack.isEmpty()) {
    int u = stack.pop();
    if (seen[u]) continue;                    // একাধিক পথে ঢুকে থাকতে পারে
    seen[u] = true;
    System.out.print(u + " ");
    for (int v : adj.get(u)) if (!seen[v]) stack.push(v);
}
// edge 0-1, 0-2, 1-3, 2-4, 4-5 হলে: 0 2 4 5 1 3

আউটপুট 0 2 4 5 1 3 (যাচাই করা): ০-এর প্রতিবেশী ১ আর ২ stack-এ গেল, ২ ওপরে থাকায় আগে বের হলো, তারপর তার গভীরে ৪ আর ৫ — শেষে ফিরে এসে ১ আর ৩. BFS আর DFS দুটিই O(V + E): প্রতিটি node আর প্রতিটি edge একবার করে দেখা।

Dijkstra — ওজনওয়ালা রাস্তায় সবচেয়ে ছোট পথ

BFS গোনে বাস বদলের সংখ্যা, কিন্তু যাত্রী জানতে চান মোট সময়। পাঁচটি থানার একটি ছোট মানচিত্র ধরুন (বাসে মিনিট, উদাহরণের জন্য বানানো): মিরপুর–ফার্মগেট ২৫, মিরপুর–মহাখালী ৪০, ফার্মগেট–মহাখালী ১০, ফার্মগেট–মতিঝিল ৪০, মহাখালী–গুলশান ১০, মহাখালী–মতিঝিল ২৫, গুলশান–মতিঝিল ৩০. BFS-এর হিসাবে মিরপুর থেকে মতিঝিল দুই ধাপ (৬৫ মিনিট), কিন্তু তিন ধাপের একটি পথ আরও দ্রুত। এখানে লাগে Dijkstra-র অ্যালগরিদম: যার দূরত্ব এখনো চূড়ান্ত নয়, তাদের মধ্যে সবচেয়ে কাছেরটিকে বের করো — তার দূরত্ব এখন চূড়ান্ত (সব ওজন শূন্য বা ধনাত্মক হলে) — তারপর তার প্রতিবেশীদের দূরত্ব কমানো যায় কি না দেখো। এই “কমানো যায় কি না দেখা”-র নাম relaxation, আর “সবচেয়ে কাছেরটি বের করা”-র জন্য PriorityQueue.

1dist[Mirpur] = 0; pq.offer({0, Mirpur});2top = pq.poll();                // সবচেয়ে কাছের3if (top.d > dist[u]) continue;  // পুরোনো রেকর্ড4for (u → v, ওজন w)5    if (dist[u] + w < dist[v]) { dist[v] = ...; pq.offer }

পুরো প্রোগ্রাম (ইনপুট: প্রথম লাইনে 5 7, তারপর প্রতিটি রাস্তা u v মিনিট; থানার নম্বর ০ মিরপুর, ১ ফার্মগেট, ২ মহাখালী, ৩ গুলশান, ৪ মতিঝিল):

List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
// প্রতিটি রাস্তা u v w: adj.get(u).add(new int[]{v, w}); adj.get(v).add(new int[]{u, w});

long[] dist = new long[n];
int[] prev = new int[n];
Arrays.fill(dist, Long.MAX_VALUE);
Arrays.fill(prev, -1);
dist[0] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
pq.offer(new long[]{0, 0});                       // {দূরত্ব, থানা}
while (!pq.isEmpty()) {
    long[] top = pq.poll();
    int u = (int) top[1];
    if (top[0] > dist[u]) continue;               // পুরোনো রেকর্ড
    for (int[] e : adj.get(u))
        if (dist[u] + e[1] < dist[e[0]]) {
            dist[e[0]] = dist[u] + e[1];
            prev[e[0]] = u;
            pq.offer(new long[]{dist[e[0]], e[0]});
        }
}
Deque<String> path = new ArrayDeque<>();
for (int v = 4; v != -1; v = prev[v]) path.push(name[v]);

Mirpur: 0 min
Farmgate: 25 min
Mohakhali: 35 min
Gulshan: 45 min
Motijheel: 60 min
Mirpur -> Farmgate -> Mohakhali -> Motijheel

এই আউটপুট পুরো প্রোগ্রামটি OpenJDK 21-এ চালিয়ে যাচাই করা। heap-এ long[]{দূরত্ব, node} রাখা হালকা আর দ্রুত; চাইলে একটি record আর Comparator দিয়ে বেশি পরিষ্কার করে লিখতে পারেন। দূরত্ব long, আর Long.MAX_VALUE-কে ∞ ধরা হয়েছে — তার সাথে কখনো কিছু যোগ করবেন না, overflow হয়ে ঋণাত্মক হয়ে যাবে। ঋণাত্মক ওজনে Dijkstra ভুল উত্তর দিতে পারে; সেখানে Bellman–Ford-এর মতো অন্য অ্যালগরিদম লাগে।

৮ · online judge, রায় আর অনুশীলনের পথ

Online judge আপনার কোড গোপন টেস্টে চালিয়ে একটি রায় দেয়। রায়গুলো চিনে নিলে ভুল খোঁজার দিক পাওয়া যায়:

কোথায় অনুশীলন করবেন

• Codeforces — নিয়মিত rated কনটেস্ট, আর হাজারো সমস্যা কঠিনতার rating অনুযায়ী সাজানো।
• AtCoder — জাপানের প্ল্যাটফর্ম; “Beginner Contest” শুরু করার জন্য চমৎকার।
• LeetCode — কোডিং ইন্টারভিউর ধাঁচের সমস্যা; সেখানে ইনপুট-আউটপুট নয়, একটি method লিখতে হয়।
• দেশের ভেতরে — Toph-এর মতো বাংলাদেশি প্ল্যাটফর্মে দেশি কনটেস্ট আর সমস্যা পাওয়া যায়। বিশ্ববিদ্যালয়গুলোর মধ্যে IUPC (inter-university) আর জাতীয় পর্যায়ের NCPC নিয়মিত হয়, আর ঢাকায় বহু বছর ধরে ICPC-র এশীয় আঞ্চলিক পর্ব আয়োজিত হচ্ছে।

যে অভ্যাসে সত্যিকারের উন্নতি হয়

1. নিজের স্তরের একটু ওপরের সমস্যা। rating অনুযায়ী এমন সমস্যা বাছুন, যা ৩০–৬০ মিনিট লড়ে প্রায় পারেন।
2. Upsolving. কনটেস্টে যে সমস্যা পারেননি, শেষে সেটা সমাধান করুন। সবচেয়ে বেশি শেখা হয় এখানে।
3. Editorial পড়ার নিয়ম। আটকে গেলে editorial-এর শুধু প্রথম ইঙ্গিত পড়ুন, তারপর আবার নিজে চেষ্টা করুন। পুরোটা পড়লে কোড না দেখে নিজে লিখুন।
4. Stress testing. WA পেলে কিন্তু ভুল খুঁজে না পেলে: একটি ধীর কিন্তু নিশ্চিতভাবে সঠিক সমাধান (যেমন nested লুপ) লিখুন, ছোট এলোমেলো ইনপুট বানিয়ে দুটি সমাধানের উত্তর মেলান। যে ইনপুটে উত্তর আলাদা, সেটাই আপনার bug-এর ঠিকানা।

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

AI-এর লেখা কনটেস্ট-সমাধান প্রায়ই নমুনা ইনপুটে নিখুঁত চলে, কিন্তু গোপন টেস্টে n = ২ × ১০^৫, মান ১০^৯, আর ইচ্ছে করে রাখা কঠিন ক্ষেত্র থাকে। বারবার দেখা ভুলগুলো:

AI-এর সঠিক ব্যবহার কনটেস্ট শেষ হওয়ার পর শেখার সঙ্গী হিসেবে: editorial ব্যাখ্যা করানো, নিজের সমাধানের complexity যাচাই, আর stress test-এর জন্য ধীর সমাধান ও ইনপুট-জেনারেটর লেখানো। নিচের prompt সমাধান চায় না, বোঝা চায়:

কনটেস্ট-কোড জমা দেওয়ার আগে — চেকলিস্ট

• constraints থেকে complexity হিসাব করেছি, আর আমার পদ্ধতি সেকেন্ডে ~১০^৮-এর হিসাবে চলবে
• সর্বোচ্চ মান গুণ করে দেখেছি — যোগফল, গুণফল, দূরত্ব long-এ
• ইনপুট BufferedReader দিয়ে, আউটপুট জমিয়ে শেষে একবার flush
• n = ১, সব মান সমান, সর্বোচ্চ n — এই edge case-গুলো হাতে চালিয়েছি
• recursion-এর গভীরতা n-এর সমান হতে পারলে iterative করেছি বা বড় stack দিয়েছি
• greedy হলে অন্তত একটি পাল্টা-উদাহরণ খুঁজে দেখেছি; কোডের প্রতিটি লাইন নিজে ব্যাখ্যা করতে পারি