Shuaib's blog

What's wrong with my solution to problem C and D (beta round 27)?
By Shuaib, 14 years ago, In English
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;
}

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
For the problem C, try this test:
4
1 2 4 3
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
yes,just try adamax's example
the 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.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
and the problem D ,I think it's a 2-SAT problem
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 test
      6 4
      1 3
      4 6
      3 5
      2 4

      → Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    D is a simple graph coloring problem. 
    → Reply