Can this problem be solved using lazy segment tree ??
I believe your code fails on
1
4
1 4
2 1
3 2
4 3
where it prints “NO”, at least according to codechef’s ide.
@dazlersan1 Please let me know the failed test case for my solution
https://www.codechef.com/viewsolution/53093824
@kailee, each row contains exactly one block, and each column contains exactly one block!!
Your test case is wrong!
Please help me to find out what’s wrong with my solution😐
https://www.codechef.com/viewsolution/53093824
May I know the failed test case?
Each row and each column should have exactly one block.
1 Like
Gotcha! Thanks for this. I feel like I missed it.
void solve()
{
int n;
cin>>n;
int a[n][2][2];
//int v[n][n];
//memset(v,0,sizeof(v));
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
//x=i+1;
//y=1+rand()%n;
/*while((x==1&&y==1)||(x==n&&y==n))
{
y=1+rand()%n;
}*/
// v[x-1][y-1]=1;
a[i][0][0]=x;
a[i][0][1]=y-1;
a[i][1][0]=y+1;
a[i][1][1]=n;
/*for(int j=0;j<n;j++)
cout<<v[i][j];
cout<<endl;*/
}
vector<vector<int>>dp(n,vector<int>(2,INT_MAX));
dp[0][0]=1;
for(int i=1;i<n;i++)
{
for(int j=0;j<2;j++)
{
int first=a[i][j][0],second=a[i][j][1];
if(j==0)
{
int st1=dp[i-1][0],st2=dp[i-1][1];
int mi=min(st1,st2);
if(mi>second)
{
dp[i][j]=INT_MAX;
}
else
dp[i][j]=mi;
}
else
{
int st1=dp[i-1][0],st2=dp[i-1][1];
if(a[i-1][0][1]>=first)
{
dp[i][j]=min(dp[i][j],max(first,st1));
}
if(a[i-1][1][1]>=first)
{
dp[i][j]=min(dp[i][j],max(first,st2));
}
}
}
}
if(dp[n-1][1]!=INT_MAX)
cout<<"YES\n";
else
cout<<"No\n";
}
I have tried various test cases also tried with generator to find where i am getting wrong but not able to get it what i did is, for each row i found minimum pos before block which i can come from previous row similarly after the block, Can anyone tell me where it is wrong…:))
Thanks a lot. It fails in my IDE as well.
Yes this is correct. There is a possible path in this example
Thanks a lot
https://discuss.codechef.com/t/rechend-editorial/95744/32?u=abhishek855
can you help me in this pls::
Here is another approach .
Here we are finding all possible columns we can approach from (1 , 1) to every row’s coloumns .
since in every row there is exactly one block so there will be either 2 or 1 or 0 contiguous range(s) of columns , not any other possibility is there .
so we have to find those ranges , that’s our task .
at last if N is included in the range of reachable columns of row N then ans will be “YES” either “NO” .
/******************************************************************************
Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby,
C#, VB, Perl, Swift, Prolog, Javascript, Pascal, HTML, CSS, JS
Code, Compile, Run and Debug online from anywhere in world.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std ;
#define pb push_back
#define ff first
#define ss second
int main()
{
int t ;
cin >> t ;
while(t--){
int n ;
cin >> n ;
vector<pair<int , int>> ans , xy(n) ;
for(int i = 0 ; i < n ; i ++) cin >> xy[i].ff >> xy[i].ss ;
sort(xy.begin() , xy.end()) ;
for(int i = 0 ; i < n ; i ++){
if(i == 0) ans.pb({1 , xy[i].ss - 1}) ;
else{
vector<pair<int , int>> v , v_ ;
for(auto it : ans){
if(xy[i].ss == 1){
if(it.ss >= 2) v.pb({max(it.ff , 2) , n}) ;
}
else if(xy[i].ss == n){
if(it.ff <= n - 1) v.pb({it.ff , n - 1}) ;
}
else{
if(it.ff <= xy[i].ss - 1) v.pb({it.ff , xy[i].ss - 1}) ;
if(it.ss >= xy[i].ss + 1) v.pb({max(xy[i].ss + 1 , it.ff) , n}) ;
}
}
for(int j = 0 ; j < v.size() ; j ++){
if(j == 0) v_.pb(v[j]) ;
else{
if(v_[j - 1].ss >= v[j].ff) v_[j - 1].ss = v[j].ss ;
else v_.pb(v[j]) ;
}
}
ans = v_ ;
}
//cout << i + 1 << ':' ;
//for(auto it : ans) cout << it.ff << ' ' << it.ss << ',' ;
}
if(ans.empty()) cout << "NO\n" ;
else if(ans.back().ss == n) cout << "YES\n" ;
else cout << "NO\n" ;
}
return 0 ;
}
You have the same mistake I had. I supposed all the x values given sorted, like 1,2,3,…
Here is a testcase, answer should be “YES”.
7
2 5
3 4
7 1
4 3
5 2
1 6
6 7
Implemented dfs and got tle 
same 
5
1 3
2 3
3 3
4 3
5 3
output should be “NO” but your code output is “YES”
7
1 5
2 6
3 5
4 4
5 6
6 5
7 4
please check this test case also