10391 - Compound Words

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10391 - Compound Words

Post by brianfry713 » Wed Jan 25, 2012 2:18 am

Less than 30.
Check input and AC output for thousands of problems on uDebug!

bunnyxl
New poster
Posts: 4
Joined: Fri Jun 29, 2012 6:32 am

10391 - Compound Words

Post by bunnyxl » Fri Jun 29, 2012 6:48 am

Hi. I got WA for this question. But I think I have removed the case that one word can be fromed in different ways. Can anyone tell some special cases for this problem ? Thanks

And below is my code

Code: Select all

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

char *r;
char *f;
int MAX;

class Lnode{
public:
	Lnode(){comp=0;isword=false; for(int i=0; i<26; i++)l[i]=0;}
	void add();
	void travle(int idx);
	void find(int idx);
	bool match(char *s);
	void disout(int idx);
private:
	bool isword;
	int comp;
	Lnode *l[26];
	static int len;
};

Lnode *root;

void Lnode::disout(int idx){
	if(comp==1){
		r[idx]=0;	
		printf("%s\n", r);
	}
	for(int i=0; i<26; i++){
		if(l[i]){
			r[idx] = 'a'+i;
			l[i]->disout(idx+1);
		}
	}
}

void Lnode:: add(){
	char c;
	int idx;
	if((c=getchar())=='\n'){
		isword=true;
		if(len> MAX)
			MAX=len;
		len=0;
		return;
	}
	len++;
	idx = c-'a';
	if(!l[idx])
		l[idx] = new Lnode;
	l[idx]-> add();
}

void Lnode:: find(int idx){
	if(isword){
		f[idx]=0;
		if(idx>0 && strcmp(r,f) &&root->match(f)){
			comp++;
		}
	}
	for(int i=0; i<26; i++){
		if(l[i]){
			f[idx]= i+'a';
			l[i]->find(idx+1);
		}
	}
}

bool Lnode:: match(char *s){
	if(!(*s)){
		return isword;
	}
	int idx= *s-'a';
	if(!l[idx])
		return false;
	return l[idx]-> match(s+1);
}

void Lnode:: travle(int idx){
	if(isword){
		r[idx]=0;
		find(0);		
	}
	for(int i=0; i<26; i++){
		if(l[i]){
			r[idx]= 'a'+i;	
			l[i]->travle(idx+1);
		}
	}
}

int Lnode:: len=0;

int main(){
	root = new Lnode;
	MAX=0;
	while(cin.peek()!=EOF){
		root-> add();
	}
	r = new char[MAX+1];
	f = new char[MAX+1];
	root->travle(0);
	root->disout(0);
	return 0;
}

bunnyxl
New poster
Posts: 4
Joined: Fri Jun 29, 2012 6:32 am

Re: 10391 - Compound Words

Post by bunnyxl » Fri Jun 29, 2012 12:42 pm

Well I've just AC this problem and I think the problem statement has some problem so I write down in case you meet the same problem in the further.

"A two-word compound word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary"

The word exactly has no use here. The output will still have cases that
1. one word is the concatenation of the same word
2. one word is the concatenation of different combinations of words
And also, it seems that two-letter word in the output will be rejected... I don't why
Finally, please fix if there is any multiple lines in your output

See if this can help

usamamaqbool
New poster
Posts: 4
Joined: Mon Dec 31, 2012 12:19 pm

10391 compound words : wrong answer

Post by usamamaqbool » Mon Dec 31, 2012 12:23 pm

//#include <fstream>
#include <iostream>
#include<string>
using namespace std;


class hash
{
private:
string *p;
int size;
int *flag;
int key;
string var;
public:
hash()
{
size=120,000;
key=0;
var='\0';
}
hash(int size,string name,int key)
{
this->size=size;
this->key=key;
this->var=var;
}
void setName(string var)
{
this->var=var;
}
string getVar()
{
return var;
}
void setKey(int key)
{
this->key=key;
}
int getKey()
{
return key;
}
void setSize(int size)
{
this->size=size;
}
int getSize()
{
return size;
}
void createArray()
{

if(size>0)
{
p=new string[size];
this->size=size;
flag=new int[size];
this->size=size;
for(int i=0;i<size;i++)
p='\0';
for(int i=0;i<size;i++)
flag=0;
}
}
void hashFunc(string var)
{
int temp=0,sum=0;
for(unsigned int i=0; i<(var.length());i++)
{
temp=var-'0';
sum=sum+temp;
}
key=sum%size;
setKey(key);

}
void insert(string var)
{

hashFunc(var);
int a=getKey();
if(flag[a]==0)
{
p[a]=var;
flag[a]=1;
}

else
{
while(flag[a]!=0 && flag[a]<size && a+1<size )
{
a=a+1;
a=a%size;
}
if(flag[a]==0)
{
p[a]=var;
flag[a]=1;
}
else
{
cout<<"Memory Full";
}
}


}
void search()
{
for(int i=0;i<size;i++)
{
if(flag==1)
{

for(int j=0;j<size;j++)
{
if(flag[j]==1&& i!=j)
{
string c=p+p[j];
for(int z=0;z<size;z++)
{
if(c==p[z])
{
cout<<p[z]<<endl;
}


}

}
}
}

}
}


};


int main()
{
hash h;
int size=0;
string var;
h.createArray();
//ifstream infile;
//infile.open ("example.dat",ios::app);
//while(!infile.eof()) // To get you all the lines.
//{
// infile>>var;
// h.insert(var);

//}
while((getline(cin,var)) !=NULL)
{
h.insert(var);

}
h.search();
//infile.close();
return 0;
}





why is this code not accepted

usamamaqbool
New poster
Posts: 4
Joined: Mon Dec 31, 2012 12:19 pm

Re: 10391 compound words : wrong answer

Post by usamamaqbool » Mon Dec 31, 2012 12:24 pm

Everytime I read through getline or cin or a file it gives WRONG ANSWER

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10391 compound words : wrong answer

Post by brianfry713 » Tue Jan 01, 2013 3:16 am

Read from stdin, write to stdout, not from/to a file.
http://uva.onlinejudge.org/index.php?op ... &Itemid=30

Try solving it using a set instead of a hash.

Maybe change the line

Code: Select all

size=120,000;
to:

Code: Select all

size=120000;
Check input and AC output for thousands of problems on uDebug!

usamamaqbool
New poster
Posts: 4
Joined: Mon Dec 31, 2012 12:19 pm

Re: 10391 compound words : wrong answer

Post by usamamaqbool » Tue Jan 08, 2013 5:40 am

#include <iostream>
#include<stdio.h>
#include<string>


using namespace std;

int main()
{
string *p;
string var;
int *flag;
int a=0;
int size=120000;
p=new string[size];
flag=new int[size];
for(int i=0;i<size;i++)
{
p="NULL";
flag=0;
}

while((getline(cin,var)) !=NULL)
{
int temp=0,sum=0;
for(unsigned int i=0; i<(var.length());i++)
{
temp=var-'0';
sum=sum+temp;
}
a=sum%size;
if(flag[a]==0)
{
p[a]=var;
flag[a]=1;
}

else
{
while(flag[a]!=0 && flag[a]<size && a+1<size )
{
a=a*2;
a=a%size;
}
if(flag[a]==0)
{
p[a]=var;
flag[a]=1;
}
}
}
for(int i=0;i<a;i++)
{
if(flag==1)
{
for(int j=0;j<a;j++)
{
if(flag[j]==1 && i!=j)
{
string c=p+p[j];
int z=0;
while(z<a)
{
if(c==p[z] && flag[z]==1)
{
flag[z]=0;
cout<<p[z]<<"\n";
}
z++;
}


}


}
}
}
return 0;
}
brianfry713 wrote:Read from stdin, write to stdout, not from/to a file.
http://uva.onlinejudge.org/index.php?op ... &Itemid=30

Try solving it using a set instead of a hash.

Maybe change the line

Code: Select all

size=120,000;
to:

Code: Select all

size=120000;

usamamaqbool
New poster
Posts: 4
Joined: Mon Dec 31, 2012 12:19 pm

Re: 10391 compound words : wrong answer

Post by usamamaqbool » Tue Jan 08, 2013 5:41 am

Thanks brianfry713 ...:)

Kindly Check Its now giving TLA????

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10391 compound words : wrong answer

Post by brianfry713 » Tue Jan 08, 2013 9:20 pm

It doesn't match the sample I/O.

Use the code blocks when posting code so the indentation is preserved.
Check input and AC output for thousands of problems on uDebug!

Muftee_Ruet
New poster
Posts: 10
Joined: Fri Sep 16, 2011 6:36 am

Re: 10391 - Compound Words

Post by Muftee_Ruet » Tue May 06, 2014 6:46 pm

what is the output of the following input?

Code: Select all

a
ali
alien
en
lien

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10391 - Compound Words

Post by brianfry713 » Wed May 07, 2014 9:23 pm

Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 103 (10300-10399)”