War with Code

F. Xor-Paths যারা যারা DFS পারো, ব্রুট ফোর্স দিয়ে সহজেই সলভ করে ফেলো, কিন্তু সাবমিট দিও না। আগে জিনিসটা বুঝো, কিভাবে রিকার্সিভলি প্রবলেমটা কাজ করছে। আমি এখনও রিকার্সিভ ততটা ভালো বুঝি না। কিন্তু যখনই রিকার্সিভের প্রয়োজন হয়, খাতা কলম নিয়ে বসি। এতটুকু তো জানি, ফাংশনগুলো স্ট্যাক ওয়াইজ সাজানো থাকে, একটা অন্যটাকে কল করতে থাকে। কিন্তু কোন এক জায়গায় গিয়ে আর কাউকে ডাকাডাকি না করে নিজেই ভ্যানিশ হয়ে যাবে। যখনও একটা ফাংশনের কাজ শেষ হয়ে যায়, তখনই এটা ভ্যানিশ, প্রয়োজনে কিছু ভ্যালু আগের ফাংশনে পাঠিয়ে দেয়। এবার প্রবলেমের কথা বলি, এটা সাবমিট দিতে হলে আরেকটু জিনিস শিখতে হবে, এটাকে বলে Meet in the middle. এটা বোঝার জন্য লিংক, . মানে কোন একটা সল্যুশনকে দুইভাগে বিভক্ত করা যাতে টাইম কমপ্লেক্সিটি অর্ধেক কমিয়ে আনা যায়। এখানে আমরা প্রথম দিক থেকে পথ চলা শুরু করব, তেমনি শেষ দিক থেকেও উল্টা পথ চলা শুরু করব। মাঝখানে যখন দুইজনের সাথে দেখা হয়ে যাবে, তখন হিসাব নিকাশ করে নিব। হিন্টসঃ- টোটাল পথ চলা হবে n+m-2 বার। তাহলে দুইজন দুইদিকথেকে এর অর্ধেক পথ চললেই দুইজনের দেখা পেয়ে যাবে। আর বাকি জিনিসটা নিজে নিজে শিখে ন

গতকাল Progক্রিয়া কনটেস্টে Simple Pyramid নামে একটি প্রবলেম ছিল। জিওম্যাট্রিতে এমনিতেই দুর্বল, প্রবলেম দেখার পরেই বুঝতে পেরেছি, এটা আমাকে দিয়ে হবে না। অতঃপর ঘাটাঘাটি করে যা শিখলাম। প্রবলেমটিতে চেয়েছিল,  ১- পিরামিডের আয়তন(volume)  ২- ঢালগুলোর ক্ষেত্রফল(slanted surface area) শুধু slopping area, base area দরকার নেই। ১ম ধাপ, পিরামিডের আয়তন(volume) নির্ণয়ের সূত্র,   = 1/3 × [Base Area] × Height এখানে উচ্চতা দেওয়া আছে, আমাদের শুধু ভূমির ক্ষেত্রফল(base area) বের করতে হবে। Sholelace formula ব্যবহার করে খুব সহজেই পলিগনের ক্ষেত্রফল বের করা যায়, তবে শর্ত হচ্ছে কো-অর্ডিনেটগুলো ক্লকওয়াইজ অথবা কাউন্টার ক্লকওয়াইজে সাজানো থাকতে হবে। ২য় ছবিটি দেখলে সহজেই বুঝতে পারবে। ২য় ধাপ, ঢালগুলোর ক্ষেত্রফল(slopping surface area) মানে সম্পূর্ণ পিরামিডে slopping area কতটুকু আছে, শেষের ছবিটিতে দেখলে খুব সহজেই বুঝা যায়, যতগুলো ত্রিভুজ আছে, ঠিক তাদের সম্মিলিত ক্ষেত্রফল ই slopping area. ছবিটিতে লক্ষ্য করে দেখতে পাবে, এখানে ৪টি ত্রিভুজ আছে। যতগুলো কো-অর্ডিনেট দেওয়া থাকবে, ঠিক ততগুলো ত্রিভুজ হবে। এখন