পাইথনে ব্লক কতবার কভার হয়েছে তা গণনা করার প্রোগ্রাম

মান লওয়া যাক আমাদের কাছে দুটি লিস্ট আছে: walks এবং target। শুরুতে আমরা একটি এক-মাত্রিক লাইনে পজিশন ০-তে আছি। এখন |walks[i]| প্রতিনিধিত্ব করে কত ধাপ হাঁटा হয়েছে। এবং walks[i] পজিটিভ হলে ডানে হাঁটার ইঙ্গিত দেয়, নেগেটিভ হলে বামে। হাঁটার সময় আমরা একটি ব্লক নেয়া হয়, অর্থাৎ পরের বা আগের ইন্টিজার পজিশনে যেতে হয়। আমাদের বের করতে হবে কতগুলো ব্লক কমপক্ষে target সংখ্যক বার হাঁটা হয়েছে।

উদাহরণ

ইনপুট: walks = [3, -7, 2], target = 2

আউটপুট: 5

কারণ নিচের ব্লকগুলো ২ বার হাঁটা হয়েছে: [0, 1], [1, 2], [2, 3], [-4, -3], [-3, -2]

এলগরিদম

1. pos := 0 (শুরুর পজিশন)
2. jumps := একটি হ্যাশ ম্যাপ (ডিফল্ট ভ্যালু ০)
3. প্রতিটি dist in walks এর জন্য:
   • jumps[pos] += 1 যদি dist > 0 অন্যথায় -1
   • jumps[pos + dist] -= 1 যদি dist > 0 অন্যথায় -1 (সংশোধন: মূল লজিকে এন্ডপয়েন্টে বিপরীত চিহ্ন)
   • pos := pos + dist
4. lastpos := 0, level := 0, total := 0
5. jumps-এর সর্টেড কি-ভ্যালু পেয়ারগুলোর জন্য:
   • যদি level >= target: total += pos - lastpos
   • level += val
   • lastpos := pos
6. total রিটার্ন করুন

পাইথন ইমপ্লিমেন্টেশন

from collections import defaultdict

def solve(walks, target):
    pos = 0
    jumps = defaultdict(int)
    for dist in walks:
        jumps[pos] += 1 if dist > 0 else -1
        jumps[pos + dist] -= 1 if dist > 0 else -1
        pos += dist
    lastpos = level = total = 0
    for pos, val in sorted(jumps.items()):
        if level >= target:
            total += pos - lastpos
        level += val
        lastpos = pos
    return total

walks = [3, -7, 2]
target = 2
print(solve(walks, target))  # Output: 5

ইনপুট

[3, -7, 2], 2

আউটপুট

5

অ্যালগরিদমের ব্যাখ্যা

এটি একটি সвиপ লাইন অ্যালগরিদম (sweep line algorithm) / ডিফারেন্স অ্যারে টেকনিক (difference array technique)।

• jumps ডিকশনারি প্রতিটি পজিশনে "এন্ট্রি/এগ্জিট" ইভেন্ট রেকর্ড করে।
• পজিটিভ ডিস্ট্যান্সে: শুরুতে +১, শেষে -১ (প্রিফিক্স সাম ধরে কভারেজ বের করা যায়)।
• নেগেটিভ ডিস্ট্যান্সে: শুরুর পজিশন থেকে শেষ পজিশন পর্যন্ত -১ (কারণ বামে যাওয়া মানে উল্টো দিক)।
• সর্টেড কি-ভ্যালুতে ইটারেট করে প্রিফিক্স সাম (level) মেইনটেইন করা হয়।
• যখন level >= target, সেই সেগমেন্টের দৈর্ঘ্য (pos - lastpos) যোগ করা হয়।

সময় জটিলতা: O(n log n) (সর্টিংয়ের কারণে), স্পেস: O(n)।