## 10391 - Compound Words

Moderator: Board moderators

neowarez
New poster
Posts: 14
Joined: Tue May 06, 2003 11:04 pm
Location: Portugal
Contact:

### 10391 - Why WA ???

THis is my code for problem 10391

[pascal]
Program Problema_A(Input, Output);
Var
Conta, I, Temp, Conta2: LongInt;
Words: Array[1..120000] Of String;

Function Procurar(N: String): LongInt;
Var
I, J, A: Integer;
Begin
I:=1;
J:=Conta;
While (I<J) Do
Begin
A:=(I+J) Div 2;
If N<=Words[A] Then
J:=A
Else
I:=A+1;
End;
If N=Words Then
Procurar:=I
Else
Procurar:=0;
End;

Procedure GetData;
Var X, Y: LongInt;
Parte1, Parte2, Parte3 :String;
Begin
Repeat
Inc(Conta);
Until Eof(Input);
For I:=1 To Conta Do
Begin
Temp:=Length(Words);
Conta2:=I;
Repeat
Inc(Conta2);
X:=Pos(Words, Words[Conta2]);
If (X=1) Then
Begin
Parte1:=Words[Conta2];
Parte2:=Words;
Parte3:=Copy(Words[Conta2], Temp+1, Length(Words[Conta2]));
Y:=Procurar(Parte3);
If Not (Y=0) Then
WriteLn(Output, Parte1);
End;
Until Not (X=1);
End;
End;

BEGIN
GetData;
END.

[/pascal]

Why WA???

It result for the example.... and much more.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

There are two errors (although they won't keep you from AC, I think):
- Conta is not initialised;
- Conta2 can get bigger than Conta and point beyond the last element of Words[].

Parta2 is assigned but never used, so get rid of it.

Your program structure is a mess. Variables are 'randomly' declared global or local, without any reason. The name GetData is misleading: besides reading the input, it processes it and produces the output. Either put the whole thing into the main program, or make three procedures: GetData, FindCompoundWords and WriteOutput, or something of the sort. Also don't mix Spanish(?) and English if you want other people to understand your code.

... I should realy contain myself by not being too patronising. Sorry for that, it's stronger than me...

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
HI, I'm also facing the same problem, always WA...
Please check my code and tell me my mistake, or give me some tricky input.

This is my code...

[pascal]--- Removed ---[/pascal]

Thanx for any help!

Regards,
angga888

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

### 10391 .- Why WA?

This is my program , I got Wa, why?

Code: Select all

``````Accepted
``````
Hint

Code: Select all

``````Input
gera
geraaa
gerardo
rdo

Output
gerardo
``````

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
what should be the result for the input?

ab
abab
abab

output:

abab
or,
abab
abab ?
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:

### 10391

Code: Select all

``````#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{

vector<string> v,r;
string s;
while (getline(cin,s))
{
v.push_back(s);
}

for (int i=0;i<v.size();i++)
{     string d;
d=v[i];
for (int t=0;t<v.size();t++)
for (int j=0;j<v.size();j++)
if(d==v[t]+v[j])
r.push_back(d);
}
sort(r.begin(),r.end());
for (int k=0;k<r.size();k++)
cout<<r[k]<<endl;

return 0;
}

``````
i am getting compile error can any one help me plz..?[/b]
win

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

vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:
now i am getting TLE
win

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am
you have used a O(n^3) algorithm, worst case is huge (10^5)^3 = 10^15 .. its not supposed to work... i think an n^2logn is possible if you use binary search, that will be around 10^10, but i am not sure whether that will work.

stl and cin, cout will make your prog slower...
fahim
#include <smile.h>

Akter_Sust
New poster
Posts: 4
Joined: Sat Sep 16, 2006 9:55 am
There is no same input.
for
ab
abab
input, output is
abab

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

### why TLE .......

Can someone tell me.. why i am getting TLE.....

Code: Select all

``````#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(string s1,string s2){
if(s2.size()<s1.size()){
if(s2==s1.substr(0,s2.size()))	return true;
return false;
}
return false;
}
int main(){
long int l,i;
string s;
vector<string> v;
vector<string>::iterator j,p;
vector<int> y;
while(cin>>s){
v.push_back(s);
y.push_back(1);
}
for(i=0;i<v.size()-1;i++){
j=search_n(v.begin()+i+1,v.end(),1,v[i],cmp);
while(j<v.end()){
if(y[j-v.begin()]==1){
p=search_n(v.begin(),v.end(),1,v[j-v.begin()].substr(v[i].size()));
if(p!=v.end()){
cout<<*j<<endl;
y[j-v.begin()]=0;
}
}
j=search_n(j+1,v.end(),1,v[i],cmp);
}
}
return 0;
}``````

alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

### Re: 10391 - Compound Words

I use a string array to store all the string.
Then I take string and concate every string with it and binary search from the array to check whether
compound word is present or not. If present output it.
Why I am getting TLE.
My code is given bellow.

Code: Select all

``````cut after acc
thnks Jan. I have used Trie and got it accepted
``````
Thanks everybody.
Last edited by alamgir kabir on Tue Apr 21, 2009 9:18 pm, edited 1 time in total.

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

### Re: 10391 - Compound Words

Use trie or hashing.
Ami ekhono shopno dekhi...
HomePage

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 10391 - Compound Words

i sloved this problem but i can not remove WA.
i consider all given input & output but my program gave WA
please give me some critical input-output