## 10887 - Concatenation of Languages

Moderator: Board moderators

jdmetz
New poster
Posts: 25
Joined: Fri May 27, 2005 5:23 pm
Location: Ann Arbor, MI USA
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
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm
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
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am
jdmetz
you were right. I never noticed this subtle point. mine also times out! thining of better ways to hash.
bye
abishek

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

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
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?
Jalal : AIUB SPARKS

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

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
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.

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
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!!!
Jalal : AIUB SPARKS

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Hi, i wrote a program based on prefix-suffix,

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)

and
if n =0 or m = 0,

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

then C={a,b,c,d}

is it wrong?

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

Sorry For My Poor English..

jdmetz
New poster
Posts: 25
Joined: Fri May 27, 2005 5:23 pm
Location: Ann Arbor, MI USA

### try this

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
wook wrote:if n =0 or m = 0,
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
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

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### WA in 10887

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 ;
}
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:
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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
I parse the input in the same form as you.
And I got AC.
I think that is not your problem