➤ Problem Link : 339C. Xenia and Weights
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
set<pair<int,int> > visited;
pair<int,pair<int,int> > depth[4501][4001];
bool flag = 0;
void printVal(int x,int y,bool turn , int j,int m)
{
if(j>=m)
return;
int mx = depth[x][y].second.first;
int my = depth[x][y].second.second;
if(!turn)
{
cout<<mx-x<<" ";
printVal(mx,my,1,j+1,m);
}
else
{
cout<<my-y<<" ";
printVal(mx,my,0,j+1,m);
}
}
int dfs(int x, int y, bool turn,string s,int j,int m,int prev)
{
int diff;
int dpt=0,mx=-1,my=-1;
if(flag)
return 0;
if(j==m+1)
{
flag=1;
return 0;
}
if(!turn)
{
diff = y - x;
int val;
for(int i = diff; i< 10;i++)
{
if(s[i]=='0' || i == prev-1)
continue;
if(visited.find(make_pair(x+i+1,y))==visited.end())
{
visited.insert(make_pair(x+i+1,y));
val = dfs(x+i+1,y,1,s,j+1,m,i+1);
}
else
val = depth[x+i+1][y].first;
if( val > dpt )
{
dpt=val;
mx = x+i+1;
my = y;
}
}
}
else
{
diff = x - y;
int val;
for(int i = diff; i< 10;i++)
{
if(s[i]=='0' || i==prev-1)
continue;
if(visited.find(make_pair(x,y+i+1))==visited.end())
{
visited.insert(make_pair(x,y+i+1));
val = dfs(x,y+i+1,0,s,j+1,m,i+1);
}
else
val = depth[x][y+i+1].first ;
if( val > dpt )
{
dpt=val;
mx = x;
my = y+i+1;
}
}
}
depth[x][y].first = dpt+1;
depth[x][y].second = make_pair(mx, my);
return dpt+1;
}
int main()
{
string s;
cin>>s;
int m;
cin>>m;
memset(depth,0,sizeof(depth));
visited.insert(make_pair(0,0));
int val=dfs(0,0,0,s,0,m,-1);
if(val<=m)
cout<<"NO";
else
{
cout<<"YES\n";
printVal(0,0,0,0,m);
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.