793 - Network Connections

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

Moderator: Board moderators

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Tue May 09, 2006 9:44 pm

I see you use DFS, but it's better to switch to Union-find, really.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Tue May 09, 2006 9:49 pm

As far as your input is concerned you'll not get TLE but WA. Test this case

Code: Select all

1

10
c 2 5
q 2 5
There is no specification about the input range. So no idea how many vertices you have to deal with. Maybe even large enough to fit in your 10 sized s1 and s2 arrays! Calling DFS so many times will cause TLE.

Use dijsoint sets.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Tue May 09, 2006 10:38 pm

above input is now ok. and also others input/output. Any more I/O!!!
now i m getting WA..... so sad!!!
plz help

Code: Select all

removed
Last edited by asif_rahman0 on Wed May 10, 2006 4:37 am, edited 1 time in total.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Tue May 09, 2006 11:20 pm

A very straightforward input to show your error

Code: Select all

2

2
c 1 2
q 1 2

3
c 1 3
q 1 2

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Wed May 10, 2006 4:41 am

thnx mamun vai

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Fri Jul 14, 2006 8:23 pm

Salamo Aleko.
Sorry i do not like reading codes...

But this is a good advice....
In many contests you may face diffrent problems like this, trying every time to make good and fast algorithm is not some thing good.
There is a algorithm called "Union Find operation with path compression"
This is the fastest know lgorithm for Union Find operation. Moreover it is to simple. You can find the full source code in this book
"Introduction to algorithms"
You can solve with it efficiently the next problems
"793 10583 10685 10608 615" :lol: 8)
Sleep enough after death, it is the time to work.
Mostafa Saad

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Sat Jul 15, 2006 4:27 am

I've used my faulty union-find to solve a few problems, but this one made me realize that it doesn't work quite the way I thought it would.

Here's a case on which my implementation is failing:

Code: Select all

1

9
c 3 9
c 1 6
c 4 8
c 3 2
c 3 8
c 5 7
c 6 2
c 5 4
q 9 1
q 4 8
Output should be

Code: Select all

2,0
P.S. Instead of C&P I retyped it and that caused its faultiness, it was ok all along.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Sat Jul 15, 2006 6:38 pm

You are right

I use the method and got AC on 793 and 10583

Thanks your help :D

f.eliel
New poster
Posts: 10
Joined: Wed Feb 08, 2006 4:31 pm

793 - WA

Post by f.eliel » Mon Sep 04, 2006 3:34 pm

My code worked fine for every test case i found here, but i still get WA.
Can someone help me?

Here is my code:

Code: Select all

#include <stdio.h>

#define max 1000

int m[max][max], d[max];
int fila[max], inicio, fim;
int suc, unsuc;

void adiciona(int a, int b) {
   int i;
   for (i = 1; i <= m[a][0]; i++)
      if (m[a][i] == b) break;
   if (i = m[a][0]+1) {
      m[a][++m[a][0]] = b;
      m[b][++m[b][0]] = a;
   }
}

void colocanafila(int n) {
     fila[fim++] = n;
     if (fim > (max-1)) fim = 0;
}

int retiradafila() {
    int ret;
    if (inicio == fim) ret = -1;
    else ret = fila[inicio++];
    if (inicio > (max-1)) inicio = 0;
    return ret;
}

void bfs(int a, int b) {
   int i, w;
     
   memset(d, -1, sizeof(d));
   d[a] = 1;
   inicio = fim = 0;
   w = a;
   while (w != -1) {
      for(i = 1; i <= m[w][0]; i++) {
         if (d[m[w][i]] == -1) {
            if (m[w][i] == b) {
               suc++;
               w = 0;
               break;
            }
            else {
               d[m[w][i]] = 1;
               colocanafila(m[w][i]);
            }
         }
      }
      if (!w) break;
      w = retiradafila();           
   }
   if (w == -1) unsuc++;
}


int main()
{
   int t, n, q, w, first=1;
   int ci, cj;
   char tipo[2];
   
   scanf("%d", &t);
   while (t) {
      if (first) first = 0;
      else printf("\n");
      t--;
      memset(m, 0, sizeof(m));
      suc = unsuc = 0;
      scanf("%d", &n);
      while (scanf("%s %d %d\n", tipo, &ci, &cj) == 3) {
         switch (tipo[0]) {
            case 'c': adiciona(ci, cj); break;
            case 'q': bfs(ci, cj); break;
         }
      }
      printf("%d,%d\n", suc, unsuc);
   }
   return 0;
}
Thanks.

elmariachi1414
New poster
Posts: 2
Joined: Sat Oct 14, 2006 9:52 pm

Post by elmariachi1414 » Sat Oct 14, 2006 9:55 pm

There is a great article about "Union Find operation" algorithm here:
http://valis.cs.uiuc.edu/~sariel/teach/ ... /22_uf.pdf

darkos32
New poster
Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia
Contact:

793 RUNTIME ERROR SIGNAL 11 ?

Post by darkos32 » Wed Feb 14, 2007 5:01 am

this is my code :

Code: Select all

CODE REMOVED

what's wrong with my code ?thanks.
Last edited by darkos32 on Wed Feb 14, 2007 8:38 am, edited 1 time in total.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Feb 14, 2007 6:19 am

hint:

Code: Select all

#define max 200
----
!! Don't open a new thread if there is a thread already for the problem.

darkos32
New poster
Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia
Contact:

sad

Post by darkos32 » Wed Feb 14, 2007 7:52 am

yep...i've changed to 1000,but i'm now got WA...

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Feb 14, 2007 8:21 am

hint2:

Code: Select all

1

1
q 1 1
hint3:
There is a bug in connect(int, int).

darkos32
New poster
Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia
Contact:

sad

Post by darkos32 » Wed Feb 14, 2007 8:37 am

i've changed the code to :

Code: Select all

CODE REMOVED
but i've still got WA...
Last edited by darkos32 on Wed Feb 14, 2007 9:04 am, edited 1 time in total.

Post Reply

Return to “Volume 7 (700-799)”