অ্যালগরিদম ও কনটেস্টে Python — constraints থেকে সমাধান

১ · অ্যালগরিদম মানে রেসিপি — আর Python কনটেস্টে কোথায় আলাদা

রাজশাহীর তানভীর একটি অনলাইন দোকানের হিসাব দেখেন। মালিক জানতে চান, “গত বছরের ১২০তম দিন থেকে ২০০তম দিন পর্যন্ত মোট বিক্রি কত?” তানভীর একটি লুপ লিখে ৮১টি দিনের বিক্রি যোগ করে দিলেন। পরদিন মালিক চাইলেন এমন পঞ্চাশটি প্রশ্নের উত্তর। তারপর অ্যাপের ড্যাশবোর্ড প্রতিটি গ্রাহকের জন্য প্রতি মিনিটে এমন হাজারো প্রশ্ন পাঠাতে শুরু করল। একই লুপ, কিন্তু এবার সার্ভার হাঁপিয়ে উঠল।

সমাধানটি কোনো দ্রুত কম্পিউটার নয়, একটি ভালো algorithm. পর্ব ০২-এ দেখেছেন, অ্যালগরিদম হলো একটি সমস্যা সমাধানের নির্দিষ্ট রেসিপি — ধাপগুলোর একটি স্পষ্ট ক্রম। এই পর্বের মূল কথাটি তার সাথে যোগ হয়: প্রতিটি রেসিপির একটি খরচ আছে, আর সেই খরচ ইনপুটের আকারের সাথে বাড়ে. কোনো রেসিপির খরচ দ্বিগুণ ইনপুটে দ্বিগুণ হয়, কোনোটির চার গুণ, কোনোটির প্রায় একই থাকে। পর্ব ৪৩-এ এই বৃদ্ধি মাপার ভাষা দেখেছেন — Big-O. এখন সেই ভাষা কাজে লাগবে আগে থেকে সিদ্ধান্ত নিতে, কোড লেখার আগেই।

Python-এর দুই দিক: হাতিয়ার প্রচুর, লুপ ধীর

অ্যালগরিদম শেখা আর অনুশীলনের জন্য Python খুব আরামদায়ক। কোড পড়তে প্রায় pseudocode-এর মতো, আর স্ট্যান্ডার্ড লাইব্রেরিতে তৈরি আছে কনটেস্টের প্রায় সব মৌলিক হাতিয়ার: sorted (Timsort), heapq, bisect, collections-এর deque, Counter, defaultdict, itertools-এর accumulate, permutations, combinations, আর functools.cache. সংখ্যার আকার নিয়েও চিন্তা নেই — Python-এর int যত বড় দরকার, তত বড় হয়।

অন্য দিকটিও সৎভাবে জানা দরকার। পর্ব ০৫ আর ৪৩-এ দেখেছেন, Python-এর প্রতিটি নির্দেশ interpreter-এর মধ্য দিয়ে যায়, প্রতিটি সংখ্যা একটি object. তাই একই সরল লুপ C++-এর চেয়ে সাধারণত কয়েক দশ গুণ ধীর চলে। কনটেস্টের সময়সীমা প্রায়ই ১-২ সেকেন্ড, আর অনেক সমস্যার সময়সীমা C++-এর কথা ভেবে ঠিক করা। ফলে Python-এ কনটেস্ট করার কৌশল দাঁড়ায় তিনটি: (১) ঠিক complexity — এখানে কোনো ছাড় নেই; (২) ভারী লুপ বিল্ট-ইন আর লাইব্রেরিকে দিয়ে করানো, যাদের ভেতরের লুপ C-তে চলে; (৩) জাজে PyPy থাকলে সেটি বেছে নেওয়া (অংশ ৮)।

২ · constraints পড়ে complexity ঠিক করা

কনটেস্টের প্রতিটি সমস্যার নিচে থাকে constraints — যেমন “1 ≤ n ≤ 2·10^5, 1 ≤ a_i ≤ 10^9”, আর ওপরে সময়সীমা, যেমন “2 seconds”. নতুনরা প্রায়ই এগুলো এড়িয়ে যান, অথচ এটাই সমস্যার সবচেয়ে বড় ইঙ্গিত। সমস্যা-লেখক n-এর সীমা বেছে নেন ঠিক এমনভাবে, যাতে প্রত্যাশিত সমাধান সময়ে শেষ হয় আর সরল কিন্তু ধীর সমাধান আটকে যায়।

হিসাবের জন্য একটি মোটা দাগের সংখ্যা মনে রাখুন: CPython মোটামুটি প্রতি সেকেন্ডে ১০^7 (এক কোটি) সরল কাজ করে. এটা কোনো নির্দিষ্ট মাপ নয় — কাজের ধরন, মেশিন আর Python version ভেদে কয়েক গুণ কম-বেশি হয়; বিল্ট-ইনের ভেতরের কাজ আরও অনেক দ্রুত। C++-এর জন্য একই হিসাব সাধারণত ১০^8 থেকে ১০^9. এই অনুমান দিয়ে constraints থেকে প্রয়োজনীয় time complexity বের করার চলতি টেবিল:

টেবিলটি C++-এর জন্য লেখা টেবিলের চেয়ে একটু সতর্ক। যেমন n ≤ 5000-এ O(n²) মানে আড়াই কোটি ধাপ — C++-এ নিরাপদ, Python-এ প্রায় সীমান্তে। এবার একটি বাস্তব সিদ্ধান্ত ধাপে ধাপে দেখুন:

n টি পণ্যের দাম দেওয়া আছে। কতগুলো জোড়া (i < j)
আছে, যাদের দামের যোগফল বাজেট B-এর বেশি নয়?

1 ≤ n ≤ 2·10^5    1 ≤ দাম, B ≤ 10^9    সময়: 2 s

count = 0
for i in range(n):
    for j in range(i + 1, n):
        if price[i] + price[j] <= B:
            count += 1          # নমুনায় ঠিক উত্তর

n(n − 1) / 2 ≈ (2·10^5)² / 2 = 2·10^10 তুলনা
Python: ~10^7 প্রতি সেকেন্ডে → ~2000 সেকেন্ড
C++   : ~10^9 প্রতি সেকেন্ডে → ~20 সেকেন্ড
# দুই ভাষাতেই TLE — ভাষা নয়, পদ্ধতি বদলাতে হবে

O(n)       = 2·10^5           # খুব আরামে
O(n log n) ≈ 2·10^5 × 18 ≈ 3.6·10^6  # ১ সেকেন্ডের কম
O(n√n)     ≈ 9·10^7           # Python-এ ঝুঁকি
O(n²)      ≈ 4·10^10          # বাদ

price.sort()                   # O(n log n)
lo, hi = 0, n - 1              # দুই আঙুল, O(n)
while lo < hi:
    if price[lo] + price[hi] <= B:
        count += hi - lo       # একসাথে অনেক জোড়া
        lo += 1
    else:
        hi -= 1

Python-এর বিল্ট-ইন কাজগুলোর খরচ

complexity হিসাবের সময় একটি ফাঁদ আছে: Python-এর এক লাইন মানেই এক ধাপ নয়। x in items দেখতে একটি কাজ, কিন্তু list-এ সেটি পুরো list ঘুরে দেখতে পারে। কনটেস্টে সবচেয়ে কাজের খরচগুলো (amortized মানে অনেকবারের গড়):

৩ · কনটেস্টে Python-এর কারিগরি — দ্রুত ইনপুট, recursion limit আর বড় সংখ্যা

সঠিক complexity-র পরেও Python-এ তিনটি জায়গায় অনেকে আটকে যান। তিনটিই অল্প কয়েক লাইনের অভ্যাসে মেটে।

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

পর্ব ১০-এর input() সাধারণ প্রোগ্রামের জন্য চমৎকার, কিন্তু প্রতিটি ডাকের নিজস্ব খরচ আছে। দুই লাখ লাইনের ইনপুটে শুধু পড়তেই যথেষ্ট সময় চলে যেতে পারে, অ্যালগরিদম শুরুর আগেই। online judge-এ Python ব্যবহারকারীদের দুটি প্রচলিত fast I/O পদ্ধতি:

import sys
input = sys.stdin.readline        # পদ্ধতি ১: লাইন ধরে, কিন্তু দ্রুত

def main():
    n = int(input())
    a = list(map(int, input().split()))
    name = input().strip()        # লাইনের শেষে "\n" থাকে — string-এ strip জরুরি
    print(sum(a), name)

main()

import sys

def main():
    data = sys.stdin.buffer.read().split()   # পদ্ধতি ২: পুরো ইনপুট একবারে, টুকরো করে
    t = int(data[0])
    ...
    sys.stdout.write("\n".join(answers) + "\n")   # সব উত্তর একবারে লেখা

main()

প্রথম পদ্ধতিতে sys.stdin.readline লাইনের শেষের newline সহ string দেয়। int() আর split() এই newline নিজেই উপেক্ষা করে, কিন্তু শব্দ তুলনার আগে .strip() ভুলে গেলে "yes\n" == "yes" মিথ্যা হয়ে উত্তর ভুল আসে — খুব পরিচিত বাগ। দ্বিতীয় পদ্ধতি সবচেয়ে দ্রুত: পুরো ইনপুট bytes হিসেবে এক ডাকে আসে, split() সব ফাঁকা জায়গায় ভাগ করে, আর আপনি একটি সূচক এগিয়ে এগিয়ে সংখ্যা নেন। (int() bytes থেকেও সরাসরি সংখ্যা বানাতে পারে।)

আউটপুটেও একই নীতি। এক লাখ উত্তরের জন্য এক লাখবার print ডাকার বদলে উত্তরগুলো একটি list-এ জমিয়ে শেষে "\n".join(...) দিয়ে একবারে লিখুন। join-এর আগে সংখ্যাগুলোকে string বানাতে হয় — map(str, answers). সব কোড main() ফাংশনের ভেতরে রাখার একটি ছোট বাড়তি সুবিধাও আছে: CPython-এ local ভ্যারিয়েবল পড়া global-এর চেয়ে সামান্য সস্তা (পর্ব ৪৩)।

recursion limit — আর কেন নিজের stack নিরাপদ

পর্ব ১৩-এর recursion অনেক অ্যালগরিদমকে সুন্দর করে লেখে — গাছে নামা, DFS, DP. কিন্তু CPython-এ ডিফল্ট সীমা প্রায় ১০০০ স্তর। এক লাখ node-এর একটি লম্বা শিকলের মতো গাছে recursive DFS চালালে আসে RecursionError: maximum recursion depth exceeded. সাধারণ প্রতিকার:

import sys
sys.setrecursionlimit(300_000)     # শুধু Python-এর গোনার সীমা বাড়ে

সমস্যা হলো, এই সীমা শুধু Python-এর হিসাবের খাতা। প্রতিটি ডাক নতুন একটি frame নেয় (পর্ব ১৩-এর call stack), আর খুব গভীর recursion-এ প্রোগ্রামের আসল (অপারেটিং সিস্টেমের দেওয়া) stack মেমরি ফুরিয়ে যেতে পারে — বিশেষত পুরোনো Python version-এ, PyPy-তে, বা functools.cache-এর মতো C-তে লেখা মোড়কের ভেতর দিয়ে ডাক গেলে। তখন সুন্দর traceback-ও আসে না — প্রোগ্রাম হঠাৎ crash করে, জাজ দেখায় Runtime Error. কেউ কেউ threading.stack_size দিয়ে বড় stack-এর একটি thread-এ পুরো সমাধান চালান; এটি কাজ করে, তবে প্ল্যাটফর্মভেদে আচরণ আলাদা। সবচেয়ে নিরাপদ পথ: গভীর হতে পারে এমন DFS নিজের stack দিয়ে iterative লেখা (অংশ ৬)। একটি list-এর append আর pop দিয়েই কাজ চলে, আর গভীরতার কোনো সীমা থাকে না।

বড় সংখ্যা — Python-এ বিনামূল্যে

C বা C++-এ ১০^9 পর্যন্ত দুটি সংখ্যা গুণ করলে ৩২-বিটের int উপচে পড়ে (overflow), আর উত্তর চুপচাপ ভুল হয়ে যায়; কনটেস্টে Wrong Answer-এর সবচেয়ে চেনা কারণগুলোর একটি এটি। Python-এর int arbitrary precision (পর্ব ০৭): 2 ** 200, ১০০-এর ফ্যাক্টোরিয়াল, বিশাল যোগফল — সব নির্ভুল। এটা কনটেস্টে Python-এর একটি সত্যিকারের সুবিধা। তিনটি সতর্কতা মনে রাখুন:

• বড় সংখ্যা ধীর: হাজার অঙ্কের সংখ্যার গুণ এক ধাপ নয়। “উত্তর 10^9 + 7 দিয়ে mod করে দিন” লেখা থাকলে প্রতিটি ধাপেই mod নিন, শেষে একবার নয়। দ্রুত ঘাতের জন্য বিল্ট-ইন pow(a, b, m); Python 3.8 থেকে pow(a, -1, m) দেয় modular inverse.
• বিশাল সংখ্যা string-এ: Python 3.11 থেকে (আর কিছু পুরোনো version-এর নিরাপত্তা আপডেটে) প্রায় ৪৩০০ অঙ্কের বেশি int-কে str() বা print করতে গেলে ডিফল্টে ValueError আসে। সত্যিই দরকার হলে sys.set_int_max_str_digits(0) দিয়ে সীমা তোলা যায়।
• float-এ নয়: int(n ** 0.5) বড় n-এ float-এর কারণে ১ কম-বেশি হতে পারে। পূর্ণসংখ্যার বর্গমূলের জন্য math.isqrt(n), ভাগের জন্য //.

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

prefix sum: একবার হিসাব, বারবার উত্তর

তানভীরের সমস্যায় ফিরে যাই। প্রতিটি প্রশ্নে l থেকে r দিনের বিক্রি নতুন করে যোগ করলে একেকটি প্রশ্নে O(n), q টি প্রশ্নে O(n · q) — দুই লাখ দিন আর দুই লাখ প্রশ্নে চার হাজার কোটি ধাপ। prefix sum-এর ভাবনা: আগে একবার একটি তালিকা বানান, যার i-তম ঘরে থাকবে প্রথম i দিনের মোট বিক্রি। তাহলে l থেকে r-এর যোগফল = (প্রথম r দিনের যোগ) − (প্রথম l−1 দিনের যোগ) — একটি বিয়োগ, O(1).

1sales = [1200, 800, 1500, 900, 2000]2prefix = [0]3for s in sales:4    prefix.append(prefix[-1] + s)5# দিন l থেকে r (1-ভিত্তিক)6print(prefix[r] - prefix[l - 1])

এবার একই সমাধান জাজের ঢঙে — ইনপুট আসে standard input থেকে, আর উত্তর যায় একবারে। প্রথম লাইনে n (দিন) আর q (প্রশ্ন), দ্বিতীয় লাইনে প্রতিদিনের বিক্রি, তারপর প্রতিটি প্রশ্নের l আর r:

import sys
from itertools import accumulate

def main():
    data = sys.stdin.buffer.read().split()      # পুরো ইনপুট একবারে
    n, q = int(data[0]), int(data[1])
    sales = list(map(int, data[2:2 + n]))
    prefix = [0, *accumulate(sales)]            # prefix[i] = প্রথম i দিনের যোগ
    out, pos = [], 2 + n
    for _ in range(q):
        l, r = int(data[pos]), int(data[pos + 1])
        pos += 2
        out.append(prefix[r] - prefix[l - 1])   # প্রতিটি প্রশ্ন O(1)
    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

two pointers আর sliding window: দুই আঙুলের কৌশল

অংশ ২-এর স্টেপারে দেখেছেন দুই আঙুলের এক ঝলক। two pointers কৌশলে একটি সারিতে দুটি সূচক থাকে, আর প্রতিটি ধাপে একটি নিয়ম দেখে ঠিক করা হয় কোনটি সরবে। কোনো সূচক কখনো পেছনে ফেরে না, তাই মোট সরানো সর্বোচ্চ 2n বার — O(n). বাস্তব প্রশ্ন: একটি দোকানে ছয়টি পণ্য, আপনার বাজেট ঠিক ৭৫০ টাকা — কোন দুটি পণ্য কিনলে পুরো টাকা খরচ হয়?

1prices = [120, 250, 300, 450, 600, 800]  # সাজানো2lo, hi = 0, len(prices) - 13while lo < hi:4    total = prices[lo] + prices[hi]5    if total == budget: break6    elif total < budget: lo += 17    else: hi -= 1

sliding window একই পরিবারের কৌশল: দুটি সূচক একটি জানালার দুই কিনারা, আর জানালাটি ডানে সরে। যেমন “পরপর ৭ দিনের সর্বোচ্চ মোট বিক্রি” — প্রতিবার সাত দিন নতুন করে যোগ না করে, নতুন দিন যোগ আর সবচেয়ে পুরোনো দিন বাদ:

def best_week(sales, k=7):
    window = sum(sales[:k])                 # প্রথম জানালা
    best = window
    for i in range(k, len(sales)):
        window += sales[i] - sales[i - k]   # নতুন দিন যোগ, পুরোনো দিন বাদ
        best = max(best, window)
    return best

জানালার আকার বদলাতে পারে এমন সমস্যাতেও (যেমন “যোগফল S-এর বেশি না হওয়া দীর্ঘতম টানা অংশ”) একই ভাবনা: ডান কিনারা সবসময় এগোয়, শর্ত ভাঙলে বাম কিনারা এগোয় যতক্ষণ না শর্ত ফেরে।

৫ · ছাঁচ ২ — খোঁজা আর সাজানো: bisect, উত্তরের ওপর binary search, sort key, greedy

bisect — সাজানো list-এ binary search, তৈরি অবস্থায়

পর্ব ০২-এ linear search আর binary search-এর পার্থক্য দেখেছেন। নিজে binary search লিখলে সীমানায় ১ কম-বেশির ভুল খুব সহজে হয়। Python-এর bisect module এটা নির্ভুলভাবে করে দেয়:

from bisect import bisect_left, bisect_right

prices = [120, 250, 250, 300, 450, 800]      # অবশ্যই সাজানো
bisect_left(prices, 250)     # 1 — প্রথম 250 যে ঘরে
bisect_right(prices, 250)    # 3 — শেষ 250-এর ঠিক পরের ঘর
bisect_right(prices, 300)    # 4 — 300 টাকা বা কম দামের পণ্য 4টি
bisect_right(prices, 250) - bisect_left(prices, 250)   # 2 — 250 কয়বার আছে

দুটির পার্থক্য শুধু সমান মান পেলে কোন দিকে থামবে। “x-এর চেয়ে ছোট কয়টি” = bisect_left(a, x); “x বা তার চেয়ে ছোট কয়টি” = bisect_right(a, x). প্রতিটি O(log n). Python 3.10 থেকে key= parameter-ও আছে। সতর্কতা: list সাজানো না থাকলে bisect কোনো ভুল জানায় না, শুধু ভুল উত্তর দেয়।

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

কনটেস্টের একটি প্রিয় কৌশল binary search on the answer. ধরুন একটি গার্মেন্টস কারখানায় পাঁচটি অর্ডার: ৩০, ১১, ২৩, ৪, ২০ ডজন। একটি লাইন প্রতি ঘণ্টায় k ডজন সেলাই করে, তবে এক ঘণ্টায় একটির বেশি অর্ডার ধরে না। ৬ ঘণ্টায় সব শেষ করতে k-এর সবচেয়ে ছোট মান কত? সরাসরি সূত্র নেই। কিন্তু “k দিয়ে কি ৬ ঘণ্টায় হবে?” — এই হ্যাঁ/না প্রশ্নের উত্তর সহজ, আর k বাড়লে উত্তর একবার “হ্যাঁ” হলে আর কখনো “না” হয় না। এই একমুখী (monotonic) বৈশিষ্ট্য থাকলেই সম্ভাব্য উত্তরের পরিসরে binary search চলে:

def hours_needed(orders, k):
    return sum((x + k - 1) // k for x in orders)    # প্রতিটি অর্ডারে ceil(x / k) ঘণ্টা

def min_speed(orders, h):
    lo, hi = 1, max(orders)          # উত্তর এই পরিসরেই
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_needed(orders, mid) <= h:
            hi = mid                 # mid চলে — আরও ছোট চেষ্টা
        else:
            lo = mid + 1             # mid চলে না — বাড়াতে হবে
    return lo

# min_speed([30, 11, 23, 4, 20], 6) → 23

খরচ: প্রতিটি যাচাই O(n), আর যাচাই হয় log(max) বার — মোট O(n log max). ceil-এর জন্য (x + k - 1) // k পূর্ণসংখ্যার হিসাব; math.ceil(x / k) বড় সংখ্যায় float-এর কারণে ভুল করতে পারে।

key দিয়ে sort, আর কাস্টম তুলনা

Python-এর sort stable আর key function নেয় (পর্ব ১৪, ৩৮)। একাধিক নিয়মে সাজাতে tuple-key সবচেয়ে সহজ — tuple আগে প্রথম উপাদানে তুলনা হয়, সমান হলে দ্বিতীয়তে:

students = [("Rafi", 88), ("Mim", 95), ("Arif", 88)]
students.sort(key=lambda s: (-s[1], s[0]))    # নম্বর বেশি আগে, সমান হলে নামের ক্রমে
# [('Mim', 95), ('Arif', 88), ('Rafi', 88)]

from functools import cmp_to_key
nums = ["3", "30", "34", "5", "9"]            # জুড়ে সবচেয়ে বড় সংখ্যা বানাতে হবে
nums.sort(key=cmp_to_key(lambda a, b: (b + a > a + b) - (b + a < a + b)))
"".join(nums)    # '9534330'

সংখ্যার ক্ষেত্রে -s[1] দিয়ে উল্টো ক্রম পাওয়া যায়। কিছু ক্রম কোনো key দিয়ে প্রকাশ করা কঠিন — যেমন দ্বিতীয় উদাহরণে “a আগে বসবে যদি a + b জোড়া b + a-এর চেয়ে বড় হয়”. তখন দুটি উপাদান তুলনার একটি ফাংশন লিখে cmp_to_key দিয়ে key বানাতে হয়। ফাংশনটি ঋণাত্মক ফেরত দিলে a আগে, ধনাত্মক হলে b আগে।

greedy — প্রতিবার সেরা বাছাই, কিন্তু প্রমাণসহ

greedy algorithm প্রতিটি ধাপে তখনকার সবচেয়ে ভালো দেখানো সিদ্ধান্ত নেয়, পেছনে ফেরে না। একটি ক্লাসিক উদাহরণ: একটি সেমিনার হলে সারাদিনের কয়েকটি বক্তৃতার অনুরোধ, সময় ওভারল্যাপ করে। সবচেয়ে বেশি কয়টি বক্তৃতা রাখা যায়? সঠিক greedy নিয়ম: যেটি সবচেয়ে আগে শেষ হয়, সেটি আগে নিন.

talks = [(9, 11), (10, 12), (11, 13), (12, 14), (13, 15)]   # (শুরু, শেষ)
talks.sort(key=lambda t: t[1])         # আগে যেটি শেষ হয়
end, chosen = 0, []
for start, finish in talks:
    if start >= end:                   # আগের বক্তৃতার সাথে ধাক্কা নেই
        chosen.append((start, finish))
        end = finish
# chosen → [(9, 11), (11, 13), (13, 15)]

এই নিয়মটি প্রমাণসহ সঠিক: আগে শেষ হওয়াটি বাছলে বাকি দিনের জন্য সবচেয়ে বেশি সময় থাকে। কিন্তু “সবচেয়ে ছোট বক্তৃতা আগে” বা “সবচেয়ে আগে শুরু হওয়াটি আগে” — শুনতে যুক্তিসংগত, অথচ ভুল উত্তর দেয়। greedy-র বিপদ এখানেই: অনেক greedy নিয়ম বিশ্বাসযোগ্য শোনায়। সবচেয়ে পরিচিত উদাহরণ নোট বা কয়েন। বাংলাদেশের টাকার নোটে (১, ২, ৫, ১০, ২০, ৫০, ১০০, ২০০, ৫০০, ১০০০) “সবচেয়ে বড় নোট আগে” নিয়মে সবসময় সবচেয়ে কম নোট পাওয়া যায়। কিন্তু নোটগুলো ১, ৬ আর ৭ হলে ১২ টাকার জন্য greedy দেয় ৭ + ১×৫ = ৬টি নোট, অথচ ৬ + ৬ = মাত্র ২টি। এই ভুলটি অংশ ৮-এ একটি প্রোগ্রাম নিজেই খুঁজে বের করবে।

৬ · ছাঁচ ৩ — dict, set আর Counter; stack; গ্রিডে BFS; DFS

hashing: “আগে দেখেছি কি?” প্রশ্নের উত্তর O(1)-এ

অনেক O(n²) সমস্যার ভেতরে লুকিয়ে থাকে একটি প্রশ্ন: “এই মানটি কি আগে এসেছে?” পর্ব ১৬-১৭-এর dict আর set সেই প্রশ্নের উত্তর গড়ে O(1)-এ দেয়। অংশ ৪-এর বাজেট সমস্যাটিই দাম না সাজিয়ে, মূল ঘরসহ:

def two_sum(prices, budget):
    seen = {}                          # দাম → কোন ঘরে দেখেছি
    for i, p in enumerate(prices):
        if budget - p in seen:         # জোড়ার সঙ্গী আগে এসেছে?
            return seen[budget - p], i
        seen[p] = i
    return None

# two_sum([450, 120, 800, 300, 250], 750) → (0, 3)

একবারের পাসে O(n). শব্দ নিয়ে কাজেও একই ভাবনা: দুটি শব্দ একে অপরের anagram (একই অক্ষর, ভিন্ন ক্রম) কি না — Counter(a) == Counter(b) (পর্ব ২৭-এর Counter), বা sorted(a) == sorted(b). অনেক শব্দকে anagram-দলে ভাগ করতে চাবি হিসেবে "".join(sorted(word)) নিয়ে একটি defaultdict(list). সবচেয়ে বেশিবার আসা জিনিস চাইলে Counter(items).most_common(3).

stack: বন্ধনী মেলানো

“{[()]}” ঠিক আছে, “([)]” নেই। প্রতিটি বন্ধ-বন্ধনীকে মিলতে হবে সবচেয়ে শেষে খোলা বন্ধনীর সাথে — শেষে ঢোকা আগে বের হওয়া, অর্থাৎ stack. Python-এ list-ই stack:

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)                       # খোলা — রেখে দিন
        elif not stack or stack.pop() != pairs[ch]:
            return False                           # সঙ্গী নেই, বা ভুল সঙ্গী
    return not stack                               # খোলা কিছু বাকি থাকলে ভুল

গ্রিডে BFS: গোলকধাঁধার সবচেয়ে ছোট পথ

একটি গোলকধাঁধা — কিছু ঘরে দেয়াল (#), শুরু S, শেষ E; প্রতি ধাপে ওপরে, নিচে, বাঁয়ে বা ডানে এক ঘর যাওয়া যায়। সবচেয়ে কম কয় ধাপে E-তে পৌঁছানো যায়? গ্রিডটি আসলে একটি graph: প্রতিটি খোলা ঘর একটি বিন্দু, পাশাপাশি খোলা ঘর সংযুক্ত। ওজনহীন গ্রাফে shortest path-এর অ্যালগরিদম BFS: পুকুরে ঢিল ফেললে যেমন ঢেউ বৃত্তাকারে ছড়ায় — আগে ১ ধাপ দূরের সব ঘর, তারপর ২ ধাপ দূরের সব। এর জন্য লাগে একটি queue, আর Python-এ সেটি collections.deque (list-এর pop(0) O(n), deque-এর popleft() O(1)).

from collections import deque

def shortest_path(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    dist = {start: 0}                          # দেখা ঘর → দূরত্ব
    q = deque([start])
    while q:
        r, c = q.popleft()                     # সবচেয়ে পুরোনোটি আগে
        if (r, c) == goal:
            return dist[(r, c)]
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):   # ওপর, নিচ, বাঁ, ডান
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and grid[nr][nc] != "#" and (nr, nc) not in dist):
                dist[(nr, nc)] = dist[(r, c)] + 1
                q.append((nr, nc))
    return -1                                  # পৌঁছানো যায় না

৩ সারি × ৪ কলামের একটি ছোট গোলকধাঁধায় এই কোড কীভাবে ছড়ায়, ধাপে ধাপে দেখুন। ঘরের সংখ্যাটি শুরু থেকে দূরত্ব; . মানে এখনো দেখা হয়নি।

     কলাম 0  1  2  3
সারি 0  0  .  .  #
সারি 1  #  .  #  .
সারি 2  E  .  .  .

q = deque([(0,0)])

     কলাম 0  1  2  3
সারি 0  0  1  .  #
সারি 1  #  .  #  .
সারি 2  E  .  .  .

q = deque([(0,1)])      # নিচে দেয়াল, শুধু ডানে

     কলাম 0  1  2  3
সারি 0  0  1  2  #
সারি 1  #  2  #  .
সারি 2  E  .  .  .

q = deque([(1,1), (0,2)])  # নিচে, তারপর ডানে

     কলাম 0  1  2  3
সারি 0  0  1  2  #
সারি 1  #  2  #  .
সারি 2  E  3  .  .

q = deque([(2,1)])      # (0,2) থেকে পথ বন্ধ

     কলাম 0  1  2  3
সারি 0  0  1  2  #
সারি 1  #  2  #  .
সারি 2  4  3  4  .

q = deque([(2,0), (2,2)])  # পরের popleft-এ E → উত্তর 4

DFS — recursion দিয়ে, আর নিজের stack দিয়ে

DFS একটি পথ ধরে যত গভীরে সম্ভব যায়, আটকে গেলে ফিরে আসে — “কোন কোন শহরে যাওয়া সম্ভব”, “গ্রাফে কয়টি আলাদা অংশ”, গাছের হিসাব, backtracking. recursion দিয়ে লিখলে প্রায় সংজ্ঞার মতো দেখায়, কিন্তু অংশ ৩-এর গভীরতার সমস্যা আছে। তাই কনটেস্টে Python-এ নিরাপদ রূপটি নিজের stack দিয়ে। গ্রাফটি এখানে একটি adjacency list — প্রতিটি বিন্দুর প্রতিবেশীদের তালিকা:

def reachable(graph, start):          # graph[u] = u-এর প্রতিবেশীদের list
    seen = {start}
    stack = [start]
    while stack:
        u = stack.pop()                # শেষে রাখা আগে — তাই গভীরে আগে
        for v in graph[u]:
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return seen

BFS কোডের সাথে মিলিয়ে দেখুন: পার্থক্য প্রায় শুধু popleft() বনাম pop() — queue বনাম stack. এই এক বদলেই খোঁজার ধরন “স্তরে স্তরে” থেকে “গভীরে আগে” হয়ে যায়। কোন কোন বিন্দুতে পৌঁছানো যায় — এমন প্রশ্নে দুটিই একই উত্তর দেয়; সবচেয়ে ছোট পথের জন্য লাগে BFS.

৭ · ছাঁচ ৪ — DP, heapq আর sieve

dynamic programming: একবার হিসাব, খাতায় রাখা

একটি সিঁড়িতে n ধাপ; একবারে ১ বা ২ ধাপ ওঠা যায়। কত ভাবে ওপরে ওঠা যায়? শেষ লাফটি হয় ১ ধাপের (তার আগে n−1 ধাপে ওঠার সব উপায়) নয়তো ২ ধাপের (n−2-এর সব উপায়) — তাই ways(n) = ways(n-1) + ways(n-2). সরাসরি recursion লিখলে একই উপ-সমস্যা বারবার হিসাব হয়; ডাকের সংখ্যা n-এর সাথে প্রায় দ্বিগুণ হারে বাড়ে। dynamic programming-এর মূল ভাবনা: প্রতিটি উপ-সমস্যা একবারই সমাধান করে উত্তর রেখে দেওয়া। Python-এ সবচেয়ে সহজ পথ functools.cache (পর্ব ৩৫, ৩৮) — এক লাইনেই memoization:

from functools import cache

@cache
def ways(n):                  # n ধাপের সিঁড়ি, একবারে 1 বা 2 ধাপ
    if n <= 1:
        return 1              # base case
    return ways(n - 1) + ways(n - 2)

print(ways(90))               # 4660046610375530309 — চোখের পলকে

@cache ছাড়া ways(90) শেষ হতে হাজার হাজার বছর লাগার কথা; cache-সহ মাত্র ৯১টি আলাদা হিসাব। উত্তরটি ৬৪-বিট সীমার কাছাকাছি, আর Python-এ তা নিয়ে চিন্তাই নেই। তবে লক্ষ করুন — এটি recursion. ways(5000) ডাকলে আবার RecursionError. তখন bottom-up টেবিল: ছোট থেকে বড় ক্রমে একটি list ভরা, কোনো recursion ছাড়া। Python-এ কনটেস্টে bottom-up সাধারণত দ্রুতও, কারণ ফাংশন ডাকের খরচ নেই। অংশ ৮-এর প্রোগ্রামে কয়েন সমস্যার bottom-up DP দেখবেন: best[x] = x টাকা বানাতে সবচেয়ে কম নোট, আর প্রতিটি x-এর জন্য সব নোট চেষ্টা করে best[x - c] + 1-এর সবচেয়ে ছোটটি।

heapq: top-k আর Dijkstra

পর্ব ২৭-এ দেখা heap সবসময় সবচেয়ে ছোট উপাদানটি হাতের কাছে রাখে। Python-এর heapq একটি সাধারণ list-কে min-heap হিসেবে চালায়। একটি অনলাইন কুইজের সবচেয়ে বড় ৩টি স্কোর চাই — পুরো list sort না করেই (top-k, O(n log k)):

import heapq
scores = [78, 95, 62, 88, 91, 70]
heapq.nlargest(3, scores)               # [95, 91, 88]
heapq.nsmallest(2, scores)              # [62, 70]

heap-এর সবচেয়ে বিখ্যাত ব্যবহার একটি priority queue হিসেবে Dijkstra-র অ্যালগরিদমে — রাস্তার দৈর্ঘ্য (ওজন) ভিন্ন হলে সবচেয়ে ছোট পথ। মূল ভাবনা: যে বিন্দুর বর্তমান জানা দূরত্ব সবচেয়ে কম, সেটি আগে চূড়ান্ত করুন। heap সেই “সবচেয়ে কম” প্রতিবার O(log n)-এ দেয়:

import heapq

def dijkstra(graph, src):               # graph[u] = [(v, ওজন), ...]
    dist = {src: 0}
    pq = [(0, src)]                     # (দূরত্ব, বিন্দু) — tuple আগে দূরত্বে তুলনা হয়
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                    # পুরোনো, বাতিল এন্ট্রি
        for v, w in graph[u]:
            if d + w < dist.get(v, float("inf")):
                dist[v] = d + w
                heapq.heappush(pq, (d + w, v))
    return dist

Python-এর heapq-তে “দূরত্ব কমানো” কাজটি নেই, তাই নতুন কম দূরত্ব পেলে আরেকটি এন্ট্রি ঢোকানো হয়, আর পুরোনো এন্ট্রি বের হলে d > dist[u] দেখে বাদ দেওয়া হয় — Python-এ Dijkstra-র এটাই প্রচলিত রূপ। শর্ত মনে রাখুন: কোনো ওজন ঋণাত্মক হলে Dijkstra ভুল উত্তর দিতে পারে। বিস্তারিত গ্রাফ অ্যালগরিদম ABCL TECH-এর ডেটা স্ট্রাকচার ও অ্যালগরিদম কোর্সে.

sieve: সব মৌলিক সংখ্যা একসাথে

১০^6 পর্যন্ত বহু সংখ্যা মৌলিক কি না জানতে হলে প্রতিটি আলাদাভাবে পরীক্ষা না করে sieve of Eratosthenes: ২ থেকে শুরু করে প্রতিটি মৌলিক সংখ্যার সব গুণিতক কেটে দিন; যা বাকি থাকে, সবই মৌলিক। Python-এ গুণিতক কাটার লুপটি slice-assignment দিয়ে C-তে ঠেলে দেওয়া যায়:

from math import isqrt

def primes_upto(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, isqrt(n) + 1):
        if is_prime[p]:
            is_prime[p * p :: p] = [False] * len(range(p * p, n + 1, p))   # সব গুণিতক একবারে
    return [i for i, ok in enumerate(is_prime) if ok]

p × p থেকে শুরু, কারণ তার ছোট গুণিতকগুলো আগের মৌলিক সংখ্যারা ইতিমধ্যে কেটেছে। খরচ প্রায় O(n log log n) — কার্যত রৈখিক। ভেতরের লাইনটি Python-এর নিজস্ব কৌশল: হাতে লেখা for লুপের বদলে একটি slice-এ একসাথে False বসানো, যা অনেক দ্রুত।

৮ · কনটেস্টে ডিবাগিং, প্ল্যাটফর্ম, PyPy আর নৈতিকতা

stress testing — নিজের সমাধানের বিরুদ্ধে প্রমাণ খোঁজা

জাজ বলল Wrong Answer, কিন্তু কোন ইনপুটে — বলে না। নমুনাগুলোয় সব ঠিক। এখানে সবচেয়ে কার্যকর কৌশল stress testing: (১) একটি brute force সমাধান লিখুন — ধীর, কিন্তু এত সরল যে ভুলের সুযোগ কম; (২) একটি নির্দিষ্ট seed দিয়ে হাজারো এলোমেলো ছোট ইনপুট বানান; (৩) দুটি সমাধান চালিয়ে উত্তর মেলান; প্রথম অমিলেই থামুন — সেই ছোট ইনপুটটিই আপনার বাগের ঠিকানা। ছোট ইনপুট কেন? কারণ পাঁচটি সংখ্যার ভুল ইনপুট হাতে কাগজে মেলানো যায়, পাঁচ হাজারের নয়।

অংশ ৫-এর কয়েন প্রশ্নটিই দেখুন। greedy সমাধানটি দ্রুত, আর বাংলাদেশের নোটে সঠিক উত্তরও দেয় — তাই মনে হয় এটাই সমাধান। নিশ্চিত সমাধান হিসেবে bottom-up DP রাখা হলো, আর দুটিকে এলোমেলো নোট-সেটে মেলানো হলো:

import random
def greedy(coins, amount):                  # দ্রুত: সবচেয়ে বড় নোট আগে
    count = 0
    for c in sorted(coins, reverse=True):
        count, amount = count + amount // c, amount % c
    return count
def dp(coins, amount):                      # নিশ্চিত: bottom-up টেবিল
    best = [0] + [amount + 1] * amount      # best[x] = x টাকায় সবচেয়ে কম নোট
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                best[x] = min(best[x], best[x - c] + 1)
    return best[amount]

notes = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000]
print("1880 টাকা:", greedy(notes, 1880), dp(notes, 1880))
random.seed(45)
for t in range(1, 1001):                    # stress test: এলোমেলো ছোট টেস্ট
    coins, amount = [1, *random.sample(range(2, 13), 2)], random.randint(1, 30)
    if greedy(coins, amount) != dp(coins, amount):
        print(f"টেস্ট {t}: নোট {sorted(coins)}, {amount} টাকা -> greedy {greedy(coins, amount)}, dp {dp(coins, amount)}")
        break

কনটেস্টে Wrong Answer-এর আরও কিছু চেনা কারণ, জমা দেওয়ার আগে একবার দেখুন: n = 1 বা খালি ইনপুটের মতো edge case; একাধিক test case-এ আগের টেস্টের ভ্যারিয়েবল পরিষ্কার না করা; readline-এর newline (.strip()); / দিয়ে ভাগ করে float পাওয়া যেখানে // দরকার ছিল; আর আউটপুটের বিন্যাস — “YES” না “Yes”.

প্ল্যাটফর্ম আর PyPy

শুরু করার জন্য পরিচিত কয়েকটি competitive programming প্ল্যাটফর্ম:

পর্ব ৪৩-এ দেখা PyPy কনটেস্টে খুব কাজের। এর JIT গরম লুপকে চলার সময় machine code-এ রূপান্তর করে, তাই বিশুদ্ধ-Python লুপ-ভারী সমাধান প্রায়ই CPython-এর চেয়ে কয়েক গুণ দ্রুত চলে। অনেক জাজে (যেমন Codeforces, AtCoder) ভাষা বেছে নেওয়ার সময় PyPy থাকে; আবার কিছু প্ল্যাটফর্মে শুধু CPython — প্রতিটি প্ল্যাটফর্মে ভাষার তালিকা নিজে দেখে নিন। কয়েকটি সতর্কতা: PyPy-তে গভীর recursion তুলনামূলক ধীর আর বেশি মেমরি নেয়; খুব ছোট ইনপুটে JIT “গরম” হওয়ার আগেই প্রোগ্রাম শেষ, লাভ কম; আর PyPy-র Python version সাধারণত সর্বশেষ CPython-এর চেয়ে পিছিয়ে থাকে, তাই একদম নতুন syntax সেখানে না-ও চলতে পারে। নিয়মটি সহজ: একই কোড দুটিতেই চলে, তাই TLE এলে আগে complexity দেখুন, তারপর PyPy-তে জমা দিয়ে দেখুন।

কনটেস্টের নৈতিকতা

• অন্যের কোড নিজের বলে জমা নয়: চলমান কনটেস্টে সমাধান শেয়ার করা বা অন্যের সমাধান জমা দেওয়া প্রতারণা। প্ল্যাটফর্মগুলো কোডের মিল খুঁজে বের করে, আর এর শাস্তি ফল বাতিল থেকে অ্যাকাউন্ট বন্ধ পর্যন্ত।
• প্রতিটি কনটেস্টের AI-নিয়ম পড়ুন ও মানুন: অনেক কনটেস্ট এখন চলাকালীন AI দিয়ে সমাধান লেখা বা সমস্যা বোঝানো নিষিদ্ধ করেছে; কোথাও নিয়ম আলাদা। নিয়ম না জানলে ধরে নিন নিষিদ্ধ।
• কনটেস্টের পরে শিখুন: না পারা সমস্যার editorial পড়া, অন্যদের সমাধান দেখা — কনটেস্ট শেষ হওয়ার পরে এটাই উন্নতির সবচেয়ে বড় পথ।

৯ · AI-এর যুগে — নমুনায় পাস, বড় ইনপুটে TLE

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

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

AI-এর অ্যালগরিদম-কোড যাচাইয়ের চেকলিস্ট

• constraints থেকে নিজে প্রয়োজনীয় complexity হিসাব করেছি, আর কোডের complexity তার সাথে মিলিয়েছি
• লুপের ভেতরে লুকানো O(n) কাজ (in list, pop(0), slice, min/sum) নেই
• সর্বোচ্চ recursion-এর গভীরতা হিসাব করেছি; বেশি হলে iterative বা bottom-up রূপ ব্যবহার করেছি
• ইনপুট sys.stdin দিয়ে পড়া হচ্ছে, আউটপুট একবারে লেখা হচ্ছে
• সবচেয়ে বড় ইনপুট নিজে বানিয়ে সময় মেপেছি, আর ছোট এলোমেলো ইনপুটে brute force-এর সাথে মিলিয়েছি
• যে কনটেস্টে আছি, তার AI-নিয়ম পড়েছি — নিষিদ্ধ হলে কনটেস্ট শেষ হওয়ার আগে AI ব্যবহার করিনি