195 - Anagram

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

Moderator: Board moderators

deadangelx
New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

Re: 195: anagram, wrong answer

Post by deadangelx » Sun Apr 19, 2009 3:16 am

some info about Problem 195
1.there is no blank between characters in the word.
2.the length about 100 characters is enough
3.alphabet order is A -> a -> B -> b -> C -> c ..... -> Y -> y -> Z -> z
4.Problem 146 is similar with Problem 195, but test cases in Problem 146 are weak, and some wrong algorithms(I have tested) also got Accepted.
So make sure your algorithm is correct.

Hope it helps.

a13032002
New poster
Posts: 5
Joined: Wed Aug 27, 2008 7:05 pm

Re: 195: anagram, wrong answer

Post by a13032002 » Wed Mar 31, 2010 4:27 pm

I think my algorithm is right,but I got WA.
Could someone tell me why?please

Code: Select all

AC
    
Last edited by a13032002 on Fri Apr 02, 2010 5:00 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 195: anagram, wrong answer

Post by helloneo » Thu Apr 01, 2010 10:16 pm

I think your compare function is not correct..

m=i>='a'&&i<='a'?i-'a':i-'A';

Shouldn't this be..

m= i>='a' && i <= 'z' ? i - 'a' : i - 'A'

a13032002
New poster
Posts: 5
Joined: Wed Aug 27, 2008 7:05 pm

Re: 195: anagram, wrong answer

Post by a13032002 » Fri Apr 02, 2010 5:00 pm

helloneo wrote:I think your compare function is not correct..

m=i>='a'&&i<='a'?i-'a':i-'A';

Shouldn't this be..

m= i>='a' && i <= 'z' ? i - 'a' : i - 'A'
I got AC.Thank you! :D
That was a stupid mistake

Mehadi
New poster
Posts: 18
Joined: Sun Jan 24, 2010 11:17 am

Re: 195: anagram, wrong answer

Post by Mehadi » Mon Apr 26, 2010 10:19 pm

What's problem in my Code .PLZ help.

Code: Select all

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

int main () 
{

	long i,j,k,l,n;
	char myints[1000],s[1001];
	scanf("%ld",&n);
	while(n--)
	{
		long a[130]={0};
	
		scanf("%s",&myints);
		
		k=strlen(myints);
 		for(i=0;i<k;i++)
		{
			a[myints[i]]++;
		}
		l=0;
		for(j=65;j<=90;j++)
		{
			if(a[j])
			{
				for(i=0;i<a[j];i++)
					s[l++]=j;
			}
			if(a[j+32])
			{
				for(i=0;i<a[j+32];i++)
					s[l++]=j+32;
			}
		}
		s[l]='\0';
		do 
		{
			printf("%s\n",s);
		} while ( next_permutation (s,s+l) );
	}

  return 0;
}

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 195: anagram, wrong answer

Post by Shafaet_du » Fri Oct 01, 2010 6:37 pm

next permutation function wont be able to solve it. STL is too slow. again suppose the string is aaaaaaaaaaaaaaa. thats 15 characters,but ans is only one line, "aaaaaaaaaaaaaaa". If you use STL and hashtable to eliminate the duplicates it will stil genarate 15! outputs and you will get TLE. only clever backtracking can solve the problem.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 195: anagram, wrong answer

Post by helloneo » Fri Oct 01, 2010 7:39 pm

Mehadi wrote:What's problem in my Code .PLZ help
Try this input..

Code: Select all

1
Ba

My output is..

Code: Select all

aB
Ba

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 195: anagram, wrong answer

Post by plamplam » Sat Sep 10, 2011 6:22 pm

by Shafaet_du » Fri Oct 01, 2010 10:37 pm

next permutation function wont be able to solve it. STL is too slow. again suppose the string is aaaaaaaaaaaaaaa. thats 15 characters,but ans is only one line, "aaaaaaaaaaaaaaa". If you use STL and hashtable to eliminate the duplicates it will stil genarate 15! outputs and you will get TLE. only clever backtracking can solve the problem.
I totally disagree with you. I just solved this using STL's next_permutation(0.044s). It works fine if the string is aaaaaaaaaaaaaaaaaaaaaaaaaaaaa or aaaaaaaaaaaaaabaaaaaaaaaaaaaa etc. :roll:
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

195 - WA Anagram I am stumped !!

Post by mathgirl » Tue Apr 24, 2012 6:24 pm

My code works fine on my system. I have tested it with several inputs..
But i got WA .
Please help !!!

Code: Select all

Code deleted after AC 
Last edited by mathgirl on Wed Apr 25, 2012 4:15 pm, edited 1 time in total.

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

Re: 195 - WA Anagram I am stumped !!

Post by brianfry713 » Wed Apr 25, 2012 12:00 am

On my system this code doesn't work. You shouldn't try to modify the data in a string.
http://www.cplusplus.com/reference/string/string/data/

Instead of pushing word onto your list you can create a new string from letters.
Check input and AC output for thousands of problems on uDebug!

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

Re: 195 - WA Anagram I am stumped !!

Post by mathgirl » Wed Apr 25, 2012 4:15 pm

I got the problem.. it was in the sorting order. I wrote a custom compare function for sort and got accepted. :)
Modifying the original string should work fine on any system. next_permutation is an STL algorithm, so it cant be wrong.

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

Re: 195 - WA Anagram I am stumped !!

Post by brianfry713 » Thu Apr 26, 2012 1:54 am

The problem wasn't in next_permutation, the sort function didn't work because you had:
char *letters=(char*)word.data();
sort(letters,letters+len);

Here letters is a pointer to an internal location which should not be modified directly in the program. Its contents are guaranteed to remain unchanged only until the next call to a non-constant member function of the string object.

Instead you could have done:
char letters[len+1];
strcpy(letters,word.c_str());
sort(letters,letters+len);

And instead of pushing back word onto your list, do:
string s(letters);
output.push_back(s);
Check input and AC output for thousands of problems on uDebug!

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

Re: 195 - WA Anagram I am stumped !!

Post by mathgirl » Thu Apr 26, 2012 8:31 pm

Thank brian ! I'll make sure to follow this next time. :)

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

195 - Anagram

Post by @ce » Wed Jun 06, 2012 6:04 pm

Whats wrong with my code...plzz help

Code: Select all

Code removed after AC
Last edited by @ce on Mon Jun 25, 2012 10:01 am, edited 2 times in total.
-@ce

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

Re: 195 - Anagram

Post by brianfry713 » Wed Jun 06, 2012 10:31 pm

Input:

Code: Select all

1
aAbB
AC output:

Code: Select all

AaBb
AabB
ABab
ABba
AbaB
AbBa
aABb
aAbB
aBAb
aBbA
abAB
abBA
BAab
BAba
BaAb
BabA
BbAa
BbaA
bAaB
bABa
baAB
baBA
bBAa
bBaA
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 1 (100-199)”