Skip to content

024 — Codeforces Blind Pick (Pattern Recognition)

Source

  • 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-র নাম বলা

1. Problem in simple words

এটা একক 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 আন্দাজ করা যায়।

2. Which basic idea does this inherit from?

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

3. What is the hidden math or logic?

লুকানো 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।

4. Which data structure is needed?

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)

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

একটা 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 দিয়ে যাচাই।

8. Example input and 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]

9. Brute force thinking

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

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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 দিয়ে যাচাই করবে।

13. Thinking tweak

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

14. Step-by-step dry run

একটা কাল্পনিক 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-ধাঁচ ✔

15. Python solution

# এই 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!")

16. Line-by-line code explanation

  • 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 করে।

17. Output walkthrough

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-এর বদলি নয়।)

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

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

21. Which basic problem this inherits from

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

22. Similar harder problems

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: "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।