Toph - See you again? Tutorial

 Problem Description here

এই প্রব্লেমটি আমার তৈরী করা একটি প্রব্লেম যেটি মূলত Intra CoU Programming Contest 2020 এর জন্য সেট করা। 

প্রব্লেমঃ প্রব্লেমটিতে বলা হয়েছে একটি n সাইজের ট্রি দেয়া থাকবে। যার প্রতিটি নোডে কিছু ক্যারেক্টার থাকবে। ট্রি এর রুট নোড হচ্ছে ১। বলতে হবে, এই ট্রি এর রুট থেকে লিফ পর্যন্ত এমন কোন পাথ আছে কি না যে পাথ "tareq&shawon" এই স্ট্রিং টা কে সাবসিকুয়েন্স হিসেবে ধারণ করে। যদি এমন পাথ থাকে তবে Lexicographically Smallest পাথটি প্রিন্ট করতে হবে। 

সল্যুশনঃ এই প্রব্লেমটির একটি ডিপি সল্যুশন সম্ভব। 

১) যেহেতু, Lexicographically Smallest পাথ বের করতে হবে তাই শুরুতেই প্রতিটি নোড এর জন্য তার এডজাসেন্সি লিস্ট টি Sort করে নিবো। 

২) ডিপি অ্যারের কাজ হবে প্রতিটি নোড থেকে লিফের দিকে যতোগুলো পাথ গেছে তাদের কোন একটি পাথ ধরে এখন পর্যন্ত স্ট্রিং এর যে ক্যারেক্টারগুলো সাবসিকুয়েন্স হিসেবে পেয়েছি সেগুলো ছাড়া বাকি সাফিক্সটুকু সাবসিকুয়েন্স হিসেবে পাওয়া যায় কি না সেটি ক্যালকুলেট করা। 

৩) এরপর, ডিপি অ্যারে ব্যাবহার করে ডিপি সল্যুশন প্রিন্ট করলেই কাজ শেষ! 

এরপরও না পারলে নিচের কোড দেখতে পারোঃ 

	#include<bits/stdc++.h>
	using namespace std;
	#define Input freopen("in.txt","r",stdin)
	#define Output freopen("out.txt","w",stdout)
	#define sz 200005
	#define ll long long
	string pattern = "tareq&shawon";
	int dp[sz][15],parent[sz];
	char ch[sz];
	vector<int>graph[sz];
	void Clean(int n)
	{
	for(int i=0 ; i<=n+2 ; i++){
	for(int j=0 ; j<15 ; j++)
	dp[i][j] = -1;
	graph[i].clear();
	parent[i] = -1;
	}
	}
	void DFS(int u,int par)
	{
	parent[u] = par;
	for(auto v : graph[u]){
	if(v != par)
	DFS(v , u);
	}
	}
	bool FuN(int u,int taken)
	{
	if(u != 1 && graph[u].size() == 1){
	if(taken == 12)
	return dp[u][taken] = 1;
	else if(taken == 11 && ch[u] == pattern[taken])
	return dp[u][taken] = 1;
	else
	return dp[u][taken] = 0;
	}
	if(dp[u][taken] != -1)
	return dp[u][taken];
	bool ret1=0,ret2=0;
	for(auto v : graph[u]){
	if(v == parent[u])
	continue;
	if(taken<12 && ch[u] == pattern[taken])
	ret1 |= FuN(v , taken+1);
	ret2 |= FuN(v , taken);
	}
	return dp[u][taken] = ret1 | ret2;
	}
	void Print(int u,int taken)
	{
	if(u != 1 && graph[u].size() == 1){
	cout<<u<<endl;
	return;
	}
	bool ret1=0,ret2=0;
	cout<<u<<' ';
	for(auto v : graph[u]){
	if(v == parent[u])
	continue;
	if(taken<12 && ch[u] == pattern[taken] && dp[v][taken+1]==1){
	Print(v , taken+1);
	break;
	}
	if(dp[v][taken] == 1){
	Print(v , taken);
	break;
	}
	}
	}
	void Solve(int t)
	{
	int i,j,k,n,ans,u,v;
	cin>>n;
	for(i=1 ; i<n ; i++){
	cin>>u>>v;
	graph[u].push_back(v);
	graph[v].push_back(u);
	}
	for(i=1 ; i<=n ; i++){
	sort(graph[i].begin() , graph[i].end());
	cin>>ch[i];
	}
	DFS(1 , -1);
	ans = FuN(1 , 0);
	if(ans){
	cout<<"Case "<<t<<": YES\n";
	Print(1 , 0);
	}
	else
	cout<<"Case "<<t<<": NO\n";
	Clean(n);
	}
	int main()
	{
	int t,T;
	cin>>T;
	memset(dp , -1 , sizeof(dp));
	for(t=1 ; t<=T ; t++){
	Solve(t);
	}
	return 0;
	}

view raw See You Again.cpp hosted with ❤ by GitHub

এই প্রব্লেমের আরো একটি সল্যুশন সম্ভব। তা ডিপি ছাড়াই করা যায় শুধু ডিএফএস দিয়ে। নিচে সেই কোডও দেয়া হলোঃ 

.

	#include<bits/stdc++.h>
	#define pb(a) push_back(a)
	#define vi vector<int>
	#define RUN_CASE(t,T) for(__typeof(t) t=1;t<=T;t++)
	using namespace std;
	#define sz 100005
	vi ans;
	int complete=0,vis[sz];
	vi graph[sz];
	char cost[sz];
	string pattern = "tareq&shawon";
	void Clean(int n)
	{
	complete = 0;
	ans.clear();
	for(int i=0 ; i<=n+2 ; i++){
	vis[i] = 0;
	graph[i].clear();
	}
	}
	void DFS(int u,int id)
	{
	vis[u] = 1;
	int nxtid = id;
	if(id<12 && cost[u] == pattern[id])
	nxtid = id+1;
	if(nxtid == 12)
	complete = 1;
	ans.pb(u);
	bool fg = 1;
	for(int i=0 ; i<(int)graph[u].size() ; i++){
	int v = graph[u][i];
	if(!vis[v])
	DFS(v , nxtid) , fg = 0;
	if(complete && !fg)
	break;
	}
	if(!complete)
	ans.pop_back();
	}
	void Solve(int t)
	{
	int i,j,k,n,u,v;
	cin>>n;
	for(i=1 ; i<n ; i++){
	cin>>u>>v;
	graph[u].pb(v);
	graph[v].pb(u);
	}
	for(i=1 ; i<=n ; i++){
	cin>>cost[i];
	sort(graph[i].begin() , graph[i].end());
	}
	DFS(1 , 0);
	if(complete){
	cout<<"Case "<<t<<": YES\n";
	cout<<ans[0];
	for(i=1 ; i<(int)ans.size() ; i++){
	cout<<' '<<ans[i];
	}
	cout<<endl;
	}
	else
	cout<<"Case "<<t<<": NO\n";
	Clean(n);
	}
	int main()
	{
	int t,T;
	cin>>T;
	RUN_CASE(t,T)
	{
	Solve(t);
	}
	return 0;
	}

view raw Toph - See you again.cpp hosted with ❤ by GitHub

Happy Coding😀