## 10583 - Ubiquitous Religions

Moderator: Board moderators

N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:
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
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:
The official input also includes a pair where i = j, so a pair of the same student who believes in his own religion. Beware!

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
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!
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 ?
You should never take more than you give in the circle of life.

N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:
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

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
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 :(

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
New poster
Posts: 8
Joined: Thu Jan 19, 2006 10:42 pm
Ok, I made it using other way

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm
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
Contact:
Your code doesn't even pass the samples. Check carefully.
Ami ekhono shopno dekhi...
HomePage

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm
Thank you very much, AC =)

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

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

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) {
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:
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.

skulty
New poster
Posts: 4
Joined: Fri Dec 07, 2007 5:38 pm
Oh, sorry about that, first time in this forum... But thanks about the advise, I'll try that, it makes sense...

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