10887 - Concatenation of Languages

[Raj Ariyan]

Hi all,
I want to know how i solve this problem by using Hash. Without hashing is it solvable ? Thanks in advance.

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

[liulike]

I got TLE again and again...

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

[liulike]

AC !!


thank you all!

ftftft

[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

[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

[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]++;
        }
}

[mf]

My program (currently the fastest on the ranklist) takes 6.5 sec on my Pentium-II 400.

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

[mf]

Could you show your code?

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

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

[jdmetz]

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());
	}
}

[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;
}