## 454 - Anagrams

Moderator: Board moderators

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
First of all keep in mind that this is a multiple input problem.

For input check this

http://online-judge.uva.es/board/viewtopic.php?t=1964

Hope this will help

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland
Thanx Junayeed ! AC now !

P.S. The array size must be about 1000, not 500

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
But I got AC with the array size of 301.
Junayeed

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
edit: i switched to C++ and used string to avoid a static array since the input constraints don't say how long each word is to get AC.

[c]
CUT
[/c]

Arm.Turbo
New poster
Posts: 21
Joined: Wed Aug 11, 2004 1:20 pm
Each line in test cases < 64 chars

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
this is seriously wrong:

using an AC program (2004-11-12):

1

aPPLE
PPLEa
LEaPP

gives output:
LEaPP = PPLEa
LEaPP = aPPLE
PPLEa = aPPLE

how lexicographical is "aPPLE" ranked AFTER "LEaPP"?

so now if you rank aPPLE before LEaPP is then incorrect.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

### 454 RTE Please, help me!!!!!!!

Code: Select all

``````#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef struct
{
char original[10000];
char junta[10000];
}
inputs;

bool orden(inputs a, inputs b)
{
if( strcmp(a.junta,b.junta)==-1 )
return true;

return false;
}

void main()
{
int n,i=0,j,k,total;
inputs input[102];

while( gets(input[i].original) )
{
if(input[i].original[0]==' ')
break;

n=strlen(input[i].original);

for(k=0,j=0;j<n;++j)  // borro los espacios
if(input[i].original[j]!=' ')
input[i].junta[k++]=input[i].original[j];

input[i].junta[k]='\n';
++i;
}

total=i;
sort(input,input+total,orden);

for(i=0;i<total;++i)
for(j=i+1;j<total;++j)
cout<<input[i].original<<" = "<<input[j].original<<'\n';
}
``````

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

### Re: 454 RTE Please, help me!!!!!!!

Code: Select all

``````
if(input[i].original[0]==' ')

``````
I didn't check very carefully but I think the above line of code has an error. Are you assuming a blank line starts with space character ? What if it is empty?

Also your code looks like you are solving for a single test case . Read the prob carefully . the first line is the number of test cases and each test case maybe up to 100 lines.

Also maybe the line if( strcmp(a.junta,b.junta)==-1 ) is correct but I think it it is better to use the condition if( strcmp(a.junta,b.junta)<0 ) because I think the standard guarantees only the sign of the return value.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Thx for your reply nnahas. I didn't realize that this is a multiple input problem. However, I have corrected this problem and I got RTE, again.

This is my new code

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef struct
{
char original[10000];
char junta[10000];
}
inputs;

bool orden(inputs a, inputs b)
{
if( strcmp(a.junta,b.junta)<0 )
return true;

return false;
}

void main()
{
int casos,n,i=0,j,k,total;
inputs input[101];

scanf("%i\n",&casos);

do
{

while( gets(input.original) )
{
if( (input.original[0]==' ') || (strcmp(input.original,"")==0) )
break;

n=strlen(input.original);

for(k=0,j=0;j<n;++j) // borro los espacios
if(input.original[j]!=' ')
input.junta[k++]=input.original[j];

input.junta[k]='\n';
++i;
}

total=i;
sort(input,input+total,orden);

for(i=0;i<total;++i)
for(j=i+1;j<total;++j)
cout<<input[i].original<<" = "<<input[j].original<<'\n';

}
while(--casos);
}

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm
Antonio Ocampo wrote:Thx for your reply nnahas. I didn't realize that this is a multiple input problem. However, I have corrected this problem and I got RTE, again.

input.junta[k]='\n';

}

I think the above line has an error, because your string is not null terminated.
You should write input.junta[k]=0; That is probably causing the RTE error.

But you also have other bugs:

if( (input.original[0]==' ') || (strcmp(input.original,"")==0) )

I think this line is still wrong : What if the line is made of tabs ?
What if there is a line containing text that starts with a space ?

Also, as far as I can judge , your code doesn't take this line of the given into account :

"the order of the two phrases within a printed pair must be lexicographic, as well as the first phrases and the second ones in case some first are equal"

Finally , I don't know if this is a trap as I didn't attempt the problem, but they don't specify a maximum line length. perhap you should allocate a very large buffer to use with gets, and allocate the memory in the struct dynamically. I recommend that use the STL string data type, I think it will make your life easier.

subzero
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am
Hi,How are you?

I'm trying to solve this problem......but still getting WA... I got some inputs and the outputs are correct (i think), just see....

input:
3

carthorse
horse
horse cart
i do not know u
ok i now donut
orchestra

aPPLE
PPLEa
LEaPP

erosh
erosh
horse
horse
ac bd
a cbd
q
q
[horse]'
[e]rosh'
iiiiiiiiiiiiij
iiiiiiiiiiiiji
orchestra
pq
qp
carthorse
erosh
horsecart
ok i now donut
oknow uidot n
i do not know u
abdc
kencti kecut
kecut kencit
output:
carthorse = horse cart
carthorse = orchestra
horse cart = orchestra
i do not know u = ok i now donut

LEaPP = PPLEa
LEaPP = aPPLE
PPLEa = aPPLE

[e]rosh' = [horse]'
a cbd = abdc
a cbd = ac bd
abdc = ac bd
carthorse = horsecart
carthorse = orchestra
erosh = erosh
erosh = erosh
erosh = horse
erosh = horse
erosh = erosh
erosh = horse
erosh = horse
erosh = horse
erosh = horse
horse = horse
horsecart = orchestra
i do not know u = ok i now donut
i do not know u = oknow uidot n
iiiiiiiiiiiiij = iiiiiiiiiiiiji
kecut kencit = kencti kecut
ok i now donut = oknow uidot n
pq = qp
q = q

Regards
There is no knowledge that is no power.

Andisheh
New poster
Posts: 5
Joined: Fri Aug 26, 2005 11:29 pm

### 454 RTE Why?

I dont know why I get RTE on this problem,could you help me?
This is my code:

Code: Select all

``````
#include <iostream.h>
//#include <fstream.h>
#include <string.h>
char st[100][1000];

int check(int n,int m)
{
int k,i,j,sw[1000],ssw;
k=0;
for(i=0 ; st[n][i] ; i++)
if(st[n][i]!=' ')
k++;
j=0;
for(i=0 ; st[m][i] ; i++)
if(st[m][i]!=' ')
j++;

if(j!=k)
return 0 ;

for(i=0 ; st[m][i] ; i++)
sw[i]=0;
ssw=1;
for(i=0 ; st[n][i] && ssw; i++)
{
if(st[n][i]!=' ')
{
for(j=0 ; st[m][j] ; j++)
{
ssw=0;
if(st[m][j]==st[n][i] && sw[j]==0)
{
sw[j]=1;
ssw=1;
break;
}
}
}
}

if(i==strlen(st[n]) && ssw)
{
return 1;
}
return 0 ;
}

void main()
{
int i,j,k;

//ifstream f("454.in");
cin.getline(st[0],1000);
while(!st[0][0])
cin.getline(st[0],1000);
i=1;
while(!cin.eof())
{
cin.getline(st[i++],1000);
}
for(j=0;j<i;j++)
{
for(k=j+1 ; k<i ; k++)
if(check(j,k))
cout<<st[j]<<" = "<<st[k]<<endl;

}
//	cin>>i;
}

``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I think you r missing something. Try the following input output set. I think you will find your error.

Input:

Code: Select all

``````2

carthorse
horse
horse cart
i do not know u
ok i now donut
orchestra

aaa
aaa
aaa``````
Output:

Code: Select all

``````carthorse = horse cart
carthorse = orchestra
horse cart = orchestra
i do not know u = ok i now donut

aaa = aaa
aaa = aaa
aaa = aaa``````
Hope you will get Accepted.
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Just check the input output...

Input:

Code: Select all

``````2

carthorse
horse
horse cart
i do not know u
ok i now donut
orchestra

carthorse
horse
horse cart
i do not know u
ok i now donut
orchestra``````
Output:

Code: Select all

``````carthorse = horse cart
carthorse = orchestra
horse cart = orchestra
i do not know u = ok i now donut

carthorse = horse cart
carthorse = orchestra
horse cart = orchestra
i do not know u = ok i now donut``````
Hope it works.
Ami ekhono shopno dekhi...
HomePage

Andisheh
New poster
Posts: 5
Joined: Fri Aug 26, 2005 11:29 pm
thank you!