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

User avatar
[_TANG_]
New poster
Posts: 15
Joined: Wed May 04, 2005 12:28 am
Location: Mexico

10887 - Don't understand

Post by [_TANG_] » Fri Nov 18, 2005 12:16 am

Hi,

Can anyone tell me why does the input:

Code: Select all

1
3 3
a

b
a

b
outputs:

Code: Select all

Case 1: 7
Think that's why I can't get AC ... :cry: ... My code output is 6

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Fri Nov 18, 2005 10:07 am

I should think the concatenated words are
  • 1. aa
    2. a
    3. ab
    4.
    5. b
    6. ba
    7. bb
I couldn't get it accepted either, TLE. :(

User avatar
[_TANG_]
New poster
Posts: 15
Joined: Wed May 04, 2005 12:28 am
Location: Mexico

Strange :-?

Post by [_TANG_] » Fri Nov 18, 2005 7:15 pm

Hello,

I've a strange problem, when I debug my code with an input containing empty strings (hardcoded) its output is correct but if I try to run my code at console like this:
code.exe < input.txt > output.txt
Doesn't recognize the empty string ... I think is because of this:

Code: Select all

cin >> A >> B;

		if(A && B)
		{
			count = 0;

			for(d = 0; d < A; d++)
				cin >> vectorA[d];

			for(d = 0; d < B; d++)
				cin >> vectorB[d];

...
I read from input and copy into an array the languages then I find the count of different words.

Is there other way to catch the input and recognize the empty string?

Thnx.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Fri Nov 18, 2005 10:40 pm

cin skips whitespaces unless skipws flag is off.

Soarer
New poster
Posts: 14
Joined: Wed Nov 09, 2005 8:17 pm

Re: 10887 - Don't understand

Post by Soarer » Sat Nov 19, 2005 3:55 pm

[_TANG_] wrote:Hi,

Can anyone tell me why does the input:

Code: Select all

1
3 3
a

b
a

b
outputs:

Code: Select all

Case 1: 7
Think that's why I can't get AC ... :cry: ... My code output is 6
why is this a valid input?

You can assume that the strings are formed by lower case letters (

Soarer
New poster
Posts: 14
Joined: Wed Nov 09, 2005 8:17 pm

Post by Soarer » Sat Nov 19, 2005 4:46 pm

By the way, I need some i/o as well.. thanks.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10887 - Don't understand

Post by Martin Macko » Sat Dec 10, 2005 4:17 pm

[quote="Soarer"]why is this a valid input?

You can assume that the strings are formed by lower case letters (

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Dec 10, 2005 4:27 pm

Soarer wrote:By the way, I need some i/o as well.. thanks.
input:

Code: Select all

5
20 20
aaaaaaaaaa
aaaaaaaaa
aaaaaaaa
aaaaaaa
aaaaaa
aaaaa
aaaa
aaa
aa
a
baaaaaaaaa
baaaaaaaa
baaaaaaa
baaaaaa
baaaaa
baaaa
baaa
baa
ba
b
aaaaaaaaaa
aaaaaaaaa
aaaaaaaa
aaaaaaa
aaaaaa
aaaaa
aaaa
aaa
aa
a
aaaaaaaaab
aaaaaaaab
aaaaaaab
aaaaaab
aaaaab
aaaab
aaab
aab
ab
b
2 2
gas

gadf

1 1


1 1
a
a
5 1
gfegtwg
wgtwgtrweg
trwgtrwg
trwgrwg
trwgtgg
trwgtgg
output:

Code: Select all

Case 1: 76
Case 2: 4
Case 3: 1
Case 4: 1
Case 5: 5

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 10887 - Concatenation of Languages

Post by Jehad Uddin » Tue Aug 04, 2009 10:40 am

i have got ac,using set,bt its too slow,any faster idea??

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

10887 - Concatenation of Languages

Post by sazzadcsedu » Fri Apr 30, 2010 1:17 pm

I submitted the following algorithm but got TLE. How can i improve running time .someone plz help.Is stl map not enough???
here my code

Code: Select all


 Acc.
Using set instead of using map got Acc.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10887 - Concatenation of Languages

Post by Shafaet_du » Fri Jun 10, 2011 9:30 pm

getting tle after tle :(. I tried trie. I dont know how to write hash function yet.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Re: 10887 - Concatenation of Languages TLE

Post by nymo » Mon Jun 20, 2011 4:05 pm

As some posters said that it is possible to get AC with stl set. I am getting tle... I wonder how they did that...
regards,
nymo

Karcher
New poster
Posts: 2
Joined: Fri Nov 04, 2011 10:42 am

Re: 10887 - Concatenation of Languages

Post by Karcher » Wed Nov 09, 2011 2:01 pm

i got quite curious about this issue (getting AC with stl set), but found no exact answer. Is cell phone spy anybody in the know?
Last edited by Karcher on Wed Feb 15, 2012 8:35 am, edited 1 time in total.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 10887 - Concatenation of Languages

Post by plamplam » Tue Jan 03, 2012 11:09 am

I got Accepted with STL map, just don't use cin/getline, use gets() you should pass the Time Limit.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

hpjhc
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

10887 - Concatenation of Languages WA

Post by hpjhc » Sat Sep 14, 2013 12:11 pm

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;

int hash(string );
int insert(int );
string st1[1510], st2[1510];
int head[1000003], next[2250010];
string queue[2250010];

int main(void)
{
int t, a, b, i, j, k, cnt = 0;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &a, &b);
for(i = 0; i < a; i++)
cin>>st1;
for(i = 0; i < b; i++)
cin>>st2;
k = 1;
memset(head, 0, sizeof(head));
memset(next, 0, sizeof(next));
for(i = 0; i < a; i++)
for(j = 0; j < b; j++)
{
queue[k] = st1+st2[j];
if(insert(k))
k++;
}
printf("Case %d: %d\n", ++cnt, k-1);
}
return 0;
}

int hash(string str)
{
int hash = 0, seed = 31;
for(int i = 0; i < str.size(); i++)
hash = hash*seed+str;
return (hash & 0x7fffffff) % 1000003;
}

int insert(int s)
{
int h = hash(queue[s]);
int u = head[h];
while(u)
{
if(queue == queue[s])
return 0;
u = next;
}
next[s] = head[h];
head[h] = s;
return 1;
}

Post Reply

Return to “Volume 108 (10800-10899)”