Identical Trees with hashing

-

Problem:

এই প্রব্লেমে আমাদেরকে দুটি রুটেড ট্রি ইনপুট হিসেবে দেয়া থাকবে। বলতে হবে, ট্রি দুটি Identical(একই) কি না? অর্থাৎ, রুট ফিক্সড রেখে একই নোডের Child নোডগুলোর সাবট্রি এদিক সেদিক করার পর ট্রি দুটি দেখতে একই হবে কি না। 


Solution:

Comments

Post a Comment

Trending Post

At Coder Educational DP-A | DP Series(Episode-1)

-
কিছু কথাঃ DP Series এ আমি মূলত  At Coder Educational DP  কন্টেস্টের প্রব্লেমগুলো নিয়ে আলোচনা করবো এবং সেই সাথে ডিপি সল্যুশন প্রিন্ট, ডিপি অপটিমাইজেশনসহ আরো কিছু বিষয় নিয়ে আলোচনা করবো।  এই সিরিজ টি পড়া শুরু করার আগে সবার ব্যাসিক ডিপি সম্পর্কে ধারণা থাকা আবশ্যক।  এজন্য  শাফায়েতের ব্লগ  থেকে ডাইনামিক প্রোগ্রামিং এর সবগুলো পর্ব পড়ে নেয়ার জন্য অনুরোধ করছি।  Problem Description  here Problem: প্রব্লেমটিতে বলা হয়েছে, আমাদেরকে n টি পাথর দেয়া থাকবে। এবং প্রতিটি পাথরের উচ্চতা দেয়া থাকবে।  একটি ব্যাঙ শুরুতে ১নম্বর পাথরে আছে। ব্যাঙ টি একঘর অথবা দুইঘর জাম্প করতে পারে। অর্থাৎ, i তম পাথর থেকে i+1 or i+2 তম পাথরে যেতে পারে। ith থেকে jth পাথরে যেতে তাকে দুইটি স্টোনের উচ্চতার পার্থক্যের সমান টাকা খরচ করতে হয়।  বের করতে হবে n তম পাথরে পৌঁছাতে তাকে সর্বনিম্ন কত খরচ করতে হবে?  Recursive Solution: ১) এই প্রব্লেমের জন্য আমাদের কয়টি স্টেট লাগবে? ভালোভাবে লক্ষ্য করলে বুঝবে শুধুমাত্র পজিশন ই স্টেট হিসেবে রাখা যথেষ্ট।  ২) এরপর, প্রতি পজিশন থেকে আমি একবা...
Read more

Light OJ - 1013 Love Calculator - Tutorial

-
There're two segments in the solution of this problem. 1. To calculate the length of the shortest string you have to calculate the LCS of two given strings. 2. To calculate the total number of unique strings, you've to follow several steps. i. First of all, it'll be a three states DP. State-1 for the current position of the generating string. State-2 for the current position of the given string-1. State-3 for the current position of the given string-2. ii. If(s1[pos1] == s2[pos2]) then you've to take one way Funtion(pos+1,pos1+1,pos2+1) iii. If(s1[pos1] != s2[pos2]) then you've to take possible two way Funtion(pos+1,pos1+1,pos2)+Function(pos+1,pos1,pos2+1). iv. Now, If any of the given string is completely taken, then you've to add the remaining characters of the other string manually. Check, is the current length of generating string is equal to the previously calculated unique string length or not? If yes, that means you've successfully g...
Read more