Bappy's Blog

প্রব্লেমটি  Green Hackenbush  এর সুন্দর একটি প্রব্লেম। প্রব্লেম পড়ে থাকলে এবং Green Hackenbush বুঝে থাকলে, এটুকু নিশ্চয়ই বুঝেছো যে ১ একক দৈর্ঘ্যের এজ গুলো নিয়ে কোন সমস্যা নেই। বিপত্তি শুরু হয় যখন এজ এর দৈর্ঘ্য ১ এর বেশি হয়।  কয়েকটি কেস এনালাইসিস করলে বুঝবে যে যেসব এজ এর দৈর্ঘ্য এক এর বেশি তারা একটি লুপ এর মতো কাজ করে। অর্থাৎ, x>1 দৈর্ঘ্যের একটি এজকে আমি x সংখ্যক একক দৈর্ঘ্যের এজ দ্বারা রিপ্লেস করতে পারি।  এখন, একটি এজ [u,v] এর জন্য হিসেবটা কেমন হবে?  ১) যদি এজটির কস্ট = ১ হয়, তাহলে value[u] ^= (1 + value[v]) ২) অন্যথায়,           i) কস্ট যদি বিজোড় হয়, তাহলে value[u] ^= (1 ^ value[v])        (Think about it by pen & papper)          ii) কস্ট যদি জোড় হয়, তাহলে value[u] ^= value[v] আশা করি এখন প্রব্লেমটি তোমার কাছে একটি স্ট্রেইট ফরোয়ার্ড প্রবেলেমে রূপান্তরিত হয়েছে। তাও না পারলে সলুশন দেখতে পারো। 

এই পর্বটি পড়ার আগে ব্যাসিক গেম থিওরি শিখা জরুরী। ব্যাসিক গেম থিওরি শিখতে নিচের পর্বগুলো পড়তে হবে। পর্ব-০১ পর্ব-০২ পর্ব-০৩ মনে করি, আমাকে অনেকগুলো বাঁশ গাছ দেয়া আছে। প্রতিটি গাছের উচ্চতা h[i] একক। এখন, দুইজন প্লেয়ার যেকোন একটি বাঁশ গাছের যেকোন জায়গায় কাটতে পারবে। যে প্লেয়ার শেষ গাছের শেষ এজটি কাটবে সে জিতবে।  ৩য় গাছের ১ম এজ কাটলে উপরে দুইটি এজ সম্পূর্ণ অক্ষত থাকলেও পরবর্তীতে ওই এজগুলো আর কাটা যাবে না। কারণ সেটি গাছের মূল থেকে বিচ্ছিন্ন!  একটু ভালো করে লক্ষ করলে দেখবে এটি সিম্পল একটি নিম এর প্রব্লেম। নিমে যেরকম অনেকগুলো পাথরের স্তুপ দেয়া আছে। প্রতি চালে একজন প্লেয়ার যেকোন স্তুপ থেকে যেকোন সংখ্যক পাথর উঠাতে পারে।  তাহলে, এই প্রব্লেমের সমাধানও একই। প্রতিটি বাঁশ গাছের উচ্চতার এক্সর করতে হবে। এক্সর = ০ হলে, ২য় প্লেয়ার জিতবে। অন্যথায়, প্রথম প্লেয়ার জিতবে। এখন বিপত্তি বাধবে যদি গাছগুলো বাঁশগাছ না হয়😜 নিচের ছবিটি লক্ষ কর। এরকম হলে প্রব্লেমটির সলুশন কেমন হবে?  এই ক্ষেত্রে, আমরা Colon Principle ব্যাবহার করে প্রব্লেমটিকে আবারও নিম প্রব্লেমে কনভার্ট করতে পারি।  Colon Princi...

Problem Description  here প্রবলেমঃ প্রব্লেমটিতে মূলত বলা হয়েছে একটি r * c গ্রীড দেয়া থাকবে। গ্রীডের প্রতিটি সেলে কিছু কয়েন থাকবে। দুইজন প্লেয়ার অপটিমালি খেলবে। প্রতি টার্নে একজন প্লেয়ার এক বা একাধিক কয়েন নিবে একটি সেল থেকে। নিয়ে ঠিক তার নিচের অথবা ডানের সেলে রাখবে। যখন সবগুলো কয়েন grid[r][c] তে পৌছাবে তখন খেলা শেষ। শেষ মুভ যে প্লেয়ার দিবে সে জিতবে। বলতে হবে প্রথম প্লেয়ার জিতেছে নাকি হেরেছে।  আইডিয়াঃ এটি মূলত একটি নিম গেইম। এখন, আমরা প্রব্লেমটিকে নিম্বল গেইমে রূপান্তর এর চেষ্টা করবো। নিম্বল গেইম সম্পর্কে না জানলে  ক্লিক করুন । নিম্বল গেইমে একটি 1*n গ্রীডের প্রতিটি সেলে কিছু কয়েন থাকে। সেল গুলোর ইনডেক্স যদি 0 to n-1 হয় তবে প্রতি চালে যেকোন ঘর থেকে একটি কয়েন নিয়ে বামের যেকোন ঘরে রাখা যায় যতোক্ষণ না সবগুলো কয়েন সর্ববামের ঘরে চলে যায়।  এই প্রব্লেমে আমি  (i,j) সেল থেকে ডেস্টিনেশন সেল (r,c) তে যেতে পারি (r-i)+(c-j) সংখ্যক মুভ দিয়ে। খেয়াল করলে বুঝবে যে এই প্রব্লেমে আমি কয়েন এক বা একাধিক নিতে পারি আর মুভ এক ঘর ই দিতে পারি এক টার্নে। নিম্বল গেইমের ঠিক উল্টো! ওখানে ছিলো ক...