### Shuaib's blog

By Shuaib, 11 years ago, Problem C:

I find the first two consecutive non equal integers, and check whether they are increase or decreasing. Then I look for the next integer that is in the opposite order. (Gives wrong answer on test 18)

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>

using namespace std;

int main()
{
long long n;
vector<long long> v;
cin>>n;
long long x;
for(long long i=0;i<n;i++)
{
cin>>x;
v.push_back(x);
}

if(v.size()<3)
{
cout<<0;
return 0;
}
else
{
int ind=0;
for(long long i=0;i<v.size();i++)
{
if(v[i+1]-v[i]!=0)
{
ind=i;
break;
}
}

for(long long i=ind+2;i<v.size();i++)
{
if((v[ind+1]-v[ind]>0 && v[i]-v[i-1]<0) || (v[ind+1]-v[ind]<0 && v[i]-v[i-1]>0))
{
cout<<"3"<<endl;
cout<<ind+1<<" "<<ind+2<<" "<<i+1;
return 0;
}

}
}
cout<<0;

return 0;
}

Problem D:

I maintain two adjacency matrices, one for connection outside the circle, and one for inside. When a new road is to be build, I check whether there is a road crossing inside/outside between the two cities. (Wrong answer on test 23)

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>

using namespace std;

bool check(int x, int y, vector<vector<int> > & v)
{
if(x>y)
swap(x, y);
x=x-1;
y=y-1;
for(int i=x+1;i<y;i++)
{
for(int j=0;j<x;j++)
{
if(v[j][i]==1)
return false;
}
for(int j=y+1;j<v.size();j++)
{
if(v[j][i]==1)
return false;
}
}
v[x][y]=1;
v[y][x]=1;
return true;
}

int main()
{

int n, m;

cin>>n>>m;
vector<vector<int> > in(n, vector<int>(n, 0));
vector<vector<int> > out(n, vector<int>(n, 0));

int x, y;
vector<char> cv;
for(int i=0;i<m;i++)
{

cin>>x>>y;
if(check(x, y, in))
{
cv.push_back('i');
}
else if(check(x, y, out))
{
cv.push_back('o');
}
else {
cout<<"Impossible";
return 0;
}
}

for(int i=0;i<cv.size();i++)
{
cout<<cv[i];
}
return 0;
}  Comments (11)
 For the problem C, try this test:41 2 4 3
•  Thanks, adamax! Makes it clear.
•  I had the same problem and this test helped me to find my bug:5-1 -2 -6 -3 -4
 yes,just try adamax's examplethe main mistake of your code is the third number totally depends on whether the first number is bigger or smaller than the second number that you find first.
 and the problem D ,I think it's a 2-SAT problem
•  Thanks for the comment, kyno.yang! I am going to look into problem D in detail later. But I was wondering what's wrong with my approach.
•  Consider a situation that if a road both fit outside and inside , your code will put it into inside matrix,this will lead some aftereffects, it maybe conflict whit the next roads . But if you put it into outside matrix maybe is better.you can try this test6 41 34 63 52 4
•  Phew! Thanks! I understand the problem now. Gotta read on 2-SAT :)
•  With pleasure (∩_∩)~
•  D is a simple graph coloring problem.
•  Yep, Thank you for your tip.