10887 - Concatenation of Languages

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

[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?

[abishek]

jdmetz
you were right. I never noticed this subtle point. mine also times out! thining of better ways to hash.
bye
abishek

[mf]

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

[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?

[mf]

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.

[windows2k]

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.

[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!!!

[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?

[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

[mf]

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

[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

[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

[Emilio]

I parse the input in the same form as you.
And I got AC.
I think that is not your problem

[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...
thanx in advance