### 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[0].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;
}

• 0

 11 years ago, # |   0 For the problem C, try this test:41 2 4 3
•  11 years ago, # ^ |   0 Thanks, adamax! Makes it clear.
•  11 years ago, # ^ |   0 I had the same problem and this test helped me to find my bug:5-1 -2 -6 -3 -4
 11 years ago, # |   0 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.
 11 years ago, # |   0 and the problem D ,I think it's a 2-SAT problem
•  11 years ago, # ^ |   0 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.
•  11 years ago, # ^ |   0 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
•  11 years ago, # ^ |   0 Phew! Thanks! I understand the problem now. Gotta read on 2-SAT :)
•  11 years ago, # ^ |   0 With pleasure (∩_∩)~
•  11 years ago, # ^ |   +1 D is a simple graph coloring problem.
•  11 years ago, # ^ |   0 Yep, Thank you for your tip.