two pointer

বিশেষ করে codeforces এর অনেক প্রবলেম এর ট্যাগে দেখা যায়  "two pointer" ট্যাগ করা আছে । স্বাভাবিক ভাবেই যেহেতু পয়েন্টার কথাটা আছে নামের সাথে আমি অনেকটা সময় ধরে ভাবতাম এই প্রবলেমগুলা হয়তো পয়েন্টার ব্যাবহার করে করা হয় । অনেকটা ছয় অন্ধের হাতি দেখা গল্পের মত । পরে কোডফরসেস এর একটা কমেন্ট এ একজন এর এক্সপ্লেনেশন দেখি । এরপর একদিন বুয়েট ওনিয়ন টিমের সাকিব ভাইয়াকেও জিজ্ঞাসা করছিলাম এই জিনিসটা কি । ভাইয়া একটা প্রবলেম দিয়ে এর সলুশ্যন বলছিলেন কিভাবে হচ্ছে , এই ট্যাকনিক টাই two pointer । এইখানে  বলে রাখা ভাল অনেক এর এই ট্যাকনিকে স্লাইডিং উইন্ডো ( যেহেতু একটা বাউন্ডারির মধ্যে কাজ করতে হয় এবং বাউন্ডারিটা একটা রেঞ্জ এর মধ্যে উত্তর দেয় তাই ) বলা হয় , দুইটা আসলে একই জিনিস । two pointer সম্পর্কে আরও কিছু বলার আগে আমরা একটা প্রবলেম দেখি ।

আমাদের বলা হল আমাদের কাছে দুইটা সর্টেট array আছে , আমাদের বলতে হবে এই দুইটা array থেকে একটা একটা ভ্যালু নিয়ে আমরা কতভাবে একটা নাম্বার M বানাতে পারি যাদের কোন মধ্যে কোন ডুপলিকেট ভ্যালু নেই ।

যদি আমরা একটু Naive Method দেখি -
এইখানে আমরা inner এবং outer for loop এর দুইটা relation এর মাধ্যমে খুব সহজে Ans বের করে দিতে পারি ।


আমরা  এইখানে N পর্যন্ত দুইটা লুপ চাল্লাচ্ছি । তাই আমাদের টোটাল রানটাইম হয়ে যাচ্ছে  O( N ^ 2 ) । আমরা যদি একটু Modification করি আমরা এইটা কমিয়ে O(N) এ নিয়ে আসতে পারি ।  আমরা দুইটা পয়েন্ট নেই ।
Say low and high । low পয়েন্ট করতেছে আমাদের A array এরটার starting point কে এবং high পয়েন্ট করতেছে আমাদের B array এর ending পজিশনটাকে ।

Observation number one ::

আমরা যদি দেখি A[low] + B[high] > M তাহলে আমরা একটা জিনিস সিউর ভাবে বলতে পারব । আমাদের অবশ্যই B এর ভ্যালু কমাতে হবে । কারণ যেহেতু A[low] হচ্ছে A এর সবথেকে ছোট ভ্যালু সুতরাং  তাকে আর কমিয়ে কখনই B[high] এর সাথে add করে M বানানো যাবে না ।

Observation number two :::

আমরা যদি দেখি A[low] + B[high] < M তাহলে আমাদের অবশ্যই low এর ভ্যালু বাড়াতে হবে । কারণ high হচ্ছে B এর সবথেকে বড় ভ্যালু এর থেকে বড় ভ্যালু নাই । high থেকে আমরা কোন ভ্যালু বাড়াতে পারছি না । তাই অবশ্যই আমাদের এখন low থেকে বাড়াতে হবে ।

এইখানে একটা খটকা লাগতে পারে Observation one এ  যেহেতু A[] array তে left to right যাওয়া হচ্ছে current low ভ্যালু মানে low যাকে right now point করছে A[] array তে তার থেকেও তো কম ভ্যালু আমার array তে থাকতে পারে । আমরা নিচের কোডটা একটু ভাল মত খেয়াল করলেই দেখতে পাব যে যদি থেকে থাকে এবং তার সাথে যদি high B[] array এর এড যদি M এর সমান হয় তাহলে তা আগেই Ans এর সাথে এড হয়ে আসবে ।  একদমই একই কাজ হচ্ছে B[] array তেও । এইখানে আমরা condition দিয়ে দুইটা পয়েন্টকে নিয়ন্ত্রণ করছি ।

এইখানে আমরা low and high দুইটা পয়েন্ট merge করে আগাচ্ছি । এই ধরনের ট্যানিক এ প্রবলেম সল্ভ করাই হচ্ছে two pointer method .

এখন আমরা আরেকটা প্রবলেম এর মাধ্যমে two pointer এর মাধ্যমে কিভাবে প্রবলেম সল্ভ করা হয় এইটা দেখব ।
problem  এইখানে আমাকে N টা নাম্বার দেওয়া থাকবে এবং একটা ভ্যালু দেওয়া থাকবে say S । আমাকে minimum length এর consecutive sub sequence  বের করতে হয়ে যাতে এই consecutive sub sequence এর sum, S এর থেকে বড় বা সমান হয় ।

এই প্রবলেম অনেক এপ্ররোচে আমাদের করা যাবে মনে হইতে পারে । কিন্ত o(n) runtime আনা ব্যাতিত্ব এই প্রবলেম সল্ভ হবে না । o(n) runtime আমরা two pointer ট্যাকনিক এর মাধ্যমে আনতে পারি ।

একই ভাবে আগের প্রবলেম এর মত এইখানে আমরা দুইটা পয়েন্ট নিব । low , high । প্রাথমিক ভাবে দুইটা পয়েন্ট এই given number array এর starting point indicate করে । যতক্ষণ পর্যন্ত না low থেকে high এর sum  , M এর ভ্যালু ক্রস না করে আমরা high এর ভ্যালু বাড়াইয়া যাব । যখনই ক্রস করবে বা সমান হবে তখনই আমরা current length check করব ( high - low + 1 ) যদি minimum ans update করা যায় তাহলে update করব ।  যখনই sum  এর ভ্যালু M এর থেকে বড় হয়ে যাবে তখন আমরা low এর ভ্যালু বাড়ানো সাথে সাথে sum এর ভ্যালু ও adjust করতে থাকব ।

কোডটা দেখলে ব্যাপারটা ক্লিয়ার হয়ে যাবে

এখন যদি আমরা এই কোডটার রান টাইম দেখি । কোডটা high = 0 থেকে high < len পর্যন্ত চলছে । মানে O(n) এ ।

two pointer এর আরো একটা problem হচ্ছে এইটা  । এইখানে আমাদের given array দেওয়া হ্য়নি । আমাদের given formula দিয়ে input ready করে নিতে হবে । এইটা বাদে almost same প্রবলেম হিসাবে মিলে যাচ্ছে আগের প্রবলেমটার সাথে ।

two pointer এর আরো প্রবলেম আইডি এইখানে কমেন্ট জানালে আমি এড করে দিতে পারব । বা কোন ট্যাকনিক কমেন্ট এ দিলে সবাই জানতে পারবে ।

Happy coding :)

Practice Problem :: 1 , 2 .

Backtrack & N Queen

[ এইখানের সব চরিত্রই কাল্পনিক , বাস্তবতার সাথে কাছে , উপরে , নিচে , দূরে কোন খানেই কোন মিল নাই । গল্পে তাই বাস্তবতার সাথে কোন মিল ,  কোন লজিক খুঁজে বেড়ানো  অমূলক । ]    

হাতে একটা DLSR আছে আর কোন মেয়ে পটবে না এমনটা হবে না । রেদোয়ান এরও তাই সখিনাকে পটাইতে টাইম লাগল না । স্বাধীনতার পাওয়া থেকে স্বাধীনতা রক্ষা করা কঠিন । এত এত কম্পিটিশন এর যুগে তাই গার্লফ্রেন্ড রক্ষা করা কঠিন । কত কত থ্রেড আনাচে কানাচে । শিশির ভাবুক ছেলে , মনে গভীরের আবেগ বুঝতে তাই দেড়ি হয়ে গেছিল । ভার্সিটির লিফটে মনের আদান প্রদান হইলেও কিঞ্চিৎ সংকোচের কারণে রেদোয়ান এর কাছে একটু পিছিয়ে ছিল । সখিনা আর রেদোয়ান ক্লাসমেট , শিশির তাদের সিনিয়র । নানা ছালচাতুরে রেদোয়ান শিশির কে ধোঁকা দিয়ে সখিনাকে আগলাইয়া রাখলেও বহুমুখী প্রতিভার অধিকারী শিশির যদি কোনভাবেই সখিনার কাছে মনের ভাব পৌঁছাইয়া দিতে পারে , অতি ভাল ফ্রেন্ড থেকে শুধু  ফ্রেন্ড  সম্পর্কে  সখিনা রেদোয়ানকে নামাইয়া নিয়া আসলেও আসতে পারে । তাই কোন ভাবেই রেদোয়ান শিশির এর  কোন প্রকার নোট , হৃদয় দিয়ে আঁকা ছবি সখিনার কাছে পৌঁছাতে দিতে পারে না । এমনেই সহপাঠী বান্ধবী মাত্রই সিনিয়র ভাইয়াদের প্রতি কিঞ্চিৎ দুর্বল থাকে তারপর যদি সিনিয়র বহুমুখী প্রতিভার অধিকারী হয় । বলা রাখা ভাল আমরা এমন একটা যুগের কথা বলতেছি এইযুগে  লিফট , হাতে DLSR থাকলেও মোবাইল ফোন নাই , এমনকি ফেসবুক ও নাই । এই যুগে ছেলে যতই আধুনিক হোক আশে-পাশে  জুনিওর ছেলে থাকলে সৎ সাহস নিয়ে কোন মেয়ের সাথে কথা বলতে সাহস করে না ।  

যেভাবেই হোক রেদোয়ানকে সখিনাকে রক্ষা করতে হবে যেকোন ধরণের আলাপ-চারিতা   শিশির এর কুনজর থেকে । রেদোয়ান ঠিক একটা N*N rectangle Grid কল্পনা করল সখিনার আসে-পাশে একদম দাবা ঘরের মত । এই ঘর গুলা যদি রেদোয়ান গার্ড দিয়ে রাখতে পারে তাহলে শিশির কখনই সখিনার ধারের কাছেও আসবে না ।  রেদোয়ান এর কিছু স্পেশাল ফ্রেন্ড আছে । যারা সব সময় ভাবেই রেদোয়ান এর লাইফে আসে শুধু দুইজন মানুষ , এক সখিনা আর সে । আর কেউ নাই , আর কেউ থাকবে তা ও কল্পনাও করতে পারে না । তারা আবার দাবা খেলার মন্ত্রীর মত গার্ড দিতে পারে । মানে কেউ কোন ঘরে থাকলে মন্ত্রী যেমন এট্যাক করে তেমন করে গার্ড দিয়ে রাখতে পারে সখিনাকে যেন শিশির কোন ভাবেই সখিনার কাছে আসতে না পারে । এমন কিছুটা 

 

ছবির কালো দাগ দেওয়া জায়গা গুলা দিয়া শিশির কোনভাবেই তাই সখিনার সাথে দেখা করতে যাইতে পারে না । কিন্তু এইখানে একটা ঝামেলা আছে । যেহেতু তারা ভাবে এক এবং একমাত্র সখিনা ছাড়া অন্যকেউ ও আর রেদোয়ান এর মাঝে নাই যদি কোন ভাবে তারা জানতে পারে এই সখিনাকে শিশির এর থেকে গার্ড দেওয়ার কামডা রেদোয়ান অন্য আর কাউকেও দিছে তাহলে অনেক কষ্ট পাবে এবং কি ফ্রন্ডশীপ ও আর না থাকতে পারে ।  রেদোয়ান ও আছে তাই  মহাবিপদে , এক শিশির তো আছেই সুযোগ এর সন্ধানে , যখনই সুযোগ পাবে সখিনার সাথে দেখা করে মনের  মহীসোপানের গভীরে যত আবেগ আছে সব প্রকাশ করে দিতে পারে । শেষমেশ রেদোয়ান ঠিক করল , সুপার বুড়া ভাইয়া মাহির এর কাছে প্রবলেম খুলে বলবে ও ।  

সুপার বুড়া ভাইয়া মাহির খুবই গুরু গম্ভীর মানুষ । প্রোগ্রামিং ছাড়া কোন কথা বলেন না । সব কিছু শুনে অনেকক্ষণ চিন্তা ভাবনা করে বলল “ শুন রেদোয়ান তুমি যে প্রবলেম এ আছ , এইডা খুবই পুরাতন ক্যাসিক্যাল N Queen Problem , যা ১৮৫০ সালেই “Franz  Nauck” নামের এক ভদ্রলোক সমাধান দিয়ে গেছেন । এই সমাধান তোমাকে বুঝতে হবে , শুধু বুঝতে হবে না অন্তর দিয়া ফিল ও করতে হবে তাইলেই তুমি সখিনাকে শিশির এর কুনজর থেকে রক্ষা করতে পারবা ”  

আমরা যে যুগে আছি এইডা হইল ভাল যুগ , এইখানে মানুষ মনের মধ্যে ভয়-ভিতি নিয়ে প্রেম-পিরিতি করে কখন কে এসে প্রেমিকা  ভাগাইয়া নিয়া যায় । তাই যতই কঠিন হোক রেদোয়ানকে বুঝতে হবে N-Queen  প্রবলেম এর সমাধান , নিজের জন্য , নিজের অনাগত নাতি-নাতনীর জন্য যে তারা রেদোয়ানকে দাদু , সখিনাকে দিদা ডাকতে পারে ।

N Queen Problem কি ?

N Queen problem হল একটা N*N দাবা বোর্ডে কত ভাবে N টা queen বসানো যায় যাতে তারা একজন অপরজনকে কোন ভাবে এট্যাক না করে । N Queen problem এর solution এর মাধ্যমে আমরা খুব সহজেই যত কম্বিনেশন আছে তা পেয়ে যেতে পারি । 

Solution :  

Queen যেভাবে এট্যাক করে তাতে প্রতিটা Row এবং column এ মাত্র একজন করে queen  বসতে পারে এবং সাথে সাথে আমাদের চেক করে রাখতে হবে diagonal ভাবে কোন Queen আবার যে ঘরে এই Queen টা কে বসাতে চাচ্ছি তাতে  এট্যাক করে   বসে আছে কিনা । কাজটা আমরা খুব সহজেই backtrack দিয়ে করে ফেলতে পারি । আমরা জানি সব Row তে শুধু মাত্রই একটা করে Queen থাকবে এবং সিরিয়ালই যদি আমরা Queen বসাতে থাকি তাহলে আমাদের শুধু বের করতে হবে কোন Queen কোন কলামে আছে যাতে diagonally ও অন্য কোন Queen যেখানে আমরা এই Queenটা বাসাতে চাচ্ছি তাকে এট্যাক করছে না মানে এইখানে আমরা Queen বসাতে পারি ।

একটা জিনিস খেয়াল করি , যখন আমরা কোন Queen বসাই তখন শুধু এইটা চেক করলেই আগের বসানো কোন Queen এর সাথে এখন যে প্লেস এ Queenটা আমরা বসাতে চাচ্ছি তা conflict করছে কিনা মানে এই পজিশন previous বসানো কোন Queen already attack করে রেখেছে কিনা । এইখানে column এর চেক এর পার্টটা অনেক ইজি কিন্তু diagonally part টা একটু tricky . একটা জিনিস খেয়াল করলে দেখা যাবে যে সব কলাম বাম থেকে নিচের ডান দিকে যায় তাদের row আর column এর বিয়োগ ফল একই হয় এবং যে সব কলাম ডান থেকে নিচের বাম দিকে যায় তাদের row এবং column এর যোগফল একই হয় , মানে একটা Queen এর জন্য কলাম সাপেক্ষে দুইটা আলাদা ভাল্যু আছে যেইটা তারা স্টোর করে রাখে যা তাদের অন্য Queen থেকে different করে ।  কোডটা দেখি

এইখানে আমরা global variable column[] , diagonal1[] , diagonal2[] এর মাধ্যমে কোনটা কোনটা নেওয়া হইছে একটা সল্যুশন এর জন্য তা দেখানো হয়েছে । যখন কোন একটা কল হয় তার আগে আমরা এদের ১ করে দিচ্ছি মানে তাদের নেওয়া শেষ , যতক্ষণ পর্যন্ত না recursion কলটা ফেরত আসতেছে ততক্ষণ তারা ১ থাকবে মানে বুক থাকবে । এইভাবে all solution পাওয়া যায় ।

সারাংশ : 

অতপর আমরা এইটা বুঝতে পারি যে যদি আমাদের গার্লফ্রেন্ড রক্ষা করে রাখতে হয় অবশ্যই আমাদের backtrack এর এপ্লিকেশন N Queen সম্পর্কে ক্লিয়ার ধারণা রাখতে হবে নাহলে যুগ যুগান্তর ধরে শিশির এর মত সুযোগ সন্ধানীরা তাদের ভাগাইয়া নিয়া যাবে । UVA 750 প্রবলেমটা এখন তাই করা উচিত সবার । 

Game Theory ( Sprague Grundy Theorem )

 Sprague Grundy আসলে Nim game এর এই একটা variant . Nim Game এ কি থাকে অনেক গুলা পাইপ/বাক্স এমনসব জিনিস একটা row তে থাকে এবং তাদের মধ্যে কিছু সংখ্যক জিনিসপাতি থাকে ( কার্ড , বল এইসব হাবিজাবি ) একটা single move এ কোন player যে কোন সংখ্যক জিনিসপাতি একটা নিদিষ্ট  পাইপ/ বাক্স থেকে তুলে ফেলতে পারে । যদি কোন player কোন move এ কোন item  তুলতে না পারি তাহলে ও এই গেম হেরে যাবে । solution টা কি আমি চোখ বন্ধ করে পাইপে যা কিছু আসে এই ভ্যালু গুলারে xor করতে  থাকি  যদি Ans non zero কিছু হয় তাহলে আমার প্রথম player জিতে যাবে যদি তা না হয় তাহলে জয় লাভ করবে আমার second player . এইটা কেন হয় একটু ব্যাখ্যা করে নেই । ধরে নেই আমার কাছে ১৬টা কার্ড আছে । এইগুলা বিভিন্ন row তে আছে । ধরলাম ৪টা row তে আছে ।

• ১ নাম্বার row এ আছে ১টা কার্ড

• ২ নাম্বার row এ আছে ৩টা কার্ড

• ৩ নাম্বার row এ আছে ৫টা কার্ড

• ৭ নাম্বার row এ আছে ৭টা কার্ড

আমি যে কোন move এ যে  কোন সংখ্যক কার্ড যে কোন row থেকে তুলে নিতে পারি । আমি বলতে আসলে এইখানে যে দুই জন player খেলছেন । যখন কোন player কোন কার্ড তুলতে পারবে না তিনি হেরে যাবেন । এর solution process এ প্রতিটি row যে যত সংখ্যক কার্ড আছে তাদেরকে binary number এ represent করা হয় । তাদের প্রতিটা পজিশন এর xor value calculate করা হয় । এদের ভ্যালু হচ্ছে আমার সেই state এর Nim sum .যদি কোন state এর Nim sum non zero কোন কিছু হয় তাহলে এইটা হল winning state ( মানে এই state এ যে player আছেন তিনি optimal game খেললে জিতবেন ) আর zero থাকলে losing state ( হেরে যাবেন ) । যেমন এইখানে লক্ষ্য করি

for 1st row here is one card   -->  001
for 2nd row 3 cards so          --->  011
for 3rd                                   ->  101
And for 4th row                  ----- >111
                                    _________________
                                                  000 ( xor each position bit , if even numbers of 1 or o its o other wise its 1 )

এই অবস্থায় প্রথম player যাই দেন না কেন second player always Nim sum zero করে তার কাছে next move পাঠাবে । এতে দেখা যায় এমন কিছু থাকলে কখনই প্রথম player win করতে পারে না ।
wiki তে এর একটা proof দেখানো হইছে লিঙ্ক

এখন যদি আমাকে restriction দিয়ে দেয় যে না ভাই তুমি যা খুশী চাইলেই তুলে নিতে পারবা না । কিছু রুল থাকবে । ঐ সংখ্যক নেওয়া যাবে ( যদি যায় ) তাহলে কোন state এর Nim sum 0 থাকলেও দেখা যেতে পারে যে player restricted rule এর কারণে win করছে । তাহলে আমরা কিভাবে বুঝব যে কে জিততে যাচ্ছে । এর উত্তর নিয়ে আসে Sprague grundy theorem । এইখানে বলা হয় কোন state এর grundy value হচ্ছে সেই state থেকে যে সব state এ যাওয়া যায় তাদের ভ্যালুর মধ্যে যে সর্বনিম্ন ভ্যালুটা নেই ওটা । মানে হইল ধরি কোন state A থেকে B , C , D তিনটা state এ যাওয়া যায় যাদের grundy value হল যথাক্রমে {০,১,৪} তাহলে A state এর grundy value কত ? এইখানে A এর grundy value হবে ২ , কারণ A থেকে যাদের কাছে যাওয়া যায় তাদের কারো কাছে নেই এমন সব থেকে ছোট  ২  । কোন state এর grundy value 0 হওয়া মানে হইল এই state টা হচ্ছে হারার state . ০ বাদে যে কোন স্টেটই হচ্ছে আমার জিতার state . এইভাবে Sprague grundy solution এ আমার সবগুলা পাইপ এর grundy value বের করে Nim এর মত xor করা হয় যদি পজিটিভ কিছু থাকে তাহলে প্রথম player জিতবে নতুবা হারবে । যে কোন জিনিস বুঝার সব থেকে ভাল উপায় হল এর কোন প্রবলেম দেখা । আমরা এখন একটা basic problem দেখি ।  

প্রবলেম link এই প্রবলেম এ বলা হইছে দুই জন player খেলছে little chef আর head chef . তাদের সামনে অনেকগুলা piles আছে যেসব pile এ stone আছে । একটা single move এ একজন n^n আকারে stone কোন pile থেকে রিমুভ করতে পারে । মানে ( 1^1 ==1 , 2^2 == 4 , 3^3 == 27 , 4^4 == 256 ..... ) এমন সংখ্যক । আমাকে বলতে হবে যদি তারা optimal খেলে তাহলে কে জিতবে এবং little chef first move টা দেয় । এইখানে constrain থেকে দেখা যায় প্রতিটা pile এ highest stone থাকতে পারে 100000 মানে আমি highest 6^6 = 46656 টা stone নিতে পারি । এখন আমি কোডটা দেখি 

কোড

এইখানে আমি প্রতিটা pile এর grundy value বের করে xor করে দেখব । positive হলে little chef আর না হলে head chef জিতবে । প্রায় একই রকম একটা প্রবলেম হচ্ছে light oj 1315 - Game of Hyper Knights .
এইখানে pile এর বদলে আমাকে দাবা খেলার ঘোড়া দিয়েছে এবং তাদের মুভ restricted করে দিয়েছে । আমাকে বলতে হবে কে জিতবে Bob ভাইয়া না Alice আপু । এইখানেও base case হচ্ছে (০,০) নাম্বার পজিশন যার grundy value হচ্ছে ০ ( হারার স্টেট বলে ) । উপরের প্রসেসটা বুঝা গিয়ে থাকলে এই প্রবলেমটা এখন সবার পারা উচিত ।

যাই হোক এইটুকুই আসলে আমি জানি  Sprague Grundy  সম্পর্কে । এর জন্য আমি বিশেষ ধন্যবাদ দিতে চাই one and only halfo কে :D যার কাছ থেকে আমি এই সুন্দর জিনিসটা শিখছিলাম । এখন আর একটু নেট ঘাটাঘাটি করে সবাইকে বাকিটুকু শিখতে হবে ।

[ বিদ্রঃ আমি নিজে খুবই বাজে কোডার । আমার কোন লেখাই অন্ধ বিশ্বাসে ঠিক ধরে নেওয়া বোকামি । আমি তো নিজেকে নিজেই ভুলবাল বুঝাই :P তাই এইখানেও অনেক ভুল জিনিস থাকতে পারে । সব সময়ই সব কিছু নেট থেকে যাচাই করে নিতে হবে ] 

Binary Search part - 1

 বাইনারি সার্চ কি ? 

বাইনারি সার্চ হচ্ছে একটা sorted array তে কোন Key value (  যেইটা আমি খুঁজে বের করতে চাচ্ছি ) এর position বের করা । অধিকাংশ  ভার্সিটিতেই ফাস্ট ইয়ারের কোন না কোন কোর্সে ( আমি প্রথম জানতে পারি আমার ১/২ এর ডিসক্রিট ম্যাথ কোর্সে ) পড়ানো হয় তাই  আল্গরিথম নিয়ে কারো কোন প্রবলেম থাকে না , প্রবলেম হয় এর Use এ । কখন কোথায় আমার বাইনারি সার্চ লাগবে এইটা ধরতে । পৃথিবীর অনেক সুন্দর আল্গরিথম এর মধ্যে আমার মনে বাইনারি সার্চ একটি । কত কঠিন দেখতে লাগা প্রবলেম গুলাকে কত easy করে দেয় ।
আমি ধরে নিচ্ছি যারা এইটা পড়ছে সবারই Binary search নিয়ে idea আছে । কিভাবে code হয় । যদি তাও কারো না থেকে থাকে তাহলে নিচের দুইটা লিঙ্ক দেখলেই সবার ক্লিয়ার হয়ে যাবে । 

(১) টপ কোডার বাইনারি সার্চ                                                                                                              

(২)আসিফের হ-য-ব-র-ল ( Painless Binary Search )                                                                        

আমার এই লেখাটার উদ্দেশ্য হচ্ছে কিছু interesting problem এ আমি যদি binary search চালাই তাহলে  কিভাবে solution আমি খুব সহজেই পেয়ে যাই তা আলোচনা করা । আমি নিজে খুবই বাজে কোডার হয়ত আমার প্রসেস গুলা থেকেও ভাল প্রসেস আছে আমি এই প্রসেস এ AC পাইছিলাম তা আলোচনা করার চেস্টা করতেছি । লিখাটা আমার অনেক গুলা পার্ট এ করার ইচ্ছা আছে কারণ binary search এর এত এত সুন্দর problem আছে একটা পার্ট লিখা সম্ভব না :D

যেসব জিনিসপাতি সবাই জানি :

আচ্ছা যদিও আমরা সবাই জানি তাও কয়েকটা বিষয় আগে রিভাইস দিয়ে নেই বাইনারি সার্চ এর প্রবলেম দেখার আগে । 

•  কোন sorted array binary search চালানো মানে lg(n) এর calculation করা । lg(n) এর মানে আমি কিছুটা এমন কল্পনা করতে পারি যদি n এর value  ১০০ হয় তাহলে  ১০০  < ২ ^  ( এর যে পাওয়ার use করলে এর মান বড় হয় তত গুলা অপারেশন ) যেমন এইখানে ৭ ,  ১০০ < ২ ^ ৭ ( ১২৮ ) । অর্থাৎ যদি ১০০ length এর কোন array এর উপর আমার বাইনারি সার্চ চালানো হয় তাহলে আমার মাত্র ৭টা অপারেশন করা লাগবে । 
• বাইনারি সার্চ আমি শুধু মাত্র sorted value এর উপর করতে পারব । 
• lower_bound ( আমাকে একই value এর অনেক গুলা জিনিস থাকলে এদের সবার প্রথমের value এর index return করবে ) ও upper_bound  ( almost same as lower_bound this time we will get the highest index of the key value + 1 , if there is no match then we will get immediate highest index ) 

Light Oj 1048 - Conquering Keokradong :::

এই প্রবলেমটা অনেক interesting . আমি  Keokradong climb করতে যাচ্ছি এর জন্য আমাকে  বিভিন্ন ক্যাম্পের distance দেওয়া আছে । ( এইখানে একটা ক্যাম্পের distance আর আগের ক্যাম্পের সাপেক্ষে ) . এখন আমাকে একটা লিমিট দেওয়া হইছে ( K ) এর মানে হইল আমাকে আমার পুরা tripটা k+1 camp এ নিয়ে আসতে হবে ( যেখানে আমি K night থাকব ) কিন্তু এমন ভাবে যেন আমার দুইটা ক্যাম্পের distance এর maximum value minimum হয় , আসলে এইখানে বলা হইছে আমি highest আমার trip কে k+1 এ ভাগ করতে পারি কিভাবে যেখানে পর পর ক্যাম্পের মধ্যে distance সব থেকে কম হয় । 

এখন দেখি প্রবলেমটা পড়ার সাথে সাথে আমার মাথায় কি কি চিন্তা আসতে পারে । প্রথমত আমাকে আসলে এমন কোন value নিতে হবে যাতে আমার পর পর ক্যাম্পের মধ্যে Distance কম হয় যদি দেখি এইটা কম আছে তাহলে আমি ওই ক্যাম্পটা skip করে Ans generate করার চেস্টা করব । আমাকে এমন sample case দেওয়া হইছে আমি Idea পাওয়ার সাথে সাথে মনে হবে আরে এমনই । ইয়েস পাইছি Idea । কোড করে সাথে সাথে submit এমন সুন্দর একটা verdict "Wrong Answer"  । ও আচ্ছা আমি এইটা মিস করছি আমাকে N এর value 1000 দেওয়া হইতে পারে এমন K এর মান হইতে পারে min ( N , 300 ) । তাহলে skipটা N-k শুধু একটা value এর উপরও হয়ত থাকতেছে না আমাকে অনেক গুলা position এই এমন কাজ করতে হয়ত হইতে পারে । মানে এমন অনেক কেস এই থাকবে যেখানে আমাকে এমন করে দেখতে হবে । আচ্ছা তাইলে বুঝছি DP করে করত হবে , অর্থাৎ আমাকে খালি বের করতে হবে skip পয়েন্ট গুলা কোনগুলা । normal sense এ যখন দেখি N এর মান 10000 হয়( মানে একটা ক্যাম্প থেকে অন্য ক্যাম্পের distance ) হইতে পারে মানে যদি আমি Dp করতে যাই তাহলে worst case এ N-k == 999*10000 == 9990000 লাগতেছে আর position er junno 1000 তো আছেই । অর্থাৎ যদি কোন compiler dp[1000][9990000] এমন কিছু declear করার permission আমাকে দেয় এবং অভয় দেয় পাগলা কোড কর আমি দ্রুতই Ans generate করে দিব তাহলে আমি একটা try দেওয়ার হইলেও দিতে পারতাম । যেইটা বর্তমান সময়ে কেউ দিচ্ছি না so dp এর চিন্তা বাদ । এতক্ষণ আমি খালি value skip এর পয়েন্ট নিয়েই চিন্তা ভাবনা করছি এখন এইটা বাদ দিয়ে দেখি অন্য কিছু ভাবা যায় নাকি । আসলে আমার main concern এর ব্যাপাটা হইল max value । আমি যদি max value ঠিক করে দেখি এমন কিছু করা possible কিনা মানে এই Max value এর জন্য আমার পুরা tripটাকে K part এ ভাগ করা যায় কিনা । যদি যায় তাহলে আমি Max value কমাইয়া দেখব এইভাবে possible হচ্ছে কিনা যদি হয় তাহলে কম Max value এর আমার Ans . এই কাজটাই আমি খুব সহজেই binary search এ করতে পারি । এইখানে Max value এর highest value  কি হইতে পারে সবগুলা ক্যাম্পের distance এর যোগফল কারণ এর চেয়ে বেশি কিছু আমার লাগতেছে না । আর lowest অবশ্যই পর পর দুইটা ক্যাম্পের মধ্যে যে distance তাদের মধ্যে highest টা ( কারণ K <= min ( n , 3000 ) ) .এখন All possible এর মধ্যে আমি lowest possibleটা নিব মানে এইখানে আমার lower_bound এর concept লাগতেছে । 

ক্যাম্প সাইট পিন্ট এর কাজটা এর পর অনেক সোজা । তাই আর আলোচনা করতেছি না । সবাই এখনই বুঝে গেছে না গেলে খাতা কলমে চিন্তা করে বের করতে হবে :D সব তো বলা ঠিক না :D 

প্রিন্ট এর কাজ বাদ দিয়ে same concept এ একটা প্রবলেম আছে এই প্রবলেম এর solution process বুঝা হয়ে গেলে  এইটাও সবার Try করা উচিত ।
 Light Oj 1076

Renting Bikes :::: 

এইটা আরেকটা খুবই চমৎকার binary search এর প্রবলেম । এই প্রবলেম এ কি বলা হইছে বলি । এইখানে বলা আছে N টা school boy আছে যাদের কোন bike নাই তারা bike রেন্ট নিতে পারে । যে site bike rent দেয় তাদের M টা bike আছে । প্রতিটা bike rent এর জন্য আলাদা আলাদা ফিক্সড প্রাইজ আছে । school boy গ্রুপ এর কিছু কমন মানি আছে ( সবার চাঁদা ধরতে পারি ) যেই টাকা তারা bike rent এ use করতে পারে কিন্তু কেউ নিজের টাকা থেকে অন্যকে টারা ধার দিতে পারে না এবং তারা রেন্ট নেওয়া বাইক শেয়ার ও করে না । আমাকে বলতে হবে maximum কয়টা boy bike রেন্ট নিতে পারবে এবং তাদের মিনিমাম কতটা খরচ করতে হইতে পারে ( মানে নিজেদের টাকা ) । 

প্রবলেমটা পড়ার সাথে সাথে মাথায় Idea আসে এইটা অবশ্যই greedy problem এমন কোন না কোন ভাবে sorting করে value গুলা use করতে হবে এবং অবশ্যই আমি যার নিজের টাকা বেশী তাকে বাইক দিতে চেস্টা করব । যদি আমি আরো একটু ভাবি যদি আমি ঠিক করে ফেলি আমি ৩জন কে bike দিব তাহলে অবশ্যই এইটা সবথেকে ভাল যার সবথেকে বেশী টাকা পয়সা আছে ও কিনবে ৩ নাম্বার সব থেকে কম cost এর বাইক , তারপরের জন্য ২ নাম্বার , এবং শেষজন সবথেকে কম cost এর বাইক । এই যে 3 জন ফিক্সড করে চেক করা এইটাই তো বাইনারি সার্চ :D আর যদি আরও একটু ভাবি code টা হবে upper_bound এর মত অর্থাৎ আমি সব সময় চেস্টা করব যেন আমি সব থেকে বেশী জন নিতে পারি । আর একটা পয়েন্ট আমি সব সময়ই আমার common money এর পুরাটাই use করব । 

    কোড

Present  :::: 

এইটা ও খুব চমৎকার প্রবলেম । এইখানে বলা হইছে beaver নামে এক পিচ্চি নতুন প্রোগ্রামিং শিখতেছে । ও তার প্রিয় ম্যামকে ম্যামের বার্থডে তার বাগানের ফুল গিফট করতে চায় ( ছেলে চালু পাবলিক :P ) । কিন্তু এইটা bad manners to present little flowers কিন্ত্ তার বাগানের ফুলগুলা হঠাৎ করে আর বড় হচ্ছে না এখন এর m days বাকি আছে বার্ডে থেকে । ও স্পেশাল একটা water পাইছে যেইটা দিলে next day তে ফুল গুলা 1 unit height বাড়ে । কিন্ত্ প্রবলেম হইল এই special water ও w wide এর contiguous flower কে শুধু মাত্র স্প্রে করতে পারে একদিনে  । আমাকে বলতে হবে ফুলগুলার minimum height কত হবে gift এর সময় মানে গিফট দেওয়া ফুলাগুলার মধ্যে কোন ফুলের height সব থেকে কম হবে ।  

    আমি যখনই দেখব আমাকে Min বা Max এর কোন ক্যালকুলেশন এর প্রয়োজন হচ্ছে আমি চেস্টা করে দেখব যে এইটা কোনভাবে binary search এ ফেলা যাচ্ছে কিনা । অধিকাংশ ক্ষেত্রেই দেখা যাবে Ans আসসে বা যদি দেখি Ans আসতেছে আমি binary search করার চেস্টা করব । এই প্রবলেমটা দেখি আমাকে কি করতে হবে । আমি ফুলগুলার highest min value calculation করব for sure এইটা করতে হবে binary search এ । আর যদি একটু ভাবি এতে upper_bound এর একটা ভাব আছে । all possible Ans থেকে আমি ম্যাক্স নিব । এখন দেখি কিভাবে । 

টানা লিখা আসলে অনেক ধৈর্যের  ব্যাপার :P আর পারতেছি না এখন লিখলেও খারাপ হবে । Next part এ আরও কিছু interesting প্রসেস লিখার চেস্টা করব । আর কেউ ভাল কোন প্রবলেম করে থাকলে কমেন্ট এ সবার জন্য suggest করতে পারেন যাতে আমরা সবাই এইখান থেকে শিখতে পারি ।

Greedy Method

Greedy কি ? 

 প্রথমেই আসা যাক , greedy কি ? greedy হল ভবিষ্যতের এর কথা চিন্তা না করে বর্তমান অবস্থা গুলা বিবেচনা করে বেস্ট একশনটা নেওয়া । হয়ত এইটা পরবর্তীতে সবথেকে optimal নাও  হতে পারে । greedy solution তো optimal না তাহলে কেনই বা আমি greedy solution নিতে চাব । প্রথমত greedy solution time efficient । এমন অনেক ক্ষেত্রেই ধরে নেওয়া হয় greedy solution টাই best possible Ans . greedy solution যেহেতু  implement করা সহজ তাই অনেক optimized problem এর solution এর জন্য greedy use করা হয় । 

কিছু পরিচিত greedy process Change Making , kruskal Algorithm , Activity Selection . 

Change Making : 

        Change Making problem এ বলা হয় আমার কাছে অনেক গুলা বিভিন্ন মানের মুদ্রা আছে । আমাকে কোন সব থেকে কম মুদ্রা ব্যবহার করে Change দিতে হবে । আমি কিভাবে কাজটা করব । 

      এর প্রসেস হচ্ছে আমি সবসময় সবথেকে বড় মুদ্রাটা থেকে স্টার্ট করব এবং যতক্ষণ পর্যন্ত না এর ভ্যালু আমার change  ( একটা নিয়ে Total change  ভ্যালু থেকে subtract করা তো আছেই ) এর amount থেকে বড় হয়ে যাবে আমি নিতে থাকব , যদি তা বড় হয়ে cross হয়ে যায় তাহলে এর পরের value দিয়ে কাজ করার চেস্টা করতে থাকব । 

Code টা কিছুটা এমন

 আবারও বলে থাকা ভাল coin change এর জন্য greedy solution optimal না , optimal হল  dp   solution . কিন্তু  টাইম লিমিট অনেক সময় dp solution এর থেকে greedy solution      টাকেই optimal ধরে নেওয়া হয় । যদি এমন দেখা যায় coin গুলোকে ascending order এ সর্ট করার পর 2*coin[i] <= coin[i+1] তাহলে দেখা যাবে greedy solution best optimal result এই দিচ্ছি । 

Activity Selection Problem :

      Activity selection problem টা এমন আমাকে অনেক গুলা কাজ দেওয়া আছে । start time ও end time সহ । আমি একটা সময় শুধু মাত্র একটা কাজ এই করতে পারি । আমাকে যদি Nটা কাজ দেওয়া হয় তাহলে আমি সব চেয়ে বেশী  কয়টা কাজ করতে পারব । এইখানে overlapping possible না মানে একটা কাজ শেষ না করে কোন কাজ শুরু করতে পারব না  । এই প্রবলেম এর solutionটা অনেক সুন্দর । আমি কাজগুলাকে তাদের end time এর বেসিস এ sort করব । এর পর আমি যে কাজটা সবার আগে আসবে তা করব । এমন এর পর এ সেই কাজটা শুরু করব যার start time এই কাজের end time এর থেকে বেশী । 

Codeটা কিছুটা এমন
    

          এখন দেখা যাক এইভাবে করলে আমি কেন সব সময় বেস্ট Ans পাচ্ছি । আমি যদি end time  ধরে সর্ট করে
          কাজ স্টার্ট এর জন্য নেই আমি সবসময় সেইসব কাজ এই নিব যাদের end time অন্য কাজগুলা থেকে আগে      শেষ হচ্ছে   মানে আমি best option পাচ্ছি আরো বেশী কাজ স্টার্ট  করার ।

Active selection problem থেকে বুঝা যায় আসলে greedy কেন আসলে মাঝে মধ্যে dp থেকে ভাল ।  ধরুন আমার N টা কাজ এর লিস্ট আছে যাদের থেকে আমার বেস্ট লিস্ট করতে হবে যাতে আমি সবথেকে বেশী কাজ শেষ করতে পারি । DP এর জন্য আমার possible option 2^N . এখন N এর মান যদি অনেক বড় হয় তাহলে তা strict time limit জন্য খুব একটা ভাল উপায় না । আমি TLE খাব অনেক code এই । তাই মাঝে মধ্যে greedy is good .

Interval scheduling  problem :
 Interval scheduling ( Greedy ) problem এ আমাকে  অনেক গুলা কাজ এর start এবং end time দেওয়া হইছে । আমাকে প্রতিটা কাজ এর জন্য একটা  program assign করতে হবে । আমাকে বলতে হবে কিভাবে করলে সব থেকে কম  program assign করতে হবে । এইখানে overlapping possible না মানে একটা কাজ শেষ না করে কোন প্রোগ্রাম ফ্রী হবে না । মানে ৬ মিনিট এ যদি কোন কাজ শেষ হয় আর অন্য একটা কাজ ৬ মিনিট থেকে start হয় তাহলে ৬ মিনিট এর কাজ না শেষ করে যেহেতু অন্য কাজ শুরু করা যাবে না তাই এইখানে দুইটা প্রোগ্রাম লাগবে । আমি এইখানে sort করব । sort করার সময় end point , start point কে আলাদা ভাবে mark করব । start point priority পাবে মানে sorting এ সেম পয়েন্ট এ end , start থাকলে start আগে থাকবে । 

          

   কোডিং এ আমি চেক করব current position maximum কয়টা program স্টার্ট আছে , এইটাই আমার Ans . কারন এই সময় এই আমার সব থেকে প্রোগ্রাম রান করে রাখতে হবে । এর চেয়ে কম নিলেও আমার হবে না বেশী নিলে এক্সট্রা প্রোগ্রামগুলা বসে থাকবে ।

   Minimum Spanning Tree ( kruskal ) : 
  minimum spanning tree ও greedy problem এর জন্য ভাল উদারন । শাফায়াত ভাইয়া অনেক ভাল টিউটরিয়াল লিখছে kruskal . আশা রাখি এইখান থেকে একটু দেখলেই সবার clear হয়ে যাবে ।


কিভাবে আইডিয়া পাব এইটা greedy solution হতে পারে ?   যেকোন প্রবলেম এর solution idea পাবার পূর্বশর্ত হল এইরকম প্রবলেম অনেক সল্ভ করা । আমি যদি দেখি Ans গুলা current best option থেকে আসসে তাহলে আমি greedy solution এর কথা ভাবতে পারি । অনেক greedy problem এর সর্টিং , বাইনারি সার্চ এর দরকার হয় মানে সর্টিং , বাইনারি সার্চ করে বেস্ট পসিবল উত্তর পাওয়া যায় । এইসব ব্যাপার মাথায় রাখতে হবে । অনেক Dp প্রবলেম টাইম লিমিট এর মধ্যে করার জন্য code optimized করার প্রয়োজন হয় । তখন অনেক কেস greedy process থেকে বাদ দেওয়া হয় । তাছাড়া কোন প্রবলেম dp ,আর কোনটা  greedy তার মধ্যে difference করার জন্যও আমাদের greedy ভাবনা ভাবতে হবে । greedy মানে আমি নরমাল এই বেস্ট পসিবলের জন্য যা  চিন্তা করি ( human brain current stage থেকে একটা certain stage পর্যন্ত ভ্যালু ভাবতে পারে , তাই আমাদের চিন্তার ধরন greedy ) .  Uva আর Light Oj তে অনেক প্রবলেম আছে greedy এর জন্য । এইগুলা কিছু করলেই আরোও idea clear হবে সবার ।
problem
Uva Problem
Light Oj

সবাইকে অনেক শুভ কামনা :)
   
   

Editorial ( AUST ACM Practice Contest - 2 , 16/09/2014)

contest link ::: AUST ACM Practice Contest - 2

Problem A : 

এইখানে বলা হইছে  X = 0 ,  আমাকে বিভিন্ন pre or post increment or decrement operation দেওয়া হবে আমাকে শেষ X এর ভ্যালু বলতে হবে । এইখানে টেস্টকেস দেওয়া আছে , আমাকে ফাস্ট  এ টেস্ট কেস ইনপুট নিতে হবে তারপর একটা একটা করে srting input নিব এইখানে আমাদের খালি চেক করতে হবে কোন + sign আছে কিনা থাকলে ভ্যালু বাড়াব না হলে কমবে ।
পিয়াস এর কোড

Problem B : 

এইটাও অনেক সহজ প্রবলেম ।এইখানে বলা হইছে আমাকে একটা srting ইনপুট দিবে আমাকে বলতে হবে এইখানে কয়টা word আছে । এইখানে  আমাকে EOF পর্যন্ত ইনপুট নিতে হবে । তারপর আমাকে প্রতিটা ইনপুট এর জন্য Word count করে প্রিন্ট করতে হবে ।
say string inp ;
           getline( cin , inp ) ;
           int i , Ans = 0 , sz = inp.size() ; // string এর সাইজ দেয়
           for ( i = 0 ; i < sz ; i++ )
           {
                  if( i && !isalpha(inp[i]) && isalpha(inp[i-1]) Ans++ ; // এর মানে হইল এই লেটারটা কোন Alphabet না কিন্তু আগের লেটার টা ছিল মানে আমি একটা word পেয়েছি
           }
         print --- > Ans ; 

 Problem C :

  টেস্ট কেস এর প্রবলেম । এইখানে আমাকে একটা বৃত্ত এর ব্যাসার্ধ দিবে যা একটা চতুর্ভুজ এর ভিতর এর সব বাহুকে স্পর্শ করে যাছে আমাকে এর শেড করা জায়গার Area বলতে হবে । ফরমুলাটা হইল যদি  radius --> r then

area = ( 4 * r * r ) - 2 pi r * r ; // proof নিজে নিজে কর ।

Problem D : 

triangle print এর প্রবলেম । ১/১ এ ল্যাবে স্যার এর অনেক প্রিয় Assignment । এই প্রবলেম এ New লাইন এর অনেক প্রবলেম হয় । এইখানে এই ব্যাপারটা সবার খেয়াল করতে হবে ।
NOTE: There is a blank line after each separate waveform, excluding the last one.এর মানে হইল সব কেস এর পর আমি একটা extra new line print দিব কিন্তু লাস্ট কেস এ দিব না । এইটা আমাকে চেক রাখতে হবে ।
সিফাত এর কোড

Problem E : 

এইখানে আমাকে দুইটা নাম্বার দিবে n , m . আমাকে তারপর n টা সংখ্যা দিবে যাদের থেকে আমি m টা সংখ্যা নিব । কিন্তু এমন ভাবে এই m গুলার সংখ্যার মধ্যে maximum আর minimum এর difference হবে minimum .
sorting এর প্রবলেম । আমি nটা নাম্বার sort করব তারপর m টা number এর মধ্যে Ans বের করব।

        int n , m , i  ;

                  cin >> n >> m ;
                  for ( i = 0 ; i < n ; i++ )  cin >> Inp[i] ; // Inp --> Array globally declear
                  sort( Inp , Inp+n ) ; // sort ascending order
                  int Ans = Inp[m-1] - Inp[0] ; // initial value
                  for ( i = 1 ; i + m - 1 < n ; i++ )
                  if ( Inp[i+m-1] - Inp[i] < Ans ) // Value update
                  Ans = Inp[i+m-1] - Inp[i] ;
                  print --- > Ans ; 

 Problem F : 

এইটা DP এর basic state reduction problem । এইখানে চারটা নোড দেওয়া হইছে A , B , C , D . প্রাথমিক ভাবে পিপড়াটা আছে D তে । আমাকে একটা নাম্বার n দেওয়া হবে । আমাকে count করে বলতে হবে n length এর কয়টা cyclic path আছে । cyclic path মানে যেখানে ছিলাম আবার সেখানেই আসব । এইখানে D থেকে D তেই আসব কয়ভাবে ( কয়টা Unique path আছে ) । যেমন n== 2 হলে

1. D - A - D 
2. D - B - D 
3. D - C - D 

এমন ৩টা path আছে । এখন আসি space reduction dp কি ? Dp তে আসলে আমরা কি করি state by state value calculate করি । কোন state এর value তার আগের এক বা একাধিক state থেকে পাই । যদি এমন দেখা যায় একটা state এর ভাল্যু খালি তার আগের এক/দুই/তিন ( মানে fixed অল্প কিছু state ) এর উপর depend করে তাইলে আমি আগের state এর ভ্যালু বাদ দিতে পারি । এই প্রবলেম এর জন্য দেখি কিভাবে ? এইখানে ০ length এর খালি একটা cyclic path এই আছে ।

0 মানে পিপড়া D তে ছিল D তেই আছে । এখন যদি 1 length এর বের করতে চাই তাহলে কিভাবে  । আসলে 1 length এর cyclic path মানে o length এর A তে total cyclic path + 0 length এর B তে total cyclic path + 0 length এর C এর total cyclic path .
মানে আসলে এমন । 2 length এর calculation এর জন্য খালি 1 length এর state এর ভ্যালু দরকার আমার । তাই 2 length এর জন্য 0 length এর ভ্যালু আমার মেমু করে রাখার কোন দরকার নাই ।

dp[now][ node == D here  ]  = (  dp[prev][A] + dp[prev][B] + dp[prev][C] )  % Mod
এখন প্রতি state শেষ এ আমি now , prev এর ভ্যালু চেঞ্জ করব । এইটা কিভাবে কাজ করছে তা খাতা কলমে করে দেখ ।

    long long dp[4][2] ;
    dp[0][0] = dp[1][0] = dp[2][0] = 0 ;
    dp[3][0] = 1 ;
    int n , i ;
    cin >> n ;
    int now = 1 ;
    int prv = 0 ;
    for ( i = 1 ; i <=  n ; i++ )
    {
        dp[0][now] = (dp[1][prv] + dp[2][prv] + dp[3][prv] )%Mod ;
        dp[1][now] = (dp[0][prv] + dp[2][prv] + dp[3][prv] )%Mod ;
        dp[2][now] = (dp[0][prv] + dp[1][prv] + dp[3][prv] )%Mod ;
        dp[3][now] = (dp[0][prv] + dp[2][prv] + dp[1][prv] )%Mod ;
        swap(now,prv);
    }
    cout << dp[3][prv] << endl ;

 Problem G : 

এই প্রবলেমটা কিছুদিন আগেই CF এর কনটেস্ট এর ছিল । আমি প্রবলেমটা ভালমত না পড়ার কারনে মিস করে গেছিলাম ।এইটার Dp এবং Directed graph এর longest path দুইটাই solution আছে ।আমি গ্রাফ এর প্রসেসটা বলি ।  এইখানে আমাকে n length এর m সংখ্যক Array দেওয়া হইছে । আমাকে এই m Array এর মধ্যে longest common subsequence এর বলতে হবে । এইখানে সবচেয়ে Important point

                   " Each of them consists of numbers 1, 2, ..., n in some order."    

 এর মানে হইল n এর যে ভ্যালু থাকবে Array তে 1 - n পর্যন্তই থাকবে যেকোন order এ । এইখানে n এর লিমিট ১০০০ আমি যদি এখন এদের কে directed graph এ convert করতে পারি তাহলে আমার খালি longest path এর lengthটাই আমার উত্তর । ১০০০ যেহেতু লিমিট আমি খুব সহজেই n^2 , m <= 5  এর মধ্যে চেক করতে পারি দুইটা index i & j এর জন্য সব Array তেই i এর পর j আছে কিনা । যদি থাকে তাহলে i --> j path থাকবে । graph বানানো হইলে আমাকে জাস্ট বের করতে  হবে maximum length এর path যেইটা Dfs দিয়ে সবাই পারবে আশা রাখি । 

const int MX = 1005 ;
vector < int > G[MX] ;
int pos[10][MX] , Best[MX] , Inp[10][MX];
int N , K ;
bool used[MX];
int Ans ;
void Dfs(int node)
{
    used[node] = 1 ;
   // Best[node] = 1 ;
    int sz = G[node].size();
    int i ;
    for ( i = 0 ; i < sz ; i++ )
    {
        int u = G[node][i];
        if( !used[u] )  // already visited
        Dfs(u);
        Best[node] = max( Best[node] , Best[u] + 1 ) ;
    }
    Best[node] = max(Best[node] , 1 );
    Ans = max( Ans , Best[node]);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int i , j , k , n ;
    cin >> N >> K ;
    for ( i = 1 ; i <= K ; i++ )
    {
        for ( j = 0 ; j < N ; j++ )
        {
            cin >> Inp[i][j] ;
            pos[i][Inp[i][j]] = j+1 ;
        }
    }
     bool thik ;
    // now graph construct
    for ( i = 1 ; i <= N ; i++ )
    {
        for ( j = 1 ; j <= N ; j++ )
        {
            if ( i == j ) continue ;// no self loop possible
            // now we check if its possible to have a edge for i to j
            // its only possible if j is after i in every set
         thik= 1 ;
            for ( k = 1 ; k <= K && thik ; k++ )
            {
                if ( pos[k][j] <= pos[k][i] )
                thik = 0 ; // not possible t
            }
            if ( thik ) G[i].pb(j);
        }
    }
    Ans = 0 ;
    for ( i = 1 ; i <= N ; i++ )
    {
        if( !used[i] ) Dfs(i);
    }
    cout << Ans << endl ;

Problem H : 

এইটা Interval scheduling ( Greedy ) problem . এইখানে অনেক গুলা কাজ এর start এবং end time দেওয়া হইছে । আমাকে প্রতিটা কাজ এর জন্য একটা wrapper program assign করতে হবে । আমাকে বলতে হবে কিভাবে করলে সব থেকে কম wrapper program assign করতে হবে । এইখানে overlapping possible না মানে একটা কাজ শেষ না করে কোন প্রোগ্রাম ফ্রী হবে না । মানে ৬ মিনিট এ যদি কোন কাজ শেষ হয় আর অন্য একটা কাজ ৬ মিনিট থেকে start হয় তাহলে ৬ মিনিট এর কাজ না শেষ করে যেহেতু অন্য কাজ শুরু করা যাবে না তাই এইখানে দুইটা প্রোগ্রাম লাগবে । আমি এইখানে sort করব । sort করার সময় end point , start point কে আলাদা ভাবে mark করব । start point priority পাবে মানে sorting এ সেম পয়েন্ট এ end , start থাকলে start আগে থাকবে । 

          struct abc
                    {
                            int value , mark ; // mark 0 for start point , 1 for end
                    } Inp [ Mx + Mx ] ;
                     bool cmp ( abc A  , abc B )
                     {
                              if ( A.value == B.value ) return A.mark < B.mark ;  // start mark age thakbe
                              return A.value < B.value ;
                     }

                   int main()
                  {
                           int n , i  , x , y , idx = 0;
                          cin >> n ;
                         for ( i = 0 ; i < n ; i++ )
                        {
                                 cin >> x >> y ;
                                 Inp[idx].value = x ;
                                 Inp[idx++].mark = 0 ;
                                 Inp[idx].value = y ;
                                 Inp[idx++].mark = 1 ;
                        }
                      sort(Inp , Inp+idx , cmp );
                     int Ans = -Inf ;
                    int cur = 0 ; // eita count korbe koyta program ekhon run korche
                    for ( i = 0 ; i < idx ; i++ )
                    {
                                  if( Inp[i].mark == 0 ) // mane notun program start hoiche
                                   cur++;
                                   else cur-- ; // program off hoiche
                                  Ans = max(Ans , cur );
                    }
                   print -- > Ans ;
                   return 0 ;

               }

   কোডিং এ আমি চেক করব current position maximum কয়টা program স্টার্ট আছে , এইটাই আমার Ans .

যে যে প্রবলেম সল্ভ করা যায়নি কনটেস্ট টাইমে তা upsolving ( কনটেস্ট এর পর সল্ভ ) করতে হবে ।  না হলে আসলে কিছুই শিখা হবে না । সবার জন্য শুভ কামনা :)

                   

               

       

       

             

২ স্যাট

[ বিদ্র :  এই গল্পের  সব চরিত্রই কাল্পনিক বাস্তব জীবনের সাথে মিল নাই ]                                                                                                                      

 [ সংবিধকরণ সতর্কীকরণ :  অতিরিক্ত সিরিয়াসনেস প্রোগ্রামিং লাইফের জন্য ক্ষতিকারক ]  

সময়কাল ২০৩০ ।  আমাদের ম্যাল্টি বিলিওনিয়ার রাফি ভাইয়া অবশেষে বিবাহ এর সিন্ধান্ত নিয়েছেন । টাকা-পয়সা , ক্যারিয়ার অনেক দেখা হইছে এখন ঘরকান্না করা দরকার ।  প্রোগ্রামিং এ তুখড় ভার্সিটি লাইফে রাফি ভাইয়ার এর পিছনে কম রমণীর লাইন ছিল না । কিন্তু ক্যারিয়ার সচেতন  ভাইয়া  কখনই ঘরের পানি ঘোলা করতে দেন নাই ( এমনেই এখন ঢাকা শহরের বেশিরভাগ  ট্যাংকের পানি ঘোলা হইয়া গেছে :( )  ভাইয়া এই প্রোগ্রামটা কিভাবে করব ? ভাইয়া এইটা বুঝতেছি না ? ভাইয়া এইখানে জিলাপির প্যাচ লাগছে ছাড়াইয়া দেন :( এরকম কত নাম না জানা , প্রকাশিত এবং অপ্রকাশিত , হাজার রকমের ইমো যুক্ত কত ফেসবুক ম্যাসেজ আসত তার হিসাব নাই । কিন্তু আমাদের বেরসিক রাফি ভাইয়ার এক রিপ্লাই "www.google.com" :(   প্রগ্রামার না  বুঝে নারীর মনের ইঙ্গিত , আফসোস । কি আর করা সময় , নদীর স্রোত এবং নারি কখনই কারো জন্য অপেক্ষা করে না । ভার্সিটি লাইফের নাম না জানা হাজারও ইনা , বিনা , টিনা এখন বিবাহ করে বাচ্চাকাচ্চা সহ সুখে শান্তিতে আছে । যদিও সেই ২৮ ইঞ্চির পেট এখন সাড়ে ৪৪ ইঞ্চি হইছে কিন্তু রাফি ভাইয়ার চ্যারম এখনও তেমন কমে নাই ;) । বিবাহের মার্কেটের  রাফি ভাইয়ার সিন্ধান্ত লিক  হইতে না হইতেই চারিদিক দিয়ে ভাইয়ার জন্য পাত্রীর লাইন লাইগা গেল । আমরাও পড়লাম  মহাবিপদে , কিন্তু ভাইয়ার এত এত awesome পিচ্চি ভাই থাকতে এইটা কোন প্রবলেম :P আমরা অনেক কষ্টে চার জনের সর্ট লিস্ট করলাম । 

(১) নায়লা নাইম (২) সাফা কবির   (৩) মাহি  (৪) ববি 

ভাইয়া আবার চার জনকেই সমান পছন্দ করেন , কাউকেই কম বেশি না :( আর ভাইয়া অনেক ভাল মানুষ এবং ভাল  মানুষের জন্ম , বিবাহ , মৃত্যু একবারই হয় তাই ভাইয়াও চান না পরিবারে কাউকে কষ্ট  দিতে । ভাইয়ার পাত্রী নিয়ে বাবা , মা , ভাইয়া ( ভাইয়ার ভাইয়া ) , আপুর সবারই নিজের কিছু চাওয়া পাওয়া আছে । ব্যাপারটা কিছুটা এমন                           

বাবা চান মাহি এবং নায়লা নাইম কেউই বউ না হোক।                                                                                                   মা চান সাফা কবির বা  মাহি  হোক।                                                 

ভাইয়া চান নায়লা নাইম হোক কিন্তু ববি না হোক ।

আপু চান ববি এবং  নায়লা নাইম  কেউই না হোক ।                                                                                                                                                                                

ব্যাপারটা কিছুটা এমন সবার একটা করে সিন্ধান্ত রাখা হইলেই তারা খুশী থাকে কিন্তু একটাও যদি কোন না রাখা না হয় তাহলে তারা অনেক কষ্ট পাবেন । এবং ভাইয়াও চান সবাইকে খুশী রাখতে । যদি আমরা সবাইকে খুশী রাখতে চাই তাহলে সবার চাহিদাকে এমন একটা boolean expression এ প্রকাশ করতে পারি                                                                 

( মাহি বউ হবে না || নায়লা নাইম হবে না ) && ( সাফা কবির হবে ||  মাহি হবে  ) && ( নায়লা নাইম হবে || ববি হবে না ) && ( ববি হবে না || নায়লা নাইম ও হবে না )                                                                                                                                                                                                                                       

যদি উপরের expression টার ভ্যালু আমরা ট্রু দেখাতে পারি তাহলে আমরা বলতে পারব যে এমন কোন ব্যাবস্থা আছে যেখানে সবাই খুশী থাকে । এইরকম ভাবে কোন প্রবলেমকে আমরা কোন boolean expression এ প্রকাশ করতে পারলে এই টাইপের প্রবলেমগুলা  ২ সেট আল্গরিথম দিয়ে খুব সহজেই সমাধান করা যায় । এইখানে আমরা এই ২ স্যাট আল্গরিথম এর কাজ এই দেখব । 

২ স্যাট  : 

তত্ত্বীয় সংজ্ঞায় আসি , ২ স্যাট হইল প্রতিটা ভ্যারিয়্যাবলের ( এইখানে কোন এক পাত্রী বউ হবে কি হবে না তাই ভ্যারিয়বল ) একটা ভ্যালু সেট যাতে পুরা এক্সপ্রেশনটা ট্রু হয় । এইখানে কতগুলা ব্যাপার খেয়াল করি , 

১) যদি ফাইনাল সেট এ কোন ভ্যারিয়েবল X = true  হয় তাহলে notX = true ও হবে , ধরি এইখানে  X = মাহি বউ হবে তাহলে notX = মাহি বউ হবে না  । মানে এইখানে যদি ফাইনাল ট্রু এক্সপ্রেশন এ দেখা যায় মাহি বউ হবে = ট্রু তাহলে সেট এ মাহি বউ হবে না ওই ভ্যারিয়বলটাও  = ট্রু  হবে । যদি এমন না হয় তাহলে কখনই এক্সপ্রেশন এর ভ্যালু ট্রু পাওয়া যাবে না । এইটা থেকে আমরা আবার আরো একটা ব্যাপারে নিশ্চিত হইতে পারি । যদি variable থাকে Nটা ( এইখানে পাত্রীর সংখ্যা )  তাহলে  2N সংখ্যক নোড থাকবে এক্সপ্রেশন এ । 

২) আমি প্রতিটা নোডকে যদি একটা directed graph এ represent করতে পারি এবং তাতে যদি SCC ( strongly connected component )  বের করি তাহলে প্রতিটা সেট এর ( এইখানে বাবা , মা , ভাইয়া , আপুর ইচ্ছাগুলা একটা সেট ) এইখানে যেহেতু সবারই একটা না একটা ইচ্ছা পূরণ হইতেও হবে তাহলে আমরা এক্সপ্রেশনটাকে এইভাবেও দেখতে পারি । যেমন বাবার ইচ্ছা হইল "  মাহি এবং নায়লা নাইম কেউই বউ না হোক  ( মানে এর দুইটার একটা অত্যন্ত সত্য হোক ) " এখন একটু ব্যাপারটা খেয়াল করলেই ক্লিয়ার হয়ে যাবে ,              

*******যদি কোন ভাবে মাহি বউ হয়ে যায় তাহলে বাবার ইচ্ছা পূরণ করার জন্য নায়লা নাইম অবশ্যই বউ হইতে পারবে না ( আসলে এইখানে ইলেকশন এর ব্যাপারটা দিলে বুঝতে সুবিধা হইত , বউ তো একজন এই হয় এইটা নিয়া কেউ কনফিউজ থাইকেন না , ২Set all possible true expression এর ভ্যালু দেয় মানে একাধিক বউ হইলেও দেখা যাইতে পারে expression true আছে )                                                                                                                                                                                                                                                                                                                                                                                                ******* যদি কোনভাবে নায়লা নাইম বউ হয়ে যায় তাহলে বাবা চান কখনই মাহি বউ হবে না ।                                                                                                           

ধরে নেই   X = মাহি বউ হবে না , Y = নায়লা নাইম বউ হবে না  । এখন যেহেতু একটা একটা সত্য থাকবেই তাই SCC তে মাহি বউ হবে না ( X )  এবং নায়লা নাইম বউ হবে ( !Y ) একই সেট এর হবে  । আর একটা ব্যাপার SCC তে কখনই X এবং !X node এক color এর হইতে পারে না , যদি হয় তাহলে এক্সপ্রেশন এর ভ্যালু কখনও ট্রু হবে না । এইগুলা গেল তত্ত্বীয় ব্যাপার এখন আমরা কোড দেখতে পারি , আসলে কি করতে হবে এবং কিভাবে কাজ করে । 

কোড :                

   (১) ২ সেট এ আমাদের সবার প্রথমে প্রতিটা পারশন এর জন্য তাদের চাহিদার সেট গুলার varibale কে আমাদের directed graph এর কনভার্ট করতে হবে । 

যেমন এইখানে বাবা চান 

মাহি এবং নায়লা নাইম কেউই বউ না হোক 

এর মানে হইল যদি কোন ভাবে মাহি বউ হয় তাহলে নায়লা নাইম বউ হবে না , আর কোন ভাবে যদি নায়লা নাইম বউ হয় তাহলে অবশ্যই মাহি হবে না । 

মানে সোজা কথা 

মাহি বউ - > নায়লা নাইম বউ না 

নায়লা নাইম বউ -> মাহি বউ না । 

এখন বুঝার সুবিধার জন্য আমরা সবগুলা varibale কে numbering করে ফেলি 

ধরি এইখানে , 

নায়লা নাইম বউ -> ০ নাম্বার  নোড 

নায়লা নাইল বউ না -> ১ নাম্বার নোড 

সাফা কবির বউ -> ২ নাম্বার নোড 

সাফা কবির বউ না -> ৩ নাম্বার নোড 

মাহি বউ -> ৪ নাম্বার নোড 

মাহি বউ না -> ৫ নাম্বার নোড 

ববি বউ -> ৬ নাম্বার নোড 

ববি বউ না -> ৭ নাম্বার নোড 

তাহলে বাবার জন্য এইরকম হবে 

বাবা চান মাহি এবং নায়লা নাইম কেউই বউ না হোক 

মানে এইখানে, 

 ৪ - > ১

০ - > ৫ 

এর মধ্য কানেকশন আছে । 

মা এর জন্য হবে 

মা চান সাফা কবির বা  মাহি  হোক 

মানে এইখানে 

২ -> ৫ 

৪ -> ৩ 

এর মধ্য কানেকশন আছে । 

ভাইয়ার জন্য হবে 

ভাইয়া চান নায়লা নাইম হোক কিন্তু ববি না হোক 

মানে এইখানে 

১ -> ৭ ( নায়লা নাইম না হলে ববি অবশ্যই বউ হবে না ) 

৬ -> ০ ( যদি ববি বউ হয়ে যায় অবশ্যই নায়লা নাইম হবে ) 

আপুর জন্য হবে 

আপু চান ববি এবং  নায়লা নাইম  কেউই না হোক । 

মানে এইখানে 

৬ -> ১ ( ববি হয়ে গেলে নায়লা নাইম হবে না ) 

০ -> ৭ ( নায়লা নাইম হয়ে গেলে ববি হবে না )                                                                                                                                                                                          

(২) এখন আমাদের দ্বিতীয় কাজ হইল SCC বের করা এই গ্রাফ এর ।                                                                                                                                     

উপরোক্ত গ্রাফে যদি এখন আমি topological সর্ট চালাই তাহলে order পাব ( হাতে করে দেখতেই পারি ) ৬ ৪ ৩ ২ ১ ০ ৭ ৬ ৫ এর পর যদি SCC color করি । দেখা যাবে যে সব নোড এইখানে আলাদা আলাদা color হয়েছে ।                                                                                                                                                                     

৬ ->  ১ নাম্বার  কালার                                                                                                                                                                                           

৪ ->  ২                                                                                                                                                                                                     

৩ - > ৩                                                                                                                                                                                                          

২ -> ৪ 

১ -> ৫ 

০ -> ৬ 

৭ -> ৭ 

৫ -> ৮ 

(৩) এখন চেক করার two সেট হবে কিনা  simple একটা for loop চালাইয়া এই চেকটা আমি করতে পারি । 

আমি দেখব যে কোন varibale X এর কালার ১ হলে notX এর কালার কি , যদি কোনটাতে same পাওয়া যায় তাহলে এইখানে two sat possible না । 

(৪) এখন হল প্রিন্ট এর কাজ আমি এখন চেক করব কোন নোড x আমাদের Ans হবে যদি  X কালার > notX এর কালার হয়। মানে এইখানে নায়লা নাইম বউ হবে যদি ( color of nayla Nayim > color of not  Nayla Nayim after SCC ) উপরের কোড এ তাই আমরা দেখব নায়লা নাইম বা সাফা কবির যে কাউকেই রাফি ভাইয়া যদি বিয়ে করেন তাহলে পরিবারের সবাই খুশী থাকে । 

আমি আসলে যা জানি তা লিখার চেস্টা করলাম , আমি খুবই বাজে কোডার অবশ্যই ৯৯% কেউই কিছু বুঝে নাই :P এখন গুগল করে সবাইকে বুঝতে হবে ।  যাই হোক , কোড maxima তে থাকার কারনে দিলাম না ।  

লিঙ্ক : http://e-maxx.ru/algo/2_sat

বুঝা হয়ে গেলে Loj   এর ১২৫১ করা যাবে :)