454 - Anagrams

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

Moderator: Board moderators

Post Reply
yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

454 - Anagrams

Post by yatsen » Fri Jan 18, 2002 9:16 am

I think 454 is not difficult. But I got WA.
Can anyone tell me what's wrong with my code.Thanks.

Code: Select all

#include <stdio.h>
#include <string.h>
#define Maxarray 1000
#define STRLENGTH 100
void delspace(char *s)
{
	char t[STRLENGTH];
	int i,j=0,k=strlen(s);
	for (i=0;i<k;i++)
		if (s[i]!=' ') t[j++]=s[i];
	t[j]='?';
	strcpy(s,t);
	return;
}

void sortstr(char *s)
{
	int k=strlen(s),i,j;
	char temp;
	for (i=0;i<k-1;i++)
		for (j=i+1;j<k;j++)
			if (s[i]>s[j]) { temp=s[i]; s[i]=s[j]; s[j]=temp; }
	return;
}

int getsLine(char *line)
{
  int i=0;
  char ch;
  if (1 != scanf("%c", &ch)) return 0;
  while (ch != 'n')
  {
    line[i++] = ch;
    if (1 != scanf("%c", &ch)) break;
  }
  line[i] = '?';
  return i;
}

int checkblankline(char *s)
{
	int k=strlen(s),i;
	for (i=0;i<k;i++) if (s[i]!=' ') return 1;
	return 0;
}

main()
{
char ostr[Maxarray][STRLENGTH],nstr[Maxarray][STRLENGTH],dummy[STRLENGTH];
int i,j,k,c,testcase;

scanf("%dn",&testcase);
for (c=0;c<testcase;c++)
{
	i=0;
	while (getsLine(ostr[i])>0)
	{
		if (checkblankline(ostr[i])==0) break;
		strcpy(nstr[i],ostr[i]);
		delspace(nstr[i]);
		sortstr(nstr[i]);
		i++;
	}
	for (j=0;j<i;j++)
		for (k=j+1;k<i;k++)
			if ( strcmp(nstr[j],nstr[k])==0 )
					printf("%s = %sn",ostr[j],ostr[k]);
	printf("n");
} /* while */
return 0;
}
Last edited by brianfry713 on Mon Nov 24, 2014 11:16 pm, edited 1 time in total.
Reason: Added code blocks

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Jan 18, 2002 1:28 pm

You dont check, if you get the same words twice. In this case you should only take the first one. Then your output is not in lexicographic order. You can make another array to store the output and sort it then. But as far as I see the other part of your program is ok (perhaps the strings are longer, I had STRLEN 500).

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

454 - Anagrams

Post by angga888 » Sun Dec 22, 2002 4:57 pm

I have tried so many input in my 454 source program in Pascal and I think the output is correct. This is my input :


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


What should the output be ?

And please give me another unique input to test my program.

Thanx for helping me.
Angga :D

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

454 RE & CE

Post by zsepi » Sun Jan 05, 2003 10:31 am

alright, I don't think I will post my code here, but I am getting real $%^&* with the compiler difference between the judge's and mine... honestly, why does the same C code compiles and runs on my machine fine and gets RE (invalid memory reference) from the judge? Is there any way I could set up my compiler and machine so that things would run *exactly* as they would on the judge's machine? it would save me a lot of redundant submission, my reputation (statistics) would be better, not even mentioning how much less frustrated I would feel - you know it's different when the program crushes on your computer and when it does that on the judge's :wink:
PS: before anyone would suggest: no, I don't get RE because I don't have long enough arrays - in this particular problem, I have 10000 for phrases and I am prepared for 10000 phrases at the moment (though I know there can be only 100, but I just wanted to be sure I eliminated this problem)
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Sun Jan 05, 2003 2:23 pm

Well, sometimes declaring large arrays are not enough. Check your code, is there any part that goes out of the range? Maybe you're accessing array[-1]? I usually check my code by shrinking the array to exactly the size of the input, so I can tell where I'm going out of range...

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

Post by zsepi » Sun Jan 05, 2003 2:29 pm

junjieliang wrote:Well, sometimes declaring large arrays are not enough. Check your code, is there any part that goes out of the range?
you are completely right, I wouldn't wanna argue with that - the only reason I mentioned that I maximized the arrays was to avoid people telling me to make sure that the array is big enough... the whole issue is that I am not getting WA, but RE, which is really upsetting after X time spent debugging that prog and finally got it working - only to figure out that it only works on MY machine, not the judge's. so my post was more to figure out if it is possible to create an environment which is like the judge.... but thanx for your reply anyways :)
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Anagram

Post by saiqbal » Fri Mar 07, 2003 5:04 pm

my AC program's output for ur input:
[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
this is a multiple input problem. check if ur program dealt with that.

good luck
-sohel

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu May 29, 2003 11:35 am

After rejudgement I got WA ...
Could anyone tell me why ?
I use following algorithm (for each case):
1. read input phrases,craete pair (phrase,sorted phrase) and sort them by letters (bca is sorted to abc)
2. sort them by letter's frequency in sorted phrase
3. create all possible pairs on anagrams
4. sort this pairs lexicographically
5. print every pair exactly once to output ...
I try to avoid some sortings in many ways, but still got WA....

Could anyone help me? I can send my code to this person ... :)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Thu May 29, 2003 3:49 pm

now that you mention it, after I check my stat,
my Acc 454 is missing. :o

here's my algo/pseudocode

1.scan multiple input
2.for each case do the following
3.scan for the input and put them in an array until the input
is an empty string
4.sort the input in the array once (lexicographicly)
5.check anagrams in the array for every words in the input
(using ON^2 solution),if it's anagram then output them


if someone know what's wrong pls post in
this thread. :wink:

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Thu May 29, 2003 8:45 pm

For now I still got AC.
my AC algo are :
1. scan multiple input.
2. scan input. if strlen input == 0 go to step 3.
3. sort all inputs.
4. sort every input ( c ba to abc ), and store in other array.
5. search anagram with data that produce by step 4 :

Code: Select all

for(i=0;i<n-1;i++)
    for(j=i+1;j<n;j++)
          if(strcmp(data[i],data[j])==0) 
            print data from step 3 [i] = data from step 3 [j];

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri May 30, 2003 7:44 am

Hisoka, can you send me your EXE for this problem? I compare our outputs and try to resolve my problem :)

Best regards
DM

PS. Send it, If you could, to Dominik.Michniewski@interia.pl
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri May 30, 2003 2:18 pm

I think that problem is in sentence:

Code: Select all

Each anagram pair should be printed exactly once
I understood it, that for input like

Code: Select all

aaa
aaa
aaa
output should be empty or contains only one line aaa = aaa.
But I see that I should print

Code: Select all

aaa = aaa
aaa = aaa
aaa = aaa
So I think, that description isn't really clear ...

Best regards
DM

PS. I try to get Acc, when judge server will be up (I think it'll be soon) :)
PS. And special thanks to Hisoka for EXE :):)
Last edited by Dominik Michniewski on Fri May 30, 2003 3:18 pm, edited 1 time in total.
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Fri May 30, 2003 3:04 pm

I send my .exe to you.

But my program cannot handle input like this. And I still got AC, I try to submit again my code to judge, tomorrow, and give me AC too.

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Sat May 31, 2003 4:40 pm

hi Hisoka

may I know how big array size for character that
you use in your code ???


thx.

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Sat May 31, 2003 5:26 pm

hello deddy...

For input I use input[200][100], and for other array I use [100]

Post Reply

Return to “Volume 4 (400-499)”