## External Problem Choosing the Pairs

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

LCSFC
New poster
Posts: 10
Joined: Fri Aug 01, 2014 2:39 pm

### External Problem Choosing the Pairs

Hi everyone, i'm trying to solve this problem of contest Dalalio:
https://www.urionlinejudge.com.br/judge ... /view/1562
My approach was taking the students as vertexes of an undirected graph G and the edges (a,b) would be if a likes b or b likes a. I used a queue and added initially all vertexes of degree one, which certainly has to make pair with his own choice in the match because no one wants them. Then for each unmatched item i dequeued i match it (i only enqueue if it has degree one) and decrement one from the degree of all adjacent to the pair[ i ] . If after the queue is empty there is some unmatched i match with its choice if possible, if not possible then i set the flag of impossible matching, if n is odd i also set this flag. Is this approach in the right way? Give me some tips of a way to solve it, please.
Sorry if posting links from other judges is forbidden, but i'm really curious on how to do this problem.
Thanks!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: External Problem Choosing the Pairs

Post your code, are you getting WA, TLE, or ?
Check input and AC output for thousands of problems on uDebug!

LCSFC
New poster
Posts: 10
Joined: Fri Aug 01, 2014 2:39 pm

### Re: External Problem Choosing the Pairs

I'm getting WA 60%, the code is this:

Code: Select all

``````#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 50000
#define MAXVERTEX 10005
#define INFINITY 100000000
typedef struct edge
{
int u,v;

}
EDGE;
EDGE g[MAX];
//ordering edges of list of edges
int compare(const void* a,const void* b)
{
EDGE x=*(edge*)a;
EDGE y=*(edge*)b;
if(x.u!=y.u)
return x.u-y.u;
return x.v-y.v;

}
main()
{
int i,j,n,m,k,v,front,rear,p,correct;
int degree[MAXVERTEX],begin[MAXVERTEX],matched[MAXVERTEX],queue[MAXVERTEX],prefer[MAXVERTEX];
while(scanf("%d",&n)!=EOF)
{
k=0;//number of edges in the edge-list g
for(i=0;i<n;i++)
{
degree[i]=0;
begin[i]=-1;
matched[i]=-1;
prefer[i]=-1;
}

for(i=0;i<n;i++)
{
scanf("%d",&prefer[i]);
prefer[i]--;
v=prefer[i];
if(prefer[v]!=i)//if the edge was not in the graph
{
g[k].u=i;
g[k].v=v;
k++;
g[k].u=v;
g[k].v=i;
k++;
degree[i]++;
degree[v]++;
}

}
qsort(g,k,sizeof(edge),compare);
v=0;
for(i=0;i<k;i++)
{
if(g[i].u==v)
{
begin[v]=i;//beginning of the list of edges of v
v++;
}
}
front=rear=0;
for(i=0;i<n;i++)
{
if(degree[i]==1)
queue[rear++]=i;
}
while(front!=rear)
{
v=queue[front++];
if(matched[v]==-1)//unmatched
{
//if v is in the queue it has degree 1, so there is only one possible unmatched vertex adjacent to v
for(i=begin[v];g[i].u==v && i<k;i++)
{
if(matched[g[i].v]==-1)
{
matched[v]=g[i].v;
matched[g[i].v]=v;
i=k+1;
}
}
//decrement degree of all adjacent to the matched of v, if became one, enqueue it
p=matched[v];
for(i=begin[p];g[i].u==p && i<k;i++)
{
degree[g[i].v]--;
if(matched[g[i].v]==-1 && degree[g[i].v]==1)
queue[rear++]=g[i].v;
}
//both are matched, they has degree 0
degree[v]=degree[matched[v]]=0;
}
}
correct=1;
//if there were a cicle in the graph they would not be matched in the process before, but if the cile is even i can match
//everyone trivially
for(i=0;i<n;i++)
{
if(matched[i]==-1 && matched[prefer[i]]==-1)
{
matched[i]=prefer[i];
matched[prefer[i]]=i;
}
}
//if there is someone unmatched its not possible
for(i=0;i<n;i++)
{
if(matched[i]==-1)
correct=0;
}
//if n is odd, it wasnt possible anyway
if(n%2!=0)
correct=0;
if(correct)
{
for(i=0;i<n;i++)
{
printf("%d ",matched[i]+1);
}
printf("\n");
}
else
{
printf("IMPOSSIBLE\n");
}

}
return 0;
}

``````
In the URI Online Judge they put that the theory of the solution of the problem was BFS. I would really apreciate if someone find some test case that fails my code. Thanks!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: External Problem Choosing the Pairs

The sample output doesn't have spaces at the end of a line.
Check input and AC output for thousands of problems on uDebug!

LCSFC
New poster
Posts: 10
Joined: Fri Aug 01, 2014 2:39 pm

### Re: External Problem Choosing the Pairs

Thanks, i changed that, but now i'm getting wrong answer without percentage, is this solution in the right way? Is there any tricky test case?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: External Problem Choosing the Pairs

What is the difference between WA 60% and WA without percentage?
Check input and AC output for thousands of problems on uDebug!

LCSFC
New poster
Posts: 10
Joined: Fri Aug 01, 2014 2:39 pm

### Re: External Problem Choosing the Pairs

The updated code is this:

Code: Select all

``````#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 50000
#define MAXVERTEX 10005
#define INFINITY 100000000
typedef struct edge
{
int u,v;

}
EDGE;
EDGE g[MAX];
//ordering edges of list of edges
int compare(const void* a,const void* b)
{
EDGE x=*(edge*)a;
EDGE y=*(edge*)b;
if(x.u!=y.u)
return x.u-y.u;
return x.v-y.v;

}
main()
{
int i,j,n,m,k,v,front,rear,p,correct;
int degree[MAXVERTEX],begin[MAXVERTEX],matched[MAXVERTEX],queue[MAXVERTEX],prefer[MAXVERTEX];
while(scanf("%d",&n)!=EOF)
{
k=0;//number of edges in the edge-list g
for(i=0;i<n;i++)
{
degree[i]=0;
begin[i]=-1;
matched[i]=-1;
prefer[i]=-1;
}

for(i=0;i<n;i++)
{
scanf("%d",&prefer[i]);
prefer[i]--;
v=prefer[i];
if(prefer[v]!=i)//if the edge was not in the graph
{
g[k].u=i;
g[k].v=v;
k++;
g[k].u=v;
g[k].v=i;
k++;
degree[i]++;
degree[v]++;
}

}
qsort(g,k,sizeof(edge),compare);
v=0;
for(i=0;i<k;i++)
{
if(g[i].u==v)
{
begin[v]=i;//beginning of the list of edges of v
v++;
}
}
front=rear=0;
for(i=0;i<n;i++)
{
if(degree[i]==1)
queue[rear++]=i;
}
while(front!=rear)
{
v=queue[front++];
if(matched[v]==-1)
{
//if v is in the queue it has degree 1, so there is only one possible unmatched vertex adjacent to v
for(i=begin[v];g[i].u==v && i<k;i++)
{
if(matched[g[i].v]==-1)
{
matched[v]=g[i].v;
matched[g[i].v]=v;
i=k+1;
}
}
//decrement degree of all adjacent to the matched of v, if became one, enqueue it
p=matched[v];
for(i=begin[p];g[i].u==p && i<k;i++)
{
degree[g[i].v]--;
if(matched[g[i].v]==-1 && degree[g[i].v]==1)
queue[rear++]=g[i].v;
}
//both are matched, they has degree 0
degree[v]=degree[matched[v]]=0;
}
}
correct=1;
//if there were a cicle in the graph they would not be matched in the process before, but if the cile is even i can match
//everyone trivially
for(i=0;i<n;i++)
{
if(matched[i]==-1 && matched[prefer[i]]==-1)
{
matched[i]=prefer[i];
matched[prefer[i]]=i;
}
}
//if there is someone unmatched its not possible
for(i=0;i<n;i++)
{
if(matched[i]==-1)
correct=0;
}
//if n is odd, it wasnt possible anyway
if(n%2!=0)
correct=0;
if(correct)
{
for(i=0;i<n;i++)
{
printf("%d",matched[i]+1);
if(i!=n-1)
printf(" ");
}
printf("\n");
}
else
{
printf("IMPOSSIBLE\n");
}

}
return 0;
}
``````
I think the difference is that if is WA without percentage it doesn't passed only few tests (less then 5%), in a problem called A Day In Math Land i received that answer and it was one case that i was printing -0.00... that's why i think there is a tricky case...i also already tried not printing ' \n ' after last test but made no difference...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: External Problem Choosing the Pairs

Input:
6
2 4 5 3 6 1

Correct output:
2 1 4 3 6 5

Here's how I found this, using a technique that is often useful. I wrote a brute force recursive solver that for each student, tried both pairing them with their desired partner if possible and skipping them. Then if you're able to match all students print the result. This approach probably would get TLE on the judge, however you can use it for small N to test your code. I then wrote a random input generator - that didn't reveal any issues with your code. Next I wrote an input generator that printed all possible inputs for N <= 6, and I found the above mismatch, as well as many others.
Check input and AC output for thousands of problems on uDebug!

LCSFC
New poster
Posts: 10
Joined: Fri Aug 01, 2014 2:39 pm

### Re: External Problem Choosing the Pairs

Yeah i already used this techinique sometimes, but in this problems it can help really a lot...In this test case that you gave me i realized that my idea of matching the 2 degree cycles, which are not matched in the while, is wrong,but i think there's only one way to match them isn't it? i implemented a brute force aproach for little inputs now. I will think about other ideas and then test...Thanks a lot!