10583 - Ubiquitous Religions

[N|N0]

Beware!

The official test case also includes an input where i = j, so a pair of same student. In that case, the number of religions increases by 1 and number of non-religious student decreases by 1.

[N|N0]

The official input also includes a pair where i = j, so a pair of the same student who believes in his own religion. Beware!

[Mohammad Mahmudur Rahman]

The official input also includes a pair where i = j, so a pair of the same student who believes in his own religion. Beware!

Seems that you have had some serious bad experiences with this test case ! OK, If you use the standard union-find or DFS (correctly implemented, off course ) algorithm to solve this problem, why should this case i==j create any problem at all ?

[N|N0]

My algorithms is made only for that particular problem. So I don't use some generic approach, but I just count what needs to be counted. So if (i = j) that means that atheist -= 1, not atheist -= 2

[Mohammad Mahmudur Rahman]

I understand what you mean. But the point I want to make is that most people will probably solve this problem using union-find (or DFS) as this is a pretty straight-forward union-find problem. Hence, they should not worry much about this (i==j) case.

[Ashganek]

Code: Select all

#include <cstdlib>
#include <iostream>
#include <list>

using namespace std;

int main(int argc, char *argv[])
{
    int n, m, l, r, d, w, c = 0, x = 0;
    list<int> lista;
    
    while( cin >> n >> m ) {
        if( n == 0 and m == 0 )
            break;
            
            
        int *students[n+1];
        int religions[n+1], temp[n+1];
        c++; d = 1; w = 1;
        
        for( int i = 1; i <= n; i++ )
             students[i] = &x;
        
        for( int i = 0; i < m; i++ ) {
             cin >> l >> r;
             
             if( *students[l] == 0 and *students[r] == 0 ) {
                 religions[w] = d;
                 temp[d] = w;
                 students[r] = &religions[w];
                 if( r != l ) {
                     students[l] = &religions[w];
                     lista.push_front(l);
                 }
                 lista.push_front(r);
                 d++; w++;
             }
             else if( *students[r] == 0 ) {
                  students[r] = students[l];
                  lista.push_front(r);
             }
             else if( *students[l] == 0 ) {
                  students[l] = students[r];
                  lista.push_front(l);
             }
             else if( *students[l] != *students[r] ) {
                  religions[temp[*students[l]]] = *students[r];
                  d--;
             }
        }
        d = n-lista.size()+d-1;
        cout << "Case " << c << ": " << d << "\n";
        lista.clear();
    }
}

and I got runtime error when i tried to do it without * and & (dunno how to call it in english ) i did it on one array and when i found two diffrent students i loop all change the religion number, but i got TLE then.

Any suggestion?[/code]

[Ashganek]

Ok, I made it using other way

[renato_ferreira]

Hello, I don't understand why WA:

Code: Select all

Accepted

[Jan]

Your code doesn't even pass the samples. Check carefully.

[renato_ferreira]

Thank you very much, AC =)

[skulty]

It doesn't makes sense... I'm using Union Find to solve this problem, I use both union by rank and path compression, I tried to optimize the algorithm as much as I could, but I still get TLE! The only thing I can see that's making this slower is Java, but there have been some Accepted's with Java already, so it can't be impossible...
I'll leave the code here, I thing it's really easy to understand, so if anyone could see if there's anything I'm doing wrong, please help me, I'm getting crazy with this problem...

Code: Select all

import java.util.Scanner;

public class UbiquitousReligions {


  private static int[] rank = new int[50000], parent = new int[50000];
  private static int nSets;
  private static int[] stack = new int[10]; /*used as a simple stack for the path compression 
                                             enhancement of the union find algorithm. Since
                                             the rank of the sets will never be greater
                                             than 5 (thanks to path compression itself), 
                                             10 is big enough to store the whole stack.*/
  
  private static void makeSet(int maxNodes) {
    nSets = maxNodes;
    for (int i = 0; i < maxNodes; i++)
      parent[i] = i;
  }
  
  private static void union(int x, int y) {
    int xParent = findSet(x);
    int yParent = findSet(y);
    if (xParent != yParent) {
      link(xParent, yParent);
      nSets--;
    }
  }

  private static void link(int x, int y) {
    if (rank[x] > rank[y]) {
      parent[y] = x;
    } else {
      parent[x] = y;
      if (rank[x] == rank[y])
        rank[y]++;
    }
  }
  
  private static int findSet(int x) {
    int count = 0;
    while (x != parent[x]) {
      stack[count++] = x;
      x = parent[x];
    }
    while(--count > 0)
      parent[stack[count]] = x;
    return x;
  }
  
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long m;
    int x, y, n, caseNumber = 0;
    while ((n = sc.nextInt()) != 0 && (m = sc.nextLong()) != 0) {
      makeSet(n);
      for (long i = 0; i < m; i++) {
        x = sc.nextInt();
        y = sc.nextInt();
        x--;
        y--;
        union(x,y);
      }
      caseNumber++;
      System.out.println("Case " + caseNumber + ": " + nSets);
    }
  }
}

[mf]

Scanner class is very slow. It just can't parse all the input (which is about 6 Mb in this problem) in time. You should use something else, e.g. StreamTokenizer.

And please don't create a new topic, if there already exists another thread for a problem.

[skulty]

Oh, sorry about that, first time in this forum... But thanks about the advise, I'll try that, it makes sense...

[skulty]

Can't believe it... You were right, I used a BufferedReader, made splits in the Strings and used parseInt's instead of simply using a Scanner and I got Accepted with 1.6 seconds... It's not a marvelous timing, but for Java it's good enough... Thanks, it's really boring when you're sure you're using the right algorithm and still you can't make it go fast enough, but your tip did the trick, thanks a lot...

P.S: I didn't use StreamTokenizer because I made the changes without access to the internet and I didn't remember what you had sugested, but I'll try it now to see which way is better...

[skulty]

Yep, StreamTokenizer got me an Accepted in 0.9 seconds, unbelievable, I never would've thought that scanning the input could make such a difference, but from now on, whenever I see a problem where the input might be enormous, I'll use StreamTokenizer instead of Scanner... For the last time (in this thread, at least), thank you...