10887 - Concatenation of Languages

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by jdmetz » Mon Aug 08, 2005 5:55 pm

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

Post by Pupirev Sergei » Mon Aug 08, 2005 8:13 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?

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Mon Aug 08, 2005 10:26 pm

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:

Post by mf » Tue Aug 09, 2005 4:45 am

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

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Tue Aug 09, 2005 4:13 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:

Post by mf » Tue Aug 09, 2005 5:35 pm

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

Post by windows2k » Wed Aug 10, 2005 5:52 am

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.

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Thu Aug 11, 2005 2:13 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

how about this data?

Post by wook » Thu Aug 11, 2005 4:58 pm

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?


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

Post by jdmetz » Thu Aug 11, 2005 5:03 pm

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:

Post by mf » Thu Aug 11, 2005 7:52 pm

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

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

WA in 10887

Post by Riyad » Fri Aug 12, 2005 4:15 pm

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

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

Post by Riyad » Fri Aug 12, 2005 4:18 pm

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

Post by Emilio » Fri Aug 12, 2005 11:14 pm

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

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

Post by Riyad » Mon Aug 15, 2005 5:34 am

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

Post Reply

Return to “Volume 108 (10800-10899)”