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 » Sun Aug 07, 2005 6:30 am

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

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

Post by A1 » Sun Aug 07, 2005 9:19 am

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 » Mon Aug 08, 2005 3:39 am

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 » Mon Aug 08, 2005 3:49 am

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 » Mon Aug 08, 2005 3:54 am

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 » Mon Aug 08, 2005 4:49 am

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 » Mon Aug 08, 2005 5:08 am

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 » Mon Aug 08, 2005 5:10 am

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 » Mon Aug 08, 2005 6:40 am

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

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

Post by abishek » Mon Aug 08, 2005 8:20 am

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 » Mon Aug 08, 2005 8:41 am

Could you show your code?

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

Post by Jan » Mon Aug 08, 2005 10:00 am

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

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

Post by Dreamer#1 » Mon Aug 08, 2005 10:03 am

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 » Mon Aug 08, 2005 2:41 pm

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

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

Post by abishek » Mon Aug 08, 2005 3:41 pm

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