10583 - Ubiquitous Religions

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

Moderator: Board moderators

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Post by N|N0 » Thu Jun 02, 2005 9:34 pm

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.

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Post by N|N0 » Thu Jun 02, 2005 9:36 pm

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

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Thu Jun 02, 2005 11:11 pm

N|N0 wrote:The official input also includes a pair where i = j, so a pair of the same student who believes in his own religion. Beware! :wink:
Seems that you have had some serious bad experiences with this test case ! :wink: OK, If you use the standard union-find or DFS (correctly implemented, off course :D ) algorithm to solve this problem, why should this case i==j create any problem at all ?
You should never take more than you give in the circle of life.

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Post by N|N0 » Thu Jun 02, 2005 11:52 pm

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 :roll:

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Fri Jun 03, 2005 12:13 am

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. :)
You should never take more than you give in the circle of life.

Ashganek
New poster
Posts: 8
Joined: Thu Jan 19, 2006 10:42 pm

10583 - Runtime Error :(

Post by Ashganek » Thu Jan 19, 2006 10:46 pm

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 :P) 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
New poster
Posts: 8
Joined: Thu Jan 19, 2006 10:42 pm

Post by Ashganek » Fri Jan 20, 2006 12:56 am

Ok, I made it using other way :)

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

Post by renato_ferreira » Wed Jun 27, 2007 2:07 am

Hello, I don't understand why WA:

Code: Select all

Accepted
Last edited by renato_ferreira on Fri Jun 29, 2007 12:52 am, 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 Jun 28, 2007 2:06 pm

Your code doesn't even pass the samples. Check carefully. :wink:
Ami ekhono shopno dekhi...
HomePage

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

Post by renato_ferreira » Fri Jun 29, 2007 12:53 am

Thank you very much, AC =)

skulty
New poster
Posts: 4
Joined: Fri Dec 07, 2007 5:38 pm

10583 -> Union Find -> TLE?!?!

Post by skulty » Fri Dec 07, 2007 6:12 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Dec 07, 2007 6:39 pm

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
New poster
Posts: 4
Joined: Fri Dec 07, 2007 5:38 pm

Post by skulty » Fri Dec 07, 2007 8:36 pm

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

skulty
New poster
Posts: 4
Joined: Fri Dec 07, 2007 5:38 pm

Post by skulty » Sat Dec 08, 2007 1:39 am

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... :o 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... :D

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
New poster
Posts: 4
Joined: Fri Dec 07, 2007 5:38 pm

Post by skulty » Sat Dec 08, 2007 3:02 am

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...

Post Reply

Return to “Volume 105 (10500-10599)”