Why do I get TLE on problem B in august challenge?

general
1

Submission : https://www.codechef.com/viewsolution/7730530
Idea : Find the lane from which to start, then if you meet an obstacle and not both roads blocked do try to jump to other lane diagonal block if not jump to parallel block.

Solution is O(N).

2

There is no need to jump to the parallel block. Think about it.
If you’re not getting it, read the editorial.

3

That doesn’t make sense.You have to jump to the parallel block if there is an obstacle in front of you and you cannot jump to the diagonal.

4

Okay,let’s consider that we can move to the parallel cell.

Now I’ll prove that this statement is wrong by CONTRADICTION!

lets consider these four cells.

alt text

Imagine that you are initially at cell ‘C’.

Now you move to Cell ‘D’ which is parallel to it.(which according to you can be considered as an optimal move)

Now from cell ‘D’,you have two choices–

->Either you can move to cell ‘B’.(when A is blocked). It takes two steps(C–D--B).
But you can also move from ‘C’ directly to ‘B’(1 move which is optimum).

–>From cell ‘D’,you can also move to cell ‘A’.(when B is blocked). that would be C–D--A(two moves).
You were initially at ‘C’(this could have been done in one move i.e C–A).

In either of the cases you see moving parallel is not optimum.

And if you cannot jump to the next block nor the diagonal. In that case,you cannot simply go beyond that.

I got AC for my solution at first attempt :slight_smile:

You may check the code. It’s easy to understand - Solution

I hope you understand it. :slight_smile:

5

there’s no problem named B there :smiley:

6

See, if there is an obstruction at same position in both the lanes, you can’t reach the end of the lane, and print “-1”. Simple O(N) solution.

#include<bits/stdc++.h>

typedef long long int ll;
#define sc scanf
#define pr printf
#define loop(i,a,n) for(i=a;i<n;i++)
#define loop2(i,a,n) for(i=a;i>n;i--)
#define M 1<<30


using namespace std;

int main()
{
	int t,i;
	cin>>t;
	
	char path[2][200001];
	while(t--) {
		
		cin>>path[0]>>path[1];
		int l=strlen(path[0]),c=0,sw=0;
		for(i=0;i<l;i++) {
			bool b1=path[0][i]=='#';
			bool b2=path[1][i]=='#';
			if(b1 && b2) {
				sw=M;
				break;
			}
			if(b1) {
				if(c==1) sw++;
				c=0;
			}
			if(b2){
				if(c==0) sw++;
				c=1;
			}
		}
		if(sw>=M) cout<<"No\n";
		else cout<<"Yes\n"<<sw<<"\n";
		
	}

	return 0;
}
1 Like