ডায়নামিক প্রোগ্রামিং৯ মিনিট পড়া

ডিজিট ডিপি (Digit DP)

ডিজিট বা অঙ্কের ক্ষেত্রে কোনো বাধা বা সীমাবদ্ধতা যুক্ত থাকলে সেই সংখ্যাগুলোকে গণনা করুন — প্রতিটিকে একে একে চেক না করেই
time:\(O(\text{digits} \cdot 10 \cdot \text{extra\_states})\)space:\(O(\text{digits} \cdot \text{extra\_states})\)typical:N ≤ \(10^{18}\) এর ক্ষেত্রে \(O(18 \cdot 10 \cdot k)\)

ধরুন আপনি দেখতে চাইছেন যে ১ থেকে ১০,০০০ এর মধ্যে ঠিক কতগুলো লকার নম্বরে কোনো ডিজিট বা অঙ্কের পুনরাবৃত্তি নেই (no repeated digits)। এখন একে একে প্রতিটি নম্বর বা সংখ্যা পরীক্ষা করার বা চেক করার অর্থ হলো ঠিক ১০,০০০ বার তুলনা বা কম্পারিজন (comparisons) করা। কিন্তু যদি N এর মান \(10^{18}\) এর সমান হতো? তবে প্রতি ন্যানোসেকেন্ডে একটি করে নম্বর যাচাই বা চেক করলেও সম্পূর্ণ কাজটি শেষ করতে ৩১ বছর সময় লেগে যেত।

ডিজিট ডিপি (Digit DP) এই সমস্যার সমাধান করে মূলত একটি একটি করে ডিজিট (digit by digit) ক্যান্ডিডেট নম্বর বা সংখ্যা তৈরি করার মাধ্যমে, যা সবচেয়ে উল্লেখযোগ্য বা মোস্ট সিগনিফিক্যান্ট (most significant) ডিজিট বা অঙ্ক থেকে শুরু হয়ে নিচের দিকে যেতে থাকে বা এগোতে থাকে। প্রতিটি পজিশনে বা অবস্থানে এসে, এখন পর্যন্ত থাকা নম্বরটি বা তৈরি হওয়া সংখ্যাটি কোনো ভ্যালিড বা সঠিক উত্তরের দিকে এগোচ্ছে কি না সেটি বোঝার জন্য আমরা শুধু ঠিক ততটুকু স্টেট (state) বা অবস্থাই ট্র্যাক করে বা নজরে রাখি যতটুকু আমাদের না রাখলেই নয় — আর তারপর আমরা সেই ফলাফলগুলোকে বা রেজাল্টগুলোকে ক্যাশ (cache) করে রাখি বা জমা করে ফেলি।

আঁটোসাঁটো বাধা বা নিয়মের সীমাবদ্ধতা (The Tight Constraint)

এর পেছনের মূল ধারণাটি হলো। ধরুন আপনি ০ বা 0 থেকে N = 743 পর্যন্ত থাকা ভ্যালিড বা সঠিক নম্বরগুলো গণনা করতে বা গুনতে চাইছেন। আপনি তখন একবারে একটি করে ডিজিট বা অঙ্ক ব্যবহার করে নম্বরগুলো তৈরি করতে শুরু করেন:

  • প্রথম ডিজিট বা অঙ্ক: এটি 0–7 পর্যন্ত যেকোনো কিছু হতে পারে। যদি আপনি 6 কে বা ৭ এর চেয়ে ছোট কোনো অঙ্ককে বেছে নেন, তবে আপনি এখন মুক্ত বা ফ্রি (free) — বাকি ডিজিট বা অঙ্কগুলো 0-9 এর মধ্যে যেকোনো কিছুই হতে পারে। আর যদি আপনি 7 কে বা N এর ঠিক সমান হওয়া ডিজিটকেই বেছে নেন, তখন আপনি একটি আঁটোসাঁটো বা টাইট সীমাবদ্ধতায় (tight constraint) পেঁচিয়ে বা আটকে থাকবেন — যার ফলে এর পরের ডিজিট বা অঙ্ক হতে পারবে বড়জোর 4 পর্যন্ত।

এই টাইট ফ্ল্যাগ (tight flag) বা সীমাবদ্ধতার নির্দেশিকাটি ট্র্যাক করে বা নজর রাখে যে এখন পর্যন্ত বসানো প্রতিটি ডিজিট বা অঙ্ক একদম হুবহু N এর প্রফিক্স বা প্রিফিক্সের (prefix) সাথে মিলে গিয়েছে কি না বা ম্যাচ করেছে কি না। তবে যেকোনো ডিজিট বা অঙ্কের ক্ষেত্রে একবার যদি সেটি N এর চেয়ে নিচের দিকে চলে যায় বা ডাউনে যায়, তখন সাথে সাথেই এই টাইট (tight) নিয়মটি মিথ্যে বা ফলস (false) হয়ে যায় এবং অবশিষ্ট অংশটুকু তখন খুব সহজেই বা স্বাধীনভাবে পুরনো নিয়মে পূরণ করে ফেলা যায়।

স্ট্যান্ডার্ড বা প্রমিত স্টেট ভ্যারিয়েবলগুলো (Standard State Variables)

pos (position) — আমরা বর্তমানে কোন ডিজিট বা অঙ্কের পজিশন বা অবস্থানটি পূরণ করছি (যেখানে 0 = সবচেয়ে বামে থাকা অঙ্ক)।

tight (টাইট বা সীমাবদ্ধতা) — আমরা কি এখনও N-এর প্রিফিক্সের (prefix) দ্বারা সীমাবদ্ধ বা কনস্ট্রেইন্ড (constrained)? যদি এটি সত্য (true) হয়, তবে বর্তমান ডিজিটটি সেই পজিশন বা অবস্থানে শুধুমাত্র N-এর ডিজিট বা অঙ্ক পর্যন্তই যেতে পারবে।

leading_zero (আগাম শূন্য) — আমরা কি ইতিমধ্যেই শুন্য ছাড়া বা নন-জিরো (non-zero) কোনো ডিজিট বা অঙ্ক বসিয়ে ফেলেছি? এটি মূলত "007" কে এমন কিছুর সাথে গণনা করা থেকে আটকায় যার একটি আগাম শূন্য থাকে যা আবার আমাদের পরীক্ষা করা বা নজর রাখা বৈশিষ্ট্যটিকেই (property) ভেঙে ফেলে বা নষ্ট করে দেয়।

accumulated state বা অ্যাকুম্যুলেটেড স্টেট (পুঞ্জীভূত অবস্থা) — আমরা যে বৈশিষ্ট্যটিকেই পজিশনে ধরে রাখছি বা ট্র্যাক করছি: ডিজিটের যোগফল বা ডিজিট সাম মড k (digit sum mod k), বসানো শেষ ডিজিট বা অঙ্ক (যেনো পাশাপাশি থাকা একই সংখ্যা বা অ্যাডজাসেন্ট ডুপ্লিকেট (adjacent duplicate) ধরা যায়), কোনো নির্দিষ্ট ডিজিট বা অঙ্কের গণনা বা কাউন্ট (count), ইত্যাদি।

টেমপ্লেট (The Template)

এর রিকার্সিভ ফাংশনটিকে (recursive function) দেখতে এমন মনে হয়: solve(pos, tight, leading_zero, ...state)। প্রতিটি ধাপে, ডিজিটের বা অঙ্কের লিমিট বা সীমা (tight ? N[pos] : 9) নির্ধারণ করুন বা ঠিক করুন, 0 থেকে শুরু করে লিমিট পর্যন্ত প্রতিটি ডিজিটের চেষ্টা করুন, এর স্টেট বা অবস্থানকে আপডেট (update) করুন, এবং সবশেষে এটিকে রিকার্স বা পুনরাবৃত্তি করুন (recurse)। যেসব স্টেটে বা অবস্থায় tight = false সেগুলোর বা তার ফলাফলগুলোকে মেমোইজ বা ক্যাশে সেভ (memoize) করে রাখুন — এগুলো যেকোনো ধরনের আলাদা প্রিফিক্স (prefixes) জুড়ে পুনরায় ব্যবহারযোগ্য (reusable)।

রেঞ্জ বা সীমানার কুয়েরিগুলো (Range Queries): [L, R] এর মধ্যে গণনা

কোনো ডিজিট ডিপি (Digit DP) খুব স্বাভাবিকভাবেই এই প্রশ্নটির উত্তর দেয় "[0, N] এর মধ্যে ঠিক কতগুলো ভ্যালিড বা সঠিক নম্বর বা সংখ্যা আছে?" [L, R] রেঞ্জ বা সীমার ক্ষেত্রে, সাধারণত count(R) − count(L − 1) পদ্ধতিটি ব্যবহার করা হয়। এটি মাত্র দুটি কলেই (Two calls), এর কাজ সম্পন্ন বা শেষ করে দেয়।

দ্রষ্টব্য: একবার যদি এই টাইট (tight) ফাংশনটি মিথ্যে বা ফলস (false) হয়ে যায়, তবে এর মানে হলো আপনি একটি সম্পূর্ণ মুক্ত বা ফ্রি (free) অঞ্চলে প্রবেশ করে গেছেন — আপনি শুরুতে যেই আপার বাউন্ডই বা উচ্চসীমাই ব্যবহার করে থাকুন না কেন, এখন সাব-প্রোব্লেম বা উপ-সমস্যার (pos, false, leading, state) উত্তর সবসময়ে একই হবে। ঠিক এই কারণেই মূলত কেবল নন-টাইট স্টেটগুলোর বা সীমাবদ্ধতাহীন (non-tight states) অবস্থার ক্ষেত্রেই মেমোইজেশন বা মান সংরক্ষণের ব্যবহার (memoization applies) করা হয়ে থাকে।

[1, N] এর মধ্যে এমন সংখ্যাগুলো গণনা করুন যেখানে পাশাপাশি কোনো দুটি ডিজিট বা অঙ্ক সমান নয়

from functools import lru_cache


def count_no_adjacent(N):
    digits = [int(d) for d in str(N)]
    n = len(digits)


    @lru_cache(maxsize=None)
    def solve(pos, tight, last_digit, leading):
        if pos == n:
            return 1  # valid number built
        limit = digits[pos] if tight else 9
        total = 0
        for d in range(0, limit + 1):
            if not leading and d == last_digit:
                continue  # adjacent duplicate digit
            new_tight = tight and (d == limit)
            new_leading = leading and (d == 0)
            new_last = -1 if new_leading else d
            total += solve(pos + 1, new_tight, new_last, new_leading)
        return total


    return solve(0, True, -1, True)


print(count_no_adjacent(100))   # 91
print(count_no_adjacent(1000))  # 738
Output
91
738

সাধারণ কিছু অ্যাকুম্যুলেটেড বা পুঞ্জীভূত স্টেটসমূহ (Common Accumulated States)

  • 4 ডিজিট বা অঙ্কটি নেই এমন অবস্থা (No digit 4): এর জন্য কোনো অতিরিক্ত স্টেট বা অবস্থার প্রয়োজন নেই — শুধু লুপে (loop) d == 4 আসলে সেটিকে স্কিপ বা বাদ দিয়ে যান।
  • ডিজিটের বা অঙ্কের যোগফল k দ্বারা বিভাজ্য হওয়া (Digit sum divisible by k): এক্ষেত্রে মূলত sum mod k কে অ্যাকুম্যুলেট বা জমা করুন (যার মান হবে 0 থেকে k−1 পর্যন্ত)।
  • পাশাপাশি কোনো সমান ডিজিট বা অঙ্ক নেই (No adjacent equal digits): সবশেষে বসানো ডিজিট বা অঙ্কটিকে স্টোর বা সেভ করে রাখুন (যাদের মান হবে 0-9 পর্যন্ত অথবা লিডিং জিরো বা আগাম শূন্যের ক্ষেত্রে −1)।
  • একটি নির্দিষ্ট ডিজিট বা অঙ্কের কাউন্ট বা গণনা (Count of a specific digit): সেই ডিজিট বা অঙ্কটি ঠিক কতবার এসেছে সেটি স্টোর বা সেভ করে রাখুন।

এখানকার মোট স্টেটের বা অবস্থার স্পেস (state space) হলো পজিশন বা অবস্থান × 2 (tight) × অতিরিক্ত বা এক্সট্রা (extra) স্টেটসমূহ। N-এর মান \(10^{18}\) পর্যন্ত হলে, এদের পজিশনের মান বা অবস্থানের মান ≤ 19 হবে। এই ধরনের বেশিরভাগ সমস্যার ক্ষেত্রেই খুব ছোট বা অতি ক্ষুদ্র আকারের অতিরিক্ত স্টেট (extra state) থাকে, তাই এর মেমোইজেশন টেবিলে (memoization table) শুধুমাত্র কয়েকশ এন্ট্রি বা মান থাকে।

Complexity

🐢 ব্রুট ফোর্স (Brute force)
প্রতিটি নম্বর বা সংখ্যা আলাদাভাবে পরীক্ষা করা (Checking individually) — যা বড়জোর \(10^{18}\) পর্যন্ত রেঞ্জ বা সীমার ক্ষেত্রে একেবারই ব্যবহার অনুপযোগী
রেঞ্জের বা সীমানার আকারে লিনিয়ার (Linear) \(O(R - L)\)
⚡ ডিজিট ডিপি (Digit DP) (সময় বা time)
N ≤ \(10^{18}\) এর ক্ষেত্রে: 19 টি পজিশন বা অবস্থান × 10 টি ডিজিট বা অঙ্ক × নির্দিষ্ট সমস্যা বা প্রোব্লেম-নির্ভর স্টেট — যা প্রায় সময়ই 10,000 এর নিচে থাকে বা 10,000 ops বজায় রাখে
অতিকায় ক্ষুদ্র বা ছোট (Tiny) — N এর সাপেক্ষে লগারিদমিক (logarithmic) \(O(\text{digits} \cdot 10 \cdot \text{states})\)
💾 ডিজিট ডিপি (Digit DP) (স্পেস বা মেমরি / space)
টাইট (Tight) স্টেটগুলোকে ক্যাশ (cached) করা হয় না; বরং এখানকার শুধুমাত্র নন-টাইট (non-tight) স্টেটগুলোকেই পুনরায় ব্যবহার বা রিউজড (reused) করা হয়
নন-টাইট স্টেটগুলোর (non-tight states) জন্য মেমো টেবিল (Memo table) \(O(\text{digits} \cdot \text{states})\)
📐 ডিজিট সাম বা অঙ্কের যোগফল মড (mod) k এর উদাহরণ
এমনকি k = 1000 এর ক্ষেত্রেও, এটি শুধুমাত্র ~190,000 টি স্টেট বা অবস্থার সৃষ্টি করে — যা অপরিহার্যভাবেই প্রায় তাৎক্ষণিক (instant)
১৯ টি পজিশন বা অবস্থান, k-সংখ্যক অতিরিক্ত বা এক্সট্রা স্টেট \(O(19 \cdot 10 \cdot k)\)

ছোট কুইজ

যখন 'টাইট' (tight) ফ্ল্যাগ-টি সত্য বা true (সত্য) হয় তখন এর অর্থ কী বোঝায়?

পড়া চালিয়ে যান