Page 2 of 4

Posted: Mon Aug 08, 2005 5:55 pm
by jdmetz
abishek,

I figured it out - for at least one case, the first word in the first language is of length 0 - an emtpy line. scanf reads all whitespace when it encounters a space, tab, or newline in the format string, so we were skipping that new line.

I changed this part of my code:

Code: Select all

        scanf("%d %d ", &m, &n);
to

Code: Select all

        gets(sz);
        sscanf(sz, "%d %d", &m, &n);
and increased the size of sz to 100.

Now mine times out like it should.

Posted: Mon Aug 08, 2005 8:13 pm
by Pupirev Sergei
Someone who got AC, how fast does your program run on the input produced by this program?
My program (currently the fastest on the ranklist) takes 6.5 sec on my Pentium-II 400.
My program is currently the second on the ranklist ;) And it runs < 0.1 sec. on this test.
My program's complexity is about O(n*m*10). It's intresting to know is it possible to solve it faster?

Posted: Mon Aug 08, 2005 10:26 pm
by abishek
jdmetz
you were right. I never noticed this subtle point. mine also times out! thining of better ways to hash.
bye
abishek

Posted: Tue Aug 09, 2005 4:45 am
by mf
Pupirev Sergei wrote:My program is currently the second on the ranklist And it runs < 0.1 sec. on this test.
My program's complexity is about O(n*m*10). It's intresting to know is it possible to solve it faster?
Oh, yes, it is!
My new program uses sorting and binary search. Its complexity quite depends on the input. It is O(N) for inputs, like the one generated by jdmetz's program.

Hint: think, of what form can all duplicate concatenations be. (think about prefixes, suffixes, etc.)

Posted: Tue Aug 09, 2005 4:13 pm
by CodeMaker
hi mf, i have thought about the prefix-suffix approch during the contest time. but i thought its complexity will be more and i moved to hashing.

have u solved it using prefix-suffix?

Posted: Tue Aug 09, 2005 5:35 pm
by mf
CodeMaker wrote:have u solved it using prefix-suffix?
Yes, that's the approach I used in the program, which currently (again) holds the first place in the ranklist.
It has O(N) complexity only in some very special cases -- when the first language is given sorted and no string is a prefix of another one.
In the worst case, my program is O(N^2 M log M), but this complexity can occur only when the length of the longest word is near N.

During the contest I solved the problem by hashing.

Posted: Wed Aug 10, 2005 5:52 am
by windows2k
Pupirev Sergei wrote: My program is currently the second on the ranklist ;) And it runs < 0.1 sec. on this test.
My program's complexity is about O(n*m*10). It's intresting to know is it possible to solve it faster?
Does you use trie tree to solve the problem?
It looks the complexity is O(n*m*length)
I use trie tree to solve the problem, but get TLE
I don't know what's wrong with my thought.
Thx in advance.

Posted: Thu Aug 11, 2005 2:13 pm
by CodeMaker
thats great mf, i will try to solve it using that approch.
i just checked the ranklist, its unbelievable, ur timing and memory is just great!!!

how about this data?

Posted: Thu Aug 11, 2005 4:58 pm
by wook
Hi, i wrote a program based on prefix-suffix,

but i got wrong answer.

input:
4
7 2
abc
g
aa
bb
c
ca
a
c
ac
1 1


0 0
0 1
f
output:
Case 1: 12
Case 2: 1
Case 3: 0
Case 4: 1

if, n=0 and m=0,

the set C = {} (i.e. empty set)

thus, answer is 0


and
if n =0 or m = 0,
answer is n+m

for example,
A = {} (empty set)
B = {a,b,c,d}

then C={a,b,c,d}
thus answer is 4


is it wrong?
i've already noticed about blank lines

or... please give me a tricky data or LARGE data?


:)

try this

Posted: Thu Aug 11, 2005 5:03 pm
by jdmetz
Input

Code: Select all

1
7 7

a
aa
aaa
aaaa
aaaaa
aaaaaa

a
aa
aaa
aaaa
aaaaa
aaaaaa
Output

Code: Select all

Case 1: 13

Posted: Thu Aug 11, 2005 7:52 pm
by mf
wook wrote:if n =0 or m = 0,
answer is n+m
No, if N=0 or M=0, the answer should be 0.

More test cases:

Code: Select all

9
3 3

a
b

a
b
2 2
a
aa
a
aa
3 3
a
ab
abc
bcd
cd
d
5 7
a
ab
abc
abcd
abcde
bcde
cde
de
e

defg
dxyz
5 5
a
aa
aab
abc
ad
a
ab
b
bc
cd
0 0
1 1
a
b
0 1
a
1 0
b

Output:

Code: Select all

Case 1: 7
Case 2: 3
Case 3: 7
Case 4: 31
Case 5: 24
Case 6: 0
Case 7: 1
Case 8: 0
Case 9: 0

WA in 10887

Posted: Fri Aug 12, 2005 4:15 pm
by Riyad
hi everybody ,
i am getting wa in this problem ... i guess i am having trouble parsing the input .....this is how i parse my input .....could anyone tell me if there is anything wrong .if there is no problem in parsing input i may forced to paste my code here ..................

Code: Select all

# define PRED 4999 // prime
char a[2000][30];
int main(){
	int test , t ;
	int i , j ;
	char buff[100000],tool[1000];
	int counter ; 
	gets(buff);
	sscanf(buff,"%d",&test);
	//scanf("%d",&test);
	for(t=1;t<=test;++t){
		
		gets(buff);
		sscanf(buff,"%d %d",&m,&n);
		//scanf("%d%d",&m,&n);
		//while(getchar()!='\n');
		for(i = 0; i < PRED + 8 ;++i)hash_table[i].d.clear() ;
		for(i = 0 ;i < m ;++i)gets( a[i] );
		counter = 0 ;
		for(i = 0 ;i < n ;++i){
			gets(buff);
			for(j = 0; j < m ;++j){
				strcpy(tool , a[j]);
				strcat(tool , buff);
				unsigned int hash = APHash( tool );
				if( hash_find( hash , tool ) )continue ;
				++counter ;
				hash_table[hash].d.push_back( tool );
			}
		}
		printf("Case %d: %d\n",t,counter);
	}
	return 0 ;
} 
thanx in advance :(

Posted: Fri Aug 12, 2005 4:18 pm
by Riyad
i forgot to mention one thing in my previous post ........my code passes all the test cases available in this topic given by people who have got ac in this problem.............
happy coding

Posted: Fri Aug 12, 2005 11:14 pm
by Emilio
I parse the input in the same form as you.
And I got AC.
I think that is not your problem :D

Posted: Mon Aug 15, 2005 5:34 am
by Riyad
thanx for the reply Emilio ...i am releived to know i am not making any mistake while taking input . can some one give me some more i/o ....or i can paste my code here ...............pliz help... :cry:
thanx in advance