কনটেন্টে যান

024 — Codeforces Blind Pick (Pattern Recognition)

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • Original source: Self-directed capstone — Codeforces থেকে চোখ-বুজে একটা 1400–1700 rated DP তুলে নাও
  • Platform: Codeforces — https://codeforces.com/problemset/
  • Topic: dynamic programming (pattern recognition across the whole folder)
  • Difficulty: Hard
  • Pattern: Pattern recognition (any family)
  • Basic idea inherited from: পুরো folder — এটা কোনো নির্দিষ্ট problem নয়, একটা drill: code করার আগে শুধু title + constraints থেকে family-র নাম বলা

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

এটা একক problem নয়, একটা অভ্যাস। Codeforces problemset-এ যাও, "dp" tag দিয়ে filter করো, 1400–1700 rating-এ একটা problem না দেখে তুলে নাও। তারপর statement পড়ার আগে নয়, code লেখার আগে — শুধু title আর constraints থেকে বলো কোন DP family (1D / grid / knapsack / LIS / string / interval / DAG / bitmask)। এই note সেই ritual-টাকে একটা reusable checklist বানায়, আর একটা ছোট worked example দিয়ে দেখায় constraints থেকে কীভাবে family + complexity আন্দাজ করা যায়।

সরাসরি একটি প্রশ্ন দিয়ে শুরু

Codeforces 455A · Boredom দিয়ে শুরু করতে পারেন। একটি value নিলে পাশের value নেওয়া যায় না; value অনুযায়ী লাভ গুনে take-or-skip state ভাবুন। নিচের drill-এর worked example আলাদা; সেটিকে এই judge problem-এর সম্পূর্ণ সমাধান ভাববেন না।

Input ও output

এই note-এর "input" হলো constraint, "output" হলো family-অনুমান:

উদাহরণ
"n <= 18, assign n tasks to n workers, min cost"  -> bitmask DP, dp[mask]
"two strings up to 1000, min ops to make equal"   -> string DP, dp[i][j]
"array up to 1e5, longest increasing subseq"      -> LIS, dp[i] (n log n)
"coins unlimited, make amount A (A up to 1e6)"     -> unbounded knapsack
"grid 1000x1000, min path cost top-left to bottom" -> grid DP, dp[r][c]
"merge n<=300 stones, cost = sum of merged"        -> interval DP, dp[l][r]

চেনা উদাহরণে বোঝা

ভাবো তুমি অভিজ্ঞ একজন ডাক্তার, আর রোগী (problem) ঘরে ঢুকল। তুমি পুরো ইতিহাস শোনার আগেই কয়েকটা লক্ষণ (trigger word, n-এর মান) দেখে সম্ভাব্য রোগের শ্রেণি (family) আন্দাজ করো — তারপর পরীক্ষা (5-step doctrine) করে নিশ্চিত হও। অভিজ্ঞতা মানে দ্রুত সঠিক shortlist বানানো, অন্ধ আন্দাজ নয়।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত্তি গোটা folder — patterns.md-এর family-গুলো, state-transition-thinking.md-এর 5-step doctrine, আর আগের 23টা problem-এর muscle। আগের প্রতিটা note একটা নির্দিষ্ট family শিখিয়েছে; এই capstone সেগুলোকে এক জায়গায় এনে জিজ্ঞেস করে: "অদেখা একটা problem-এ তুমি কি trigger word থেকেই family চিনতে পারো?"

ভেতরের যুক্তি

লুকানো logic constraint-পড়া। n-এর সীমাই target complexity ফাঁস করে দেয়, আর complexity প্রায়ই family-কে সংকীর্ণ করে:

উদাহরণ
n <= ~20            -> 2^n বা n*2^n সম্ভব  -> bitmask DP
n <= ~500           -> O(n^2) বা O(n^3) ঠিক -> interval / two-string grid
n <= ~5000          -> O(n^2) ঠিক           -> LIS(n^2) / knapsack
n <= ~10^5, 10^6    -> O(n) বা O(n log n)    -> 1D linear / LIS(n log n)
দুটো sequence        -> O(n*m) grid          -> string DP
grid দেওয়া           -> O(rows*cols)          -> grid DP
"unlimited / coins"  -> budget axis          -> knapsack

এই mapping-টাই "hidden math": সংখ্যা → অনুমোদিত complexity → সম্ভাব্য family।

কী দিয়ে তথ্য রাখব

family-অনুযায়ী আলাদা — তাই কোনো একক উত্তর নেই, বরং একটা lookup:

উদাহরণ
1D linear   -> dp[i]            (array / দুই rolling variable)
grid        -> dp[r][c]         (2D array)
knapsack    -> dp[budget]       (1D, direction-সচেতন)
LIS         -> dp[i] ends-at-i  (array; n log n হলে tails + bisect)
string DP   -> dp[i][j]         (2D array)
interval    -> dp[l][r]         (2D, length-order fill)
DAG         -> dp[v]            (array + topo order)
bitmask     -> dp[mask]         (size-2^n array)

এটি কেন উপযুক্ত

প্রতিটা family-র state-আকার ঠিক ততটুকু তথ্য ধরে যতটা "শেষ decision" নিতে লাগে — এটাই doctrine-এর core। তাই data structure-টা state-আকারের সরাসরি অনুবাদ: prefix হলে 1D array, দুই sequence হলে 2D, subset মনে রাখা লাগলে bitmask। সঠিক family চিনলে data structure প্রায় নিজে নিজেই ঠিক হয়ে যায়।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা (যেকোনো DP-র আগে): সব সম্ভাবনা enumerate করো — সব subset, সব permutation, বা সব path — আর best/count নাও। এটা প্রায় সবসময় exponential, কিন্তু এটাই সঠিক recurrence-এর কঙ্কাল দেয়: "শেষ decision কী, আর তার আগে কী জানা লাগত?"

কোথায় বেশি কাজ হচ্ছে

enumeration সাধারণত O(2^n), O(n!) বা branching recursion — overlapping subproblem-এর কারণে একই কাজ বারবার হয়। constraint যত বড়, brute তত দ্রুত অচল; আর constraint-এর আকারই বলে দেয় কত দ্রুত হতে হবে, তাই কোন family লাগবে।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: DP problem অসীম মনে হলেও বেশির ভাগই হাতে-গোনা কয়েকটা family-র সদস্য, আর constraint-এর সংখ্যা সেই family-কে আগেই সংকীর্ণ করে দেয়। তাই "এটা কোন DP?" আন্দাজ নয় — এটা trigger word + n-এর একটা lookup।

আরও কম কাজে সমাধান

State (শব্দে): এই capstone-এ "state" হলো তোমার নিজের সিদ্ধান্ত-প্রক্রিয়ার state — কোন family shortlist করেছ আর কেন। কিন্তু drill-টা শক্ত করতে নিচের classify() function একটা concrete decision rule encode করে: feature (trigger word, constraint) → family-নাম।

Transition (decision rule):

উদাহরণ
family = first matching rule among:
    has two sequences            -> "string"
    grid + right/down moves      -> "grid"
    coins/items + capacity       -> "knapsack"
    DAG / prerequisites          -> "dag"
    longest increasing/chain     -> "lis"
    merge/burst a range          -> "interval"
    n <= 20 + use-each-once       -> "bitmask"
    sequence + ways/best to i    -> "1d-linear"

Base case: কোনো rule না মিললে → "needs a creative anchor or extra dimension" (LIS-এর শিক্ষা)।

Answer location: তোমার লেখা family-নাম, যেটা পরে 5-step doctrine দিয়ে যাচাই করবে।

ভাবনার পরিবর্তন

মোচড়: unseen problem-এ সরাসরি code-এ ঝাঁপিয়ো না। আগে family guess লিখে রাখো, তারপর statement পড়ে guess যাচাই করো, তারপর 5 step কাগজে লেখো — তবেই editor। guess vs reality track করলে তোমার pattern-recognition দ্রুত নিজেকে শোধরায়; ভুল guess নিজেই সবচেয়ে দামি feedback।

ছবিতে বোঝা

একটা decision-tree হিসেবে family-spotting:

উদাহরণ
problem পড়ো
   |
   +-- দুটো string / sequence? ------------------> String DP   dp[i][j]
   |
   +-- grid + "right/down"? ---------------------> Grid DP     dp[r][c]
   |
   +-- "coins / items / capacity / budget"? -----> Knapsack    dp[budget]
   |
   +-- "longest increasing / nesting / chain"? --> LIS         dp[i]
   |
   +-- "merge/burst a range, neighbor cost"? ----> Interval    dp[l][r]
   |
   +-- "prerequisites / DAG / longest chain"? ---> DP on DAG   dp[v]
   |
   +-- n <= 20, "use each exactly once"? --------> Bitmask     dp[mask]
   |
   +-- "n steps/days in a row, ways/best"? ------> 1D linear   dp[i]

উপর থেকে নিচে প্রথম যেটা মেলে, সেটাই তোমার প্রথম সন্দেহ — তারপর doctrine দিয়ে যাচাই।

ছোট input-এ ধাপে ধাপে

একটা কাল্পনিক pick: "n ≤ 16 শহর, প্রতিটা ঠিক একবার ঘুরে min total distance":

  1. trigger: "n ≤ 16", "প্রতিটা একবার", "min cost" → subset মনে রাখা লাগবে
  2. constraint: n ≤ 16 → 2^16 ≈ 65536 affordable → bitmask সম্ভব
  3. family guess: bitmask DP, dp[mask][last]
  4. doctrine: state = "কোন শহর-set ভিজিট করা শেষ + এখন কোথায়"; transition = একটা unvisited শহর যোগ
  5. যাচাই: statement পড়ে নিশ্চিত — হ্যাঁ, classic TSP-ধাঁচ ✔

কোড ও ব্যাখ্যা

Python

Python
# এই capstone-এর "solution" হলো একটা family-classifier:
# unseen problem-এর feature দিলে সম্ভাব্য DP family ফেরত দেয়।
# (একটা practice harness, সত্যিকারের solver নয় — কিন্তু runnable ও testable।)

def classify(features):
    """features: trigger word / constraint-এর একটা dict।"""
    n = features.get("n", None)
    text = " ".join(features.get("words", [])).lower()

    if features.get("two_sequences"):
        return "string"
    if features.get("grid") and ("right" in text or "down" in text or "path" in text):
        return "grid"
    if ("coin" in text or "item" in text or "knapsack" in text
            or features.get("capacity")):
        return "knapsack"
    if features.get("dag") or "prerequisite" in text or "dependency" in text:
        return "dag"
    if "increasing" in text or "nesting" in text or "chain" in text:
        return "lis"
    if "merge" in text or "burst" in text or "range" in text:
        return "interval"
    if n is not None and n <= 20 and ("each" in text or "every" in text
                                      or "permutation" in text):
        return "bitmask"
    if "step" in text or "day" in text or "ways" in text or "house" in text:
        return "1d-linear"
    return "needs-anchor"

def target_complexity(n):
    """constraint -> অনুমোদিত complexity (পেন্সিল-rule)।"""
    if n is None:
        return "unknown"
    if n <= 20:
        return "O(2^n) / O(n*2^n)"
    if n <= 500:
        return "O(n^2) / O(n^3)"
    if n <= 5000:
        return "O(n^2)"
    if n <= 10 ** 6:
        return "O(n) / O(n log n)"
    return "O(n) or better"

# ---- tests ----
fam_cases = [
    ({"two_sequences": True, "words": ["min ops to make equal"]}, "string"),
    ({"grid": True, "words": ["min path right down"]}, "grid"),
    ({"words": ["coins unlimited make amount"]}, "knapsack"),
    ({"words": ["longest increasing subsequence"]}, "lis"),
    ({"words": ["merge stones range cost"]}, "interval"),
    ({"words": ["course prerequisite longest chain"], "dag": True}, "dag"),
    ({"n": 16, "words": ["visit every city once permutation"]}, "bitmask"),
    ({"words": ["count ways to climb n steps"]}, "1d-linear"),
    ({"words": ["some weird novel thing"]}, "needs-anchor"),
]
for feat, want in fam_cases:
    assert classify(feat) == want, (feat, classify(feat))

comp_cases = [
    (16, "O(2^n) / O(n*2^n)"),
    (300, "O(n^2) / O(n^3)"),
    (5000, "O(n^2)"),
    (100000, "O(n) / O(n log n)"),
    (None, "unknown"),
]
for n, want in comp_cases:
    assert target_complexity(n) == want, (n, target_complexity(n))

print("সব test pass!")

কোডের প্রতিটি অংশ

  • classify: feature-dict (trigger word + constraint) নেয়; rule-গুলো patterns.md-এর family-spotting table-এর order-এ প্রথম-মিল ভিত্তিতে family-নাম ফেরত দেয়; কিছু না মিললে "needs-anchor"।
  • target_complexity: n-এর মান থেকে অনুমোদিত complexity-এর গুচ্ছ দেয় — ঠিক সেই পেন্সিল-নিয়ম যা contest-এ family সংকীর্ণ করতে কাজে লাগে।
  • দুই test block দেখায় classifier আর complexity-rule দুটোই প্রত্যাশিত family/complexity দেয়; এটা drill-এর mental model-কে concrete করে।

Output মিলিয়ে দেখা

fam_cases-এ নয়টা feature-set: আট family-র একটা করে প্রতিনিধি (string, grid, knapsack, lis, interval, dag, bitmask, 1d-linear) আর একটা "novel" যেটা needs-anchor দেয়। comp_cases-এ পাঁচটা n-মান থেকে complexity। সব assert পাস হলে শেষে print: সব test pass!। (মনে রেখো: এটা একটা teaching harness — সত্যিকারের problem-এ এই rule-গুলো শুধু shortlist দেয়, doctrine-এর বদলি নয়।)

খরচ ও সাধারণ ভুল

সময়

classify ও target_complexity দুটোই O(1) (constant কয়েকটা string-check)। মূল শিক্ষা অবশ্য picked problem-এর complexity আন্দাজ করা — যা family-অনুযায়ী O(n) থেকে O(n·2^n) পর্যন্ত।

অতিরিক্ত জায়গা

harness-টা O(1) auxiliary। আসল DP-র space family-অনুযায়ী — 1D-তে O(n) (বা O(1)), grid/string-এ O(n·m), bitmask-এ O(2^n)।

যে ভুলগুলো এড়াতে হবে

  • statement পুরো না বুঝে family-তে commit করা — guess লেখো, কিন্তু doctrine দিয়ে যাচাই করো; trigger word মাঝে মাঝে বিভ্রান্ত করে।
  • constraint উপেক্ষা করা — একই trigger word ছোট/বড় n-এ আলাদা family চায় (ছোট n হলে bitmask, বড় হলে greedy/অন্য কিছু)।
  • কোনো family না মিললে হাল ছাড়া — সেটাই সংকেত যে state-এ একটা creative anchor বা extra dimension লাগবে (LIS-এর শিক্ষা)।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: পুরো folder। ../patterns.md-এর family-spotting table আর ../state-transition-thinking.md-এর 5-step doctrine — এই দুটোই এই capstone-এর মেরুদণ্ড; classifier-টা ওই table-এরই code-রূপ।

পরের অনুশীলন

কৌশলটি মনে রাখুন

Pattern recognition as a skill: problem পড়ো → trigger word + n দেখো → family shortlist করো → 5-step doctrine-এ যাচাই করো → তারপর code। guess vs reality track করলে recognition দ্রুত নিজেকে শোধরায়। "এটা কোন DP?" হয়ে যায় একটা দ্রুত lookup, অন্ধ আন্দাজ নয়।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "DP capstone = চিনতে শেখা, solve করতে নয়।" Unseen problem-এ আগে family guess লেখো (trigger word + constraint থেকে), তারপর doctrine দিয়ে যাচাই করো, তারপর code। মনে রেখো: constraint-এর সংখ্যাই target complexity ফাঁস করে, আর complexity প্রায়ই family-কে সংকীর্ণ করে — এই reflex-ই পুরো folder-এর আসল পুরস্কার।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।