Codeforces Round #498 (Div. 3) F. Xor-Paths

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