Блог пользователя web_developer

Help with 125 B (Div. 1)
Автор web_developer, история, 4 года назад, По-английски

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!!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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";
}
    → Ответить