web_developer's blog

Help with 125 B (Div. 1)
By web_developer, history, 3 years ago, In English

Hello Codeforces, I need help with this problem

My sol. -> I've written recursive solution and it gives TLE on tc 20

Now, I want to optimize this... How can I? Plz help.

Thanks!!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that you can use state BFS for this problem, one dimension to determine which wall are you on, and for each step you create new 3 possible moves that is go 1 step up, go 1 step down, go up k steps and change to the other wall. The other dimension is just to store the place that you encounter when you was on the wall so that you can avoid solving one state multiple times.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    As you can see my solution do similar what you are talking....but the main problem I am having is in optimization.

    I tried taking two arrays, one for left wall and the other one for the right wall, but it gives me TLE again..

    Can you share some suede code of how will you optimize it?

    My optimization is something like below..

    string l, r;
int n, k;
// vector<vector<int>> dpl(n+1, vector<int>(n+1, -1));
// vector<vector<int>> dpr(n+1, vector<int>(n+1, -1));

vector<int> lp(n+1, -1);
vector<int> rp(n+1, -1);

int recursive(int i, int w, int left)
{	
	if(i<w){
		return 0;
	}
	if(left && l[i]=='X'){
		return 0;
	}
	if(!left && r[i]=='X'){
		return 0;
	}
	if(i>=n-1){
		return 1;
	}
	if(left)
	{
		if(lp[i]!=-1)
			return lp[i];
	}
	else if(!left)
	{
		if(rp[i]!=-1)
			return rp[i];
	}
	cout<<"";
	if(left)
	{
		int a = rp[i+k]!=-1?rp[i+k]:recursive(i+k, w+1, 0);
		rp[i+k]=a;
		int b = i<n-1 && (lp[i+1]!=-1?lp[i+1]:recursive(i+1, w+1, 1));
		lp[i+1]=b;
		int c = i>0 && (lp[i-1]!=-1?lp[i-1]:recursive(i-1, w+1, 1));
		lp[i-1]=c;
		return a||b||c;
		// return recursive(i+k, w+1, 0) || (recursive(i+1, w+1, 1) && i<n-1)||(i>0 && recursive(i-1, w+1, 1));
	}
	else
	{
		int a = lp[i+k]!=-1?lp[i+k]:recursive(i+k, w+1, 1);
		lp[i+k]=a;
		int b = i<n-1 && rp[i+1]!=-1?rp[i+1]:recursive(i+1, w+1, 0);
		rp[i+1]=b;
		int c = i>0 && rp[i-1]!=-1?rp[i-1]:recursive(i-1, w+1, 0);
		rp[i-1]=c;
		return a||b||c;
		// recursive(i+k, w+1, 1) || (recursive(i+1, w+1, 0) && i<n-1)||(i>0 && recursive(i-1, w+1, 0));
	}
}
 
string solve()
{
	cin>>n>>k;
	cin>>l>>r;
	// cout<<dp[0][0][0]<<endl;
	if(recursive(0, 0, 1))
		return "YES";
	return "NO";
}
    → Reply