Module ১৪ · যে algorithm-গুলো প্রতি সপ্তাহেই লাগবে: accumulate থেকে nth_element
CP আর interview pack: permutation দিয়ে brute force, prefix আর difference array, k-তম order statistic
Proপড়া
একটা contest problem বলছে n <= 10। Bob বিশ মিনিট ধরে কোনো চালাক কৌশল খোঁজে। Zara শুধু গুণ করে: 10! = 3628800টা ক্রম, আর একটা ক্রম যাচাই করতে লাগে মোটামুটি 10টা ধাপ। মানে প্রায় সাড়ে তিন কোটি ধাপ, এক second-এর ভেতরে দিব্যি। Limit-টাই ছিল ইঙ্গিত, আর pattern 1 হলো সেটা পড়তে পারা।
আপনার জন্য এই lesson টা খোলা কি না দেখা হচ্ছে…
CP আর interview pack: permutation দিয়ে brute force, prefix আর difference array, k-তম order statistic এর ভেতরে কী আছে
- Pattern 1: n ছোট হলে প্রতিটা ক্রম
- Pattern 2: prefix sum আর difference array
- Pattern 3: k-তম order statistic, আর যে median লাঠিগুলো সমান করে
- Interview-এর দশটা প্রশ্ন, নমুনা উত্তরসহ