Page 1 of 4

10887 - Concatenation of Languages

Posted: Sun Aug 07, 2005 6:30 am
by Raj Ariyan
Hi all,
I want to know how i solve this problem by using Hash. Without hashing is it solvable ? Thanks in advance.

Posted: Sun Aug 07, 2005 9:19 am
by A1
You need an efficient hashing implementation to solve it!
stl map can not solve it in 4s, so in realtime it gets TLE, but may be offtime will get Ac.

Posted: Mon Aug 08, 2005 3:39 am
by liulike
I got TLE again and again...

Posted: Mon Aug 08, 2005 3:49 am
by mf
Why don't you describe the algorithm you're using?
Are you parsing the input properly? Did you consider that the languages may have empty words?

Posted: Mon Aug 08, 2005 3:54 am
by liulike
AC !!


thank you all!

ftftft

any tricky cases?

Posted: Mon Aug 08, 2005 4:49 am
by jdmetz
Are there any tricky cases? I'm getting WA after ~2.2s rather than TLE.

Here are my current test cases, which are fairly trivial to verify by hand:

input:

Code: Select all

7
3 2
cat
dog
mouse
rat
bat
1 1
abc
cab
5 5
a
aa
aab
abc
ad
a
ab
b
bc
cd
3 3
a

b
a

b
0 0
1 1
a
b
10 0
a
b
c
d
e
f
g
h
i
j
output:

Code: Select all

Case 1: 6
Case 2: 1
Case 3: 24
Case 4: 7
Case 5: 0
Case 6: 1
Case 7: 0

Posted: Mon Aug 08, 2005 5:08 am
by liulike
My output is as follow:

Code: Select all

Case 1: 6
Case 2: 1
Case 3: 24
Case 4: 7
Case 5: 0
Case 6: 1
Case 7: 0

how fast?

Posted: Mon Aug 08, 2005 5:10 am
by jdmetz
Someone who got AC, how fast does your program run on the input produced by this program?

Code: Select all

#include <stdio.h>

main() {
        int i, j;

        char sz[11] = "aaaaaaaaaa";

        puts("1\n1500 1500");

        for (i = 0; i < 3000; i++) {
                puts(sz);
                j = 9;
                while (sz[j] == 'z') sz[j--] = 'a';
                sz[j]++;
        }
}

Posted: Mon Aug 08, 2005 6:40 am
by mf
My program (currently the fastest on the ranklist) takes 6.5 sec on my Pentium-II 400.

Posted: Mon Aug 08, 2005 8:20 am
by abishek
I keep getting WA. I do the following
I assume first tht theere are no extra blank lines in input.
then I just consider each test case, and find the mxn possible strings and store them in a set.
I consider empty strings and I use gets to parse the input.
finally I output the size of this set. I don't know where I am wrong.
I don't see why someone needs to use the stl map. stl set is good enough for this problem I think.

Posted: Mon Aug 08, 2005 8:41 am
by mf
Could you show your code?

Posted: Mon Aug 08, 2005 10:00 am
by Jan
Try the input output set...

Input:

Code: Select all

1
3 2
cat
c
ca
at
t
Output:

Code: Select all

Case 1: 5
Hope it helps.

Posted: Mon Aug 08, 2005 10:03 am
by Dreamer#1
I don't see why someone needs to use the stl map. stl set is good enough for this problem I think.
I am afraid stl set isn't fast enough for this problem. I did a simple bit of hashing to get AC with a poor timing (7 sec). May be I'll try something better later on for a better timing.

Posted: Mon Aug 08, 2005 2:41 pm
by jdmetz
mf wrote:Could you show your code?
Ok, as it gets WA and would be too slow otherwise, I will.

Code: Select all

#include <cstdio>
#include <vector>
#include <string>
#include <set>

using namespace std;

main() {
	char sz[11];
	int T, cs = 0;
	
	scanf("%d ", &T);
	while (T--) {
		int m, n;
		
		vector<string> a, b;
		
		scanf("%d %d ", &m, &n);
		for (int i = 0; i < m; i++) {
			gets(sz);
			a.push_back(sz);
		}
		for (int i = 0; i < n; i++) {
			gets(sz);
			b.push_back(sz);
		}
		
		set<string> st;
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				st.insert(a[i]+b[j]);
		}
		
		printf("Case %d: %d\n", ++cs, st.size());
	}
}

Posted: Mon Aug 08, 2005 3:41 pm
by abishek
Almost similar code.

Code: Select all


#include <stdio.h>
#include <string>
#include <set>
#include <iostream>
using namespace std;

set<string> first;
set<string> final;

int main()
{
    int t, cano=0;
    scanf("%d\n", &t);
    while(t--)
    {
        int m, n;
        string inp;
        scanf("%d %d\n", &m, &n);
        first.clear();
        final.clear();
        for(int i=0; i<m; i++)
        {
            getline(cin, inp);
            first.insert(inp);
        }
        set<string>::iterator st, en;
        for(int j=0; j<n; j++)
        {
            getline(cin, inp);
            for(st=first.begin(), en=first.end(); st!=en; st++)
            {
                final.insert(*st+inp);
            }
        }
        printf("Case %d: %d\n", ++cano, final.size());
    }
    return 0;
}