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

-

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

Comments

Post a Comment

Popular posts from this blog

Simple Pyramid(Progক্রিয়া কনটেস্ট)

-
Image
গতকাল 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. ছবিটিতে লক্ষ্য করে দেখতে পাবে, এখানে ৪টি ত্রিভুজ আছে। যতগুলো কো-অর্ডিনেট দেওয়া থাকবে, ঠিক ততগুলো ত্রিভুজ হবে। এখন
Read more
-
/*   Shahadat Hossain   I.C.T Department   Comilla University   Session: 2013-2014   .   Problem Site: LightOj   Problem No: 1174   Problem Name: Commandos  Using BFS   */ #include <cstdio> #include <sstream> #include <cstdlib> #include <cctype> #include <cmath> #include <algorithm> #include <set> #include <queue> #include <stack> #include <list> #include <iostream> #include <fstream> #include <numeric> #include <string> #include <vector> #include <cstring> #include <map> #include <iterator> #define valid(x,y) x>= 0 && y>= 0 && x<row && y<col int fx[]= { 1 ,- 1 , 0 , 0 }; int fy[]={ 0 , 0 , 1 ,- 1 }; #define pb push_back #define mp make_pair #define fs first #define se second #define pi 2 *acos( 0 ) #define PI 3.14159265358979323846264338 #define mod
Read more
-
OVISLARSUM - Large Sum Editorial of Problem C- Large Sum Topics: Big Multiple, Modular Inverse আপনার যদি এই টপিকসদ্বয় জানা থাকে, তাহলে editorial টা দেখতে পারেন। আমাদের মূলত ২টা কাজ, b পর্যন্ত যোগফল বের করা, a-1 পর্যন্ত যোগফল বের করা, তারপর subtract করে দেওয়া। আর মাঝখানে কিছু মড্যুলাস করতে হবে। তাহলে আমরা b পর্যন্ত যোগফল বের করা শুরু করি। ধরেন, আপনাকে 37 পর্যন্ত যোগফল করতে হবে, কিন্তু mod দেওয়া আছে 5. তাহলে আমার প্যাটার্ন টা এরকম হবে, ধরেন, আপনাকে 37 পর্যন্ত যোগফল করতে হবে, কিন্তু mod দেওয়া আছে 5. তাহলে আমার প্যাটার্ন টা এরকম হবে, 1 %5 = 1 2 %5 = 2 3 %5 = 3 4 %5 = 4 5 %5 = 0 6 %5 = 1 7 %5 = 2 8 %5 = 3 9 %5 = 4 10 %5 = 0 . . 31 %5 = 1 32 %5 = 2 33 %5 = 3 34 %5 = 4 35 %5 = 0 . 36 %5 = 1 37 %5 = 2 .এখানে একটা প্যাটার্ন আসতেছে 1 + 2 +3 +4 +0 1 + 2 +3 +4 +0 1 + 2 +3 +4 +0 1 + 2 +3 +4 +0 1 + 2 +3 +4 +0 1 + 2 +3 +4 +0 1 + 2 +3 +4 +0 1+2 এখন আমি যদি 37 কে 5 দিয়ে ভাগ দেই, তাহলে পাব 7, মানে এই প্যাটার্ন টা 7 বার আসবে। প্রত্যেক টা প্যটা
Read more