10158 - War

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

DJYA
New poster
Posts: 7
Joined: Sat Jan 10, 2004 10:18 pm

10158 - War

Post by DJYA » Thu Jan 22, 2004 5:13 pm

Hello everybody~

I'm trying to solve problem 10158 but always get TLE. :evil:

This problem should be about "disjiont set".
But it's like to think about so many conditions .

Could someone tell me how to solve this problem in detail ??

THX!!

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha » Sun Jun 19, 2005 3:54 pm

It is indeed a problem about "Disjoint Sets". I'll give you a small clue: at any given time a person X can be enemies with only one (or zero) group of friends Y. Never more than that.
Daniel
UFRN HDD-1
Brasil

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm

Post by hi!man! » Wed May 02, 2007 3:35 pm

I always got WA in this problem...
can anyone help me??? thanks.

a[] records friend relationship
b[] records enemy relationship

maybe I miss something...

Code: Select all

ACed
Last edited by hi!man! on Thu May 03, 2007 2:18 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed May 02, 2007 8:25 pm

Try the case.

Input:

Code: Select all

10
2 7 4
1 9 4
3 8 2
1 5 5
2 7 1
4 5 2
4 6 1
1 2 3
1 2 1
1 8 5
4 6 1
3 9 2
4 9 5
3 3 1
3 3 3
1 1 1
0 0 0
Output:

Code: Select all

0
0
0
0
1
0
1
1
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm

Post by hi!man! » Thu May 03, 2007 7:11 am

after I modify my code
still WA :(
I think that it should not have a "s" in setFriend()
but when I remove it
I got RE..is this because stack overflow?

Code: Select all

ACed
Last edited by hi!man! on Thu May 03, 2007 2:18 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu May 03, 2007 1:24 pm

hi!man! wrote: I think that it should not have a "s" in setFriend()
I don't understand what you are mentioning. However test the set...

Input:

Code: Select all

10
4 4 0
2 4 8
3 2 4
2 5 1
4 1 1
4 2 7
1 1 4
3 3 2
3 1 6
3 5 7
3 1 8
2 2 7
4 5 4
4 1 2
2 3 4
2 1 3
1 7 4
3 7 7
4 3 1
2 8 6
0 0 0
Output:

Code: Select all

0
0
0
0
0
0
0
0
1
0
1
1
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm

Post by hi!man! » Thu May 03, 2007 2:23 pm

thanks for your help~
I got AC :)
the main reason I got WA is that b[] has some problem..

btw, I don't know how to explain "s" meaning..
(sorry for my poor English)
however, it is not important now :)

jpeanut
New poster
Posts: 1
Joined: Fri May 11, 2007 7:33 pm

Post by jpeanut » Wed May 16, 2007 12:29 pm

I passed all the test code

BUT Still Wa could someone tell me where is wrong

Code: Select all

#include <stdio.h>

int main(){
int f[10000];   
int kind,b,c;
int people=0;
int count=1;


   scanf("%d",&people);
   for(int i=0;i<people;i++)f[i]=0;
   scanf("%d %d %d",&kind,&b,&c);

   while ((kind!=0)||(b!=0)||(c!=0)){
    
     if(kind==1){
         if (f[b]==0&&f[c]==0){
            f[b]=count;
            f[c]=count;
            count++; 
                 }
         else if (f[b]!=0&&f[c]==0) f[c]=f[b];
         else if (f[c]!=0&&f[b]==0) f[b]=f[c];
         else if (f[b]!=f[c]&&f[b]!=-f[c]) for(int i=0;i<people;i++){if(f[i]==f[c])f[i]=f[b];
                                                                     if(f[i]==-f[c])f[i]=-f[b];}
             
         else if (f[c]==-f[b]) printf("-1\n");
      }

     if(kind==2){
       if(f[b]==f[c]){
         if (f[b]==0&&f[c]==0){
               f[b]=count;
               f[c]=0-count;
               count++;               
                  }
         else printf("-1\n");
          }
       else if (f[b]!=0&&f[c]==0) f[c]=-f[b];
       else if (f[c]!=0&&f[b]==0) f[b]=-f[c];
       else if (f[b]!=f[c]&&f[b]!=-f[c]) for(int i=0;i<people;i++){if(f[i]==f[c])f[i]=-f[b];
                                                                   if(f[i]==-f[c])f[i]=f[b];}
      }


     if(kind==3){
          if (f[b]==f[c]&&f[b]!=0&&f[c]!=0) printf("1\n");
          else printf("0\n");
        }

     if(kind==4){
          if (f[b]==-f[c]&&f[b]!=0&&f[c]!=0) printf("1\n");
          else printf("0\n");
        }

     scanf("%d %d %d",&kind,&b,&c);
}
return 0;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed May 16, 2007 7:48 pm

Try the set below.

Input:

Code: Select all

5
2 3 3
0 0 0
Output:

Code: Select all

-1
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm

Post by renato_ferreira » Mon Jul 02, 2007 9:01 pm

Now I got RE (Signal 11) :( :(

Code: Select all

#include <stdio.h>

int *pai, *rank, *flag, pessoas;

void MakeSet(int x);
int FindSet(int x);
void Union(int x, int y);
void Separa(int x, int y);

int main()
{
    int comando, n1, n2, i;

    scanf("%d", &pessoas);

    pai = calloc(pessoas, sizeof(int));
    rank = calloc(pessoas, sizeof(int));
    flag = calloc(pessoas, sizeof(int));

    for (i = 0; i < pessoas; i++)
    {
        MakeSet(i);
    }

    while (scanf("%d %d %d", &comando, &n1, &n2))
    {
        if (comando == 0)
        {
            break;
        }

        n1 = FindSet(n1);
        n2 = FindSet(n2);

        if (comando == 1)
        {
            if (flag[n1] == n2)
            {
                printf("-1\n");
            }

            else
            {
                Union(n1, n2);
            }
        }

        else if (comando == 2)
        {
            if (n1 == n2)
            {
                printf("-1\n");
            }

            else
            {
                Separa(n1, n2);
            }
        }

        else if (comando == 3)
        {
            for (i = 0; i < pessoas; i++)
            {
                if (flag[n1] == i && flag[n2] == i)
                {
                    n1 = n2;

                    break;
                }
            }

            if (n1 != n2)
            {
                printf("0\n");
            }

            else
            {
                printf("1\n");
            }
        }

        else
        {
            if (flag[n1] != n2)
            {
                printf("0\n");
            }

            else
            {
                printf("1\n");
            }
        }
    }

    return 0;
}

void MakeSet(int x)
{
    pai[x] = x;
    rank[x] = 1;
    flag[x] = -1;
}

int FindSet(int x)
{
    if (x != pai[x])
    {
        pai[x] = FindSet(pai[x]);
    }

    return pai[x];
}

void Union(int x, int y)
{
    int i;

    if (x == y)
    {
        return;
    }

    if (rank[x] > rank[y])
    {
        pai[x] = y;
        rank[y] += rank[x];

        for (i = 0; i < pessoas; i++)
        {
            if (flag[x] == i)
            {
                flag[y] = i;
                flag[i] = y;
            }
        }
    }

    else
    {
        pai[y] = x;
        rank[x] += rank[y];

        for (i = 0; i < pessoas; i++)
        {
            if (flag[y] == i)
            {
                flag[x] = i;
                flag[i] = x;
            }
        }
    }
}

void Separa(int x, int y)
{
    if (flag[x] == -1 && flag[y] == -1)
    {
        flag[x] = y;
        flag[y] = x;
    }

    else
    {
        Union(flag[x], y);
        Union(flag[y], x);
    }
}

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10158 - War

Post by Articuno » Fri Sep 04, 2009 12:17 pm

Can anyone give me some more critical test cases? I am getting WA and I can't find my error. Someone please help.....
Here is my code:
AC
Here is a test case:

Code: Select all

5
1 0 1
1 2 3
2 1 3
1 0 2
0 0 0
The output should be:
-1
Hope it helps
Last edited by Articuno on Sun Nov 15, 2009 10:55 pm, edited 1 time in total.

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 10158 - War

Post by calicratis19 » Sat Sep 12, 2009 3:41 pm

can anyone please discuss how to solve this problem. i cant figure out how to do it with union find.

i figured out how to mark enemies.but couldnt figured out how to find common enemies.

any help will be appreciated .thank you.
Heal The World

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 10158 - War

Post by Angeh » Sun Mar 21, 2010 12:49 pm

Hi all ,
would sombody how has solved the problem give some hints ...
:(
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

amishera
New poster
Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

Re: 10158 - War

Post by amishera » Sat Jul 03, 2010 1:55 am

You have to use disjoint set forest algorithm. Or you can also use binary search tree. I think disjoint forest would be faster.

csprajeeth
New poster
Posts: 5
Joined: Sat May 26, 2012 7:25 pm

Re: 10158 - War

Post by csprajeeth » Sat Dec 28, 2013 11:04 pm

For those getting runtime error.... most likely you are overflowing the stack (due to unbounded recursion). Check if you are introducing cycles in your disjoint set data structure.

Post Reply

Return to “Volume 101 (10100-10199)”