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

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

10887 - Concatenation of Languages

Post 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.
Some Love Stories Live Forever ....

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

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

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

Post by liulike »

I got TLE again and again...

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

Post by liulike »

AC !!


thank you all!

ftftft

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

any tricky cases?

Post 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

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

Post 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

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

how fast?

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

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

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

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

Could you show your code?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post 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.
Ami ekhono shopno dekhi...
HomePage

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

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

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

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

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

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


Post Reply

Return to “Volume 108 (10800-10899)”