### web_developer's blog

By web_developer, history, 15 months ago,

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

 » 15 months ago, # |   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.
•  » » 15 months ago, # ^ | ← 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> dpl(n+1, vector(n+1, -1)); // vector> dpr(n+1, vector(n+1, -1)); vector lp(n+1, -1); vector rp(n+1, -1); int recursive(int i, int w, int left) { 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 = i0 && (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) && i0 && 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 = i0 && 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) && i0 && recursive(i-1, w+1, 0)); } } string solve() { cin>>n>>k; cin>>l>>r; // cout<
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +1 Let me see if I could implement the solution and I will leave a link here if it gets accepted.update: code
•  » » » » 15 months ago, # ^ |   0 Thank u very much...
•  » » » » » 15 months ago, # ^ |   0 you're welcome.