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!
External Problem Choosing the Pairs
Moderator: Board moderators
-
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!
Re: External Problem Choosing the Pairs
I'm getting WA 60%, the code is this:
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!
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;
}
-
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!
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
Post your updated code.
What is the difference between WA 60% and WA without percentage?
What is the difference between WA 60% and WA without percentage?
Check input and AC output for thousands of problems on uDebug!
Re: External Problem Choosing the Pairs
The updated code is this:
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...
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;
}
-
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.
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!
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!