OJ Board

[cpp]
for(y=0;y<m;y++)
{
scanf("%s",str);
for(u=0;u<n;u++) if(strcmp(name,str)==0) break;
scanf("%s",str);
for(v=0;v<n;v++) if(strcmp(name[v],str)==0) break;
fu=find(u);
fv=find(v);
if(fu==fv) continue;
link(fu,fv);
}
[/cpp]
It's simply too slow - it's possible that you do n*m strcmp calls (so with n=m=5000 it will probably get TLE...). Use map (or sort names and use binary search...).
[/cpp]

I have got it. Thanks.

In pure C, you can use binary search. (Or bsearch, if you like it that way.)

anupam wrote:

What I got after accepted is that, In pure C you will get TLE. By using STL and MAP you can get accepted in a very short time.

I don't think that the idea of the problemsetter should be to test whether you know STL or not. So, not a good problem I can say. The problemsetter should think about the case in every language if possible.

I checked and seen that without implementing the union find algorithm, just to build a separate graph and to take the input my program got TLE. Mapping is not so flexible in C.

By now it is clear that the problem description was misleading but after knowing all that from the board there is absolutely no reason why one should have made such comments. STL does make coding a lot easier but ofcourse there is almost everything you can do with pure C just as fast as using STL. When you know exactly what you've to do in this problem there is no reason why you would need more than 20-30 min for coding a decent solution that would run within half a second or so. And missing out on doing that task properly instead you've criticised the problemsetter for some... God knows how to sum up your reasoning... (!)

I thought I'd have some fun with hashing..I've tested it on my computer with no problems, but judge says Runtime error (SIGSEV) ??

[c]
#include <stdio.h>
#include <stdlib.h>

#define MOD_PRIME 99991

typedef struct node node;
struct node {
node *cdr;
node *end;
int ind;
char name[31];
};

int roots[5000],n,m;
int sizes[5000];
node names[5000];
char a[31],b[31];
node *list[MOD_PRIME];
int primes[30] = {127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,
233,239,241,251,257,263,269,271,277,281};

int find_set(int a) {
if (a!=roots[a]) roots[a] = find_set(roots[a]);
return roots[a];
}

int hash(char *a) {
int ret=0,i,len=strlen(a);
for (i=0;i<len;i++) ret += primes*(a-'a');
return ret%MOD_PRIME;
}

int lookup(char *a) {
int mhash = hash(a);
node *n = list[mhash];
while (strcmp(n->name,a)) n = n->cdr;
return n->ind;
}

int main() {
int i;
while (1) {
int mhash,la,lb,best=1,temp;
scanf("%d %d",&n,&m);
if (n+m==0) break;
for (i=0;i<MOD_PRIME;i++) list = NULL;
for (i=0;i<n;i++) {
scanf("%s",names.name);
mhash = hash(names.name);
names.cdr = NULL;
names.end = &names;
roots = names.ind = i;
sizes[i] = 1;
if (list[mhash]==NULL) list[mhash] = &names[i];
else { list[mhash]->end->cdr = &names[i]; list[mhash]->end = &names[i]; }
}
for (i=0;i<m;i++) {
scanf("%s %s",&a,&b);
la = find_set(lookup(a)); lb = find_set(lookup(b));
if (la==lb) continue;
else {
if (sizes[la] > sizes[lb]) { roots[lb] = la; temp=(sizes[la] += sizes[lb]); }
else { roots[la] = lb; temp = (sizes[lb] += sizes[la]); }
best = (best>temp) ? best : temp;
}
}
printf("%d\n",best);
}
exit(0);
}
[/c]

[EDIT]
PS: To whoever said this problem is not do'able in pure C...
If it isn't, how did I get #6 on ranklist from doing it in C
[/EDIT]

Good statements from kuegel and the probsetter. So, one hint is that, it canbe easily implemented by a binary search.

So, now the problem is easy. I request admin to put a notification that the time limit has been changed.

I am sorry if I misunderstood. Thanks for help and reply. Keep posting.

If the main idea is to test Mapping capability, then it is ok, I am wrong. Otherwise, I am ok in my view.

And, I don't mantion any word about problem statements. So, don't include that.

If it seems ok to you, then you made it easy to me to introduce a lot of problems of combination of algorithms:-)

Anyone tried with binary search trees?
NB: I didn't mantion that, it will not doable in C. Itold to think about the case in every languages.

Anupam, I think you are wrong.
It is very easy to program a fast and short solution in C, and you need no special knowledge. As mentioned by Larry before, sorting and binary search is sufficient (you can even use qsort, bsearch and strcmp to do all the work for you).
My program has 51 lines without trying to make it as short as possible, and takes 0:00.574 time at the judge.

Hi!

I was the problemsetter for this. While I was writting the problem, my idea is to create a SET problem, so I've put the time limit to 40s (and this is very much time, cause I've tested a linear search on a P2-233Mhz).

On the online contest it is a bad idea to have such a big time limit. I've learn this because the queue on the judge was very big.

So, this problem has become a SET and MAP, or a SET and SORT problem.

When I first write it, many people thought of it as a PATH problem. Then I've changed the description a bit to make sure people would think of it as a SET problem.

JP.

Hi, someone plz help me in finding the error in my code......i have no idea what's wron......

you do this:

[c]
void makeset(int x,int y)
{
if(!set[y])
set[y]=x;
else
makeset(x,set[y]);
}
[/c]

but then do this

[c]
j=bin_s(0,c-1,temp1);
k=bin_s(0,c-1,temp2);
j++;
k++;
if(find1(j)!=find1(k))
{
makeset(j,k);
}
[/c]

what if j==0? then the next time make_set gets called with k,
it will think k has no set. maybe you should do
memset(set,-1,sizeof(set));
instead of memset(set,0,sizeof(set));
since -1 can never be a valid index.

another bug..
do bin_s(0,c,temp1) and bin_s(0,c,temp2) instead of c-1.
otherwise, you'll never find something if it's in list[c-1].

these are the first two bugs I found..I haven't looked through
the rest very carefully, but i hope this helps.

good luck

PS. If you have time, please look at my code up above o_O
it's segfaulting and I have no idea why T.T

Hi Thanks a lot for ur reply...

ok, I think u had a quick view on my code (ofcourse who wants to waste time on other's junk when we have our own dying problems )
but still some people kind like u reply...

Well I think, these may not be the bugs, ofcourse there is something wrong in my code(or may not may be judge data is wrong ).

acctually I have used a different type of binary search( as i m not so good with it ) my last element is list[c-1], there is nothing in list[c] as i m indexing from list[0] not from list[1]. And dont worry about it...because if my bin_s() cant find the match then it will die in the infinite recursion as i kept no termination condition for no found and will cause run time error.
I also checked about finding the last element, and it gets it.

and another part, u know this is a set union problem. i just need some valid indexes to make the set, from bin_s i will get same result for all same input and it will be from 0 to c-1. and plz notic that after i find 'j' and 'k' from bin_s, i shift the value by 1, so 0 become 1, 4 become 5, c-1 become c , then making set...

Acctually while solving the "friends" problem (up in this volume)which is 100% similar to this one, i had a lot of checks on set-unions,and had to modify my algo about sets. i have also checked in this problem with different values...i m trying to make my own code fool but it is not falling in my trap i hope people here will give me better traps

ok , now lets talk about ur code......u know, i have little knowledge on hashing(truely i dont understand hashing ), so at first i thought i have no use in ur problem and was going to turn over my eyes from ur code, suddenly something caught my eyes- that is the size of ur arrays.
one big reasons for runtime error is small size of arrays(look how big mine r ) for the name it will take 30 characters, so 31 is ok(i dont trust them ) but there will be <=5000 entries. if u index from 0 its ok, but then be sure that u r doing it everywhere, because if u shift from 1 to c then array[5000] will cause crush as there is at max array[4999]. I always use array[MAX+1] to avoid such mistakes, u also can try

if u think it will not happen still have a try with some bigger limits of array after u get run time(always),another thing- u use "typedef" before the structure, i use it after. it may work, but may not in some compilers ....i can't help more i dont know how to use hash thank u for ur reply, plz reply again... and sorry if i wrote something wrong , u know i m a little forget it

Hi, here is some I/O from my code....i think it is ok, then why wrong answer....can anyone give me something new to try out [c]Input:
5 5
a b c d e
a c
b d
e a
c d
b c

10 3
a b c d e f g h i j
a j
a f
j f

3 1
a b c
c b

5 3
a b c d e
a b
a c
a d

4 2
a
b
c
d
a c
b d

3 3
a
b
c
a b
c b
a c

8 7
a b c d e f g h
a b
a c
a d
a e
a f
a h
a g

9 0
a b c d e f g h i

1 0
a

4 6
a b c d
a b
a c
a d
a b
a c
c d

7 3
a
b
c
d
e
f
g
c e
e f
d e

2 1
a
f
a f

10 9
a b c d e f g h i j
b a
c a
d a
e a
f a
g a
h a
i a
j a

0 0

output:
5
3
2
4
2
3
8
1
1
4
4
2
10
[/c]

acctually I have used a different type of binary search( as i m not so good with it ) my last element is list[c-1], there is nothing in list[c] as i m indexing from list[0] not from list[1].

I know that your array is 0-indexed. high should still be set to c
and not c-1 (i know that there is nothing in list[c], but high should
be set to 1 greater than the last index that contains something).
If the match is in list[c-1] you will get an infinite loop.

Furthermore:

and another part, u know this is a set union problem. i just need some valid indexes to make the set, from bin_s i will get same result for all same input and it will be from 0 to c-1. and plz notic that after i find 'j' and 'k' from bin_s, i shift the value by 1, so 0 become 1

It doesn't matter that you increase it by 1 *afterwards*. During the function itself, if the canonical element of the set containing y is the element of index 0, your makeset function will think y has no set and reset it incorrectly.

My submission for this that got AC is very similar to your solution (binary search), so I am familiar with what you are trying to do. I am just trying to do it with hashing now because I was curious to see whether it was faster or not. :/

hi codemaker,

well.. the 1st thing that i saw wrong in your code was infact the only mistake... though its not the most ideal way to code and kinda less efficient but still its acceptable...

ok now about ur mistake,

i know there r teachers in aiub who teaches students that strcmp() returns -1 if the 1st string is lexographically smaller than the 2nd one and returns 1 for the opposite case but this is absolutely rubbish ... it returns a negative value and not necessarily -1 in the 1st case and in the 2nd case it returns a positive value and not 1... i hope now u know what to correct in your code... sorry about the rude words about our teachers but u know its really sad that a few of our teachers know so little... but ofcourse not most of them... we'r again truly lucky to have some1 as great as kamruzzaman sir this man is truly a genius

anyway... well done, we're happy about ur last online contest performance... keep it up... but u shudn't have missed "C" like we did.. it was such a simple sorting problem... we should have solved 7... bad miss... well therez always a next time...

best of luck and wish me luck to,

-Dreamer

Hi dreamer #1 I got accepted after changing it to ">0" / "<0" , i cant believe that this thing got me...... , well u know, after i solved 3( i should have solved C and the one with infix postfix, but i got in panic and failed) , i looked for the 1st round problems(i missed it) i took it as a contest and solved 2 of them in 2 hour( jackpot && decimal watch) and moved to it but this thing got me. if i anttened 1st round then i had 2 solved and if that bad thing didn't got me then 3.....yup, i think these contests r the easiest...still u did well by solving 6...

Thanks everybody who tried to help me in this problem......