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

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

Post by deddy one » Sun Feb 16, 2003 12:28 pm

hmmm, I misunderstood the problem statement about the ascending order
thx red scorpion, now I know why I get WA.

only one problem lie now == > how to code it right

I tried to fix my code but still couldn't get the result as same as
your. can you tell me hints to solve this

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Sun Feb 16, 2003 4:17 pm

right you are. :oops:
"Everything should be made simple, but not always simpler"

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Mon Feb 17, 2003 10:19 am

Hi, Try to sort Acending A-a-B-b-C-c-D-d-E-e-...
using array, like this:

[code]
st['A'] = 1
st['a'] = 2
st['B'] = 3
st['b'] = 4
st['C'] = 5
st['c'] = 6

And using this array to sort the string.
Hope this helps. :lol: [/code]

VitorRodrigues
New poster
Posts: 9
Joined: Wed Apr 16, 2003 6:50 pm
Location: Braga, Portugal
Contact:

Post by VitorRodrigues » Wed Apr 16, 2003 8:16 pm

yeah. that's just the solution. i was getting WA because i've not noticed that particular question. now i've got AC.

Thanks everybody

razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Location: SUST,BANGLADESH
Contact:

Post by razibcse » Sat Apr 26, 2003 8:39 pm

I followed the same ascending order as u guys..but getting WA...

I don't find any error in my code..one problem may be in determining
the factorial of the length of the string...
I didn't find statement about what's the maximum size of the string..
please explain it to me...I used double to calculate factorial and converted it to unsigned long...is it right?
however, here's my code:

Code: Select all

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#define MAX 200
#define MAXSZ 60

int comp(const void *a,const void *b);
void permutation(long arr[],long n);
unsigned long fac(long n);

long m,to_div[MAX];
char letter[]={'0','A','a','B','b','C','c','D','d','E','e','F','f','G','g','H',
'h','I','i','J','j','K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R',
'r','S','s','T','t','U','u','V','v','W','w','X','x','Y','y','Z','z'};
void main()
{

long n,a,len,i,j,count[MAX],num[MAX];
char str[MAX];

scanf("%ld",&n);
for(a=0;a<n;a++)
 {
 for(i=0;i<MAXSZ;i++)
   {
   count[i]=0;
   num[i]=0;
   }
 scanf("%s",str);
 len=strlen(str);

 for(i=0;i<len;i++)
   for(j=1;j<MAXSZ;j++)
      if(str[i]==letter[j])
        {
        num[i]=j;
        break;
        }


 for(i=0;i<len;i++)
   count[num[i]]++;

 j=0;
 for(i=1;i<MAXSZ;i++)
   if(count[i]>1)
      to_div[j++]=count[i];
 m=j;

 

 qsort((void *)num, len, sizeof(num[0]), comp);
 permutation(num,len);

 }
}

int comp(const void *a,const void *b)
{
  return (*(long *)a - *(long *)b);
}

void permutation(long arr[],long n)
{
long a,j,k,r,s;
unsigned long x,factorial;
long temp;
factorial=fac(n);

for(a=0;a<n;a++)
   printf("%c",letter[arr[a]]);
   printf("\n");
for(x=1;x<factorial;x++)
 {
 j=n-2;
 while(arr[j]>=arr[j+1])
   j--;

 k=n-1;
 while(arr[j]>=arr[k])
   k--;

 temp=arr[j];
 arr[j]=arr[k];
 arr[k]=temp;

 r=n-1;
 s=j+1;
 while(r>=s)
   {
   temp=arr[r];
   arr[r]=arr[s];
   arr[s]=temp;

   r--;
   s++;
   }

 for(a=0;a<n;a++)
   printf("%c",letter[arr[a]]);
   printf("\n");
 }

}

unsigned long fac(long n)
{
double pro;
long a,b;
unsigned long fact;

pro=1;
for(a=2;a<=n;a++)
  pro*=a;
for(a=0;a<m;a++)
  for(b=to_div[a];b>=2;b--)
   pro/=b;
fact=(unsigned long)pro;
return fact;
}

Wisdom is know what to do next; virtue is doing it.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

195 : how to generate fast, sorted permutations/combinations

Post by Observer » Sat May 10, 2003 5:43 pm

I would like to learn some efficient algorithms/methods to generate permutations and combinations.

When using my own algorithm, I always get TLE for both 195 and 10098...... :(

Please, could anyone share their thoughts or algorithms with me?

It's hard for me to find related online resources, as I know nothing about programming languages other than Pascal.

So please help!!!

Or, you may introduce some good books or resources to me.

Thanks very much!! :D :D :D
Last edited by Observer on Sun May 11, 2003 1:43 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

Next permutation

Post by Maxim » Sat May 10, 2003 9:26 pm

I use algorithm for finding next permutation of some sequence A. Let n denote length of A. Find such A and A[j] elements that satisfy condition A < A[j], where i < j. If there are no such two elements, there is no next permutation. Otherwise, exchange these two elements and reverse order of elements A[i + 1] through A[n], i.e. A[i + 1] <-> A[n], A[i + 2] <-> A[n

steinar
New poster
Posts: 2
Joined: Sat May 31, 2003 6:22 pm
Location: Iceland

Text on permutations

Post by steinar » Sun Jun 01, 2003 10:49 pm

Try http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz. This is a preview on a chapter on permutations in Knuth's Art of Computer Programming. Should be the definite guide :)

steinar
New poster
Posts: 2
Joined: Sat May 31, 2003 6:22 pm
Location: Iceland

Post by steinar » Mon Jun 02, 2003 1:16 am

I just like to point out an alternative to using the array with st[0] = 'A', st[1] = 'a', etc. I would recommend a function, like this one:

bool isLower(char a, char b)
{
if (tolower(a) == tolower(b)) return (a < b);
else return (tolower(a) < tolower(b));
}

It gives the order you're looking for, and is (in my opinion) cleaner programming.

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

Post by deddy one » Thu Jun 05, 2003 7:21 pm

Hi try to search SEPA algoithm on the net resources

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Fri Jun 06, 2003 3:02 am

Thx for all your help!

Now I know how to generate permutations in reasonable time! Thx a lot!

For folks trying to solve Q195, be careful:
the order of the letters is
A -> a -> B -> b -> C -> c -> ... -> Z -> z
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

yes indeed

Post by Nick » Sat Jul 19, 2003 2:08 pm

The judge's input positively more than 30 chars...my mistake was the size of the array was too small.

Thanks guys,
nick

18369AT
New poster
Posts: 1
Joined: Wed Aug 06, 2003 2:07 am

Function for correct character sorting (195 - Anagram)

Post by 18369AT » Wed Aug 06, 2003 2:33 am

Here is quite efficient (I think) and easy-to-use function that helps to sort characters correctly:

[pascal]
function letval(c:char):integer;
var v:integer;
begin
if upcase(c)=c then
v:=(ord(c)-ord('A'))*2
else
v:=(ord(c)-ord('a'))*2+1;
letval:=v;
end;
[/pascal]

It generates character codes this way: A=0, a=1, B=2, etc.. and they are easy to sort...

gcp
New poster
Posts: 6
Joined: Sat Nov 22, 2003 5:38 am
Location: Brazil
Contact:

195 - OLE

Post by gcp » Sun Nov 23, 2003 4:47 am

Why OLE?


My code:

Code: Select all

[cpp]
#include <iostream.h>
#include <string.h>

char A[100], escreve[100], temp;
int n, marca[1000], cont;

void anagrama()
{
    for (int i=0; i<strlen(A); i++)
     { if (marca[i]==0)
        { escreve[cont]=A[i];
	       cont++;
	       marca[i]=1;
	       if (cont==strlen(A))
	        { escreve[cont]='\0';
	          cout << escreve << endl;
	        }
          anagrama();
	  	 	 marca[i]=0;
	  		 cont--;
        }
    }
}

void main()
{
    cin >> n;

    for (int i=1; i<=n; i++)
    {
		cin >> A;
		for (int c=0; c<1000; c++) marca[c]=0;
      cont=0;

      for (int i=0; i<strlen(A)-1; i++)
       for (int j=i+1; j<strlen(A); j++)
        if (A[j]<A[i])
         { temp=A[j]; A[j]=A[i]; A[i]=temp; }
       anagrama();
    }
}
[/cpp]


Thanks.
VIVA LEOPARDO SC!!

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

another 195 WA... (already read all other posts)

Post by stcheung » Wed Dec 03, 2003 2:25 am

Hi guys, so I submitted like 10 times already and still getting WA for 195. I understand the sorting is A < a < B < b < C < c...and my code also takes care of blank lines. So here is my code, if anyone can kindly test it against some tricky inputs that would be great. Thanks in advance!


[cpp]/* 195 */
#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <algorithm>

string next(string, int);
bool lessthan(char, char);
string mysort(string s, int len);

int main()
{
int numcases;
cin >> numcases;
string s;
getline(cin, s);
for(int i=0; i<numcases; i++)
{
getline(cin, s);
int len = s.length();
s = mysort(s, len);

while(true)
{
cout << s << "\n";
s = next(s,len);
if(s == "")
break;
}
}
return 0;
}

string next(string in, int len)
{
string result="";
char m,n;
int pos1=-1, pos2=-1;
for(int j=len-1; j>=1; j--)
{
n = in[j];
for(int i=j-1; i>=0; i--)
{
m = in;
if(m < n && i > pos1)
{
pos1 = i;
pos2 = j;
}
}
}
if(pos1 != -1)
{
char temp = in[pos1];
in[pos1] = in[pos2];
in[pos2] = temp;
result+=in.substr(0, pos1+1);

char temp2[len - pos1 - 1];
for(int k=pos1+1; k<len; k++)
temp2[k-pos1-1] = in[k];

sort(temp2, temp2+len-pos1-1);
for(int k=0; k<len-pos1-1; k++)
result+=temp2[k];
}
return result;
}

bool lessthan(char a, char b)
{
char a2 = tolower(a);
char b2 = tolower(b);
if(a2 < b2)
return true;
else if(b2 < a2)
return false;
else return (a < b);
}

string mysort(string s, int len)
{
char arr[len];
for(int k=0; k<len; k++)
arr[k] = s[k];
for(int m=0; m<len-1; m++)
{
for(int n=m+1; n<len; n++)
{
if(lessthan(arr[n], arr[m]))
{
char tmp = arr[m];
arr[m] = arr[n];
arr[n] = tmp;
}
}
}
string result="";
for(int z=0; z<len; z++)
result+=arr[z];
return result;
}[/cpp]

Post Reply

Return to “Volume 1 (100-199)”