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

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

10391 - Why WA ???

Post by neowarez » Fri May 09, 2003 5:01 pm

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);
ReadLn(Input, Words[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.

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

Post by little joey » Thu May 15, 2003 11:58 am

Read the previous thread on this problem. Your program doesn't deal correctly with Caesums input.

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

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Wed Jun 18, 2003 2:22 pm

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 :D

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

10391 .- Why WA?

Post by lord_burgos » Wed Dec 22, 2004 9:39 pm

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
Location: buet, dhaka, bangladesh

Post by ayon » Tue Jul 04, 2006 4:43 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

Post by vinit_iiita » Thu Jul 20, 2006 9:52 pm


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
Location: Bangladesh
Contact:

Post by mamun » Thu Jul 20, 2006 10:14 pm

algorithm header file not included.

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

Post by vinit_iiita » Thu Jul 20, 2006 11:34 pm

now i am getting TLE :cry:
win

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Thu Jul 27, 2006 7:25 pm

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

Post by Akter_Sust » Sat Jul 07, 2007 10:04 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 .......

Post by Ron » Sun Aug 05, 2007 8:07 am

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

Post by alamgir kabir » Sat Jul 12, 2008 8:38 pm

I am getting TLE. please help me.
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
Location: Dhaka, Bangladesh
Contact:

Re: 10391 - Compound Words

Post by Jan » Sun Jul 13, 2008 5:39 pm

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

Post by MRH » Thu Sep 03, 2009 5:55 am

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

thanks in advance

parusa
New poster
Posts: 1
Joined: Sun Jan 15, 2012 3:56 pm

10391 - Compound Words

Post by parusa » Thu Jan 19, 2012 12:41 pm

How many letters may stay in a word at most???????
It is not mentioned in this problem.

Post Reply

Return to “Volume 103 (10300-10399)”