Page 1 of 1

External Problem Choosing the Pairs

Posted: Fri Feb 06, 2015 10:03 pm
by LCSFC
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!

Re: External Problem Choosing the Pairs

Posted: Tue Feb 10, 2015 3:59 am
by brianfry713
Post your code, are you getting WA, TLE, or ?

Re: External Problem Choosing the Pairs

Posted: Thu Feb 12, 2015 2:20 pm
by LCSFC
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!

Re: External Problem Choosing the Pairs

Posted: Fri Feb 13, 2015 12:08 am
by brianfry713
The sample output doesn't have spaces at the end of a line.

Re: External Problem Choosing the Pairs

Posted: Fri Feb 13, 2015 10:24 pm
by LCSFC
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?

Re: External Problem Choosing the Pairs

Posted: Fri Feb 13, 2015 10:32 pm
by brianfry713
Post your updated code.
What is the difference between WA 60% and WA without percentage?

Re: External Problem Choosing the Pairs

Posted: Sat Feb 14, 2015 3:04 pm
by LCSFC
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...

Re: External Problem Choosing the Pairs

Posted: Wed Feb 18, 2015 12:48 am
by brianfry713
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.

Re: External Problem Choosing the Pairs

Posted: Thu Feb 19, 2015 2:24 pm
by LCSFC
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!