## 153 - Permalex

Moderator: Board moderators

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am

### 153

can anybody think of a reason why this doesnt' work?

Code: Select all

``````#include <stdio.h>

unsigned ways;
int chars;

unsigned pos (char *str) {
unsigned i,ret,numforeach;

if (strlen(str)==2) {
chars[str-'a']++;
chars[str-'a']++;
if (str!=str) ways = 2; else ways = 1;
return (str>str) ? 1 : 0;
}

ret = pos(str + 1);
chars[str-'a']++;
ways = (ways*strlen(str))/chars[str-'a'];
numforeach = ways/strlen(str);
for (i=0; i+'a'!=str; i++) {
ret += chars[i]*numforeach;
}
return ret;
}

int main () {
char cur;

while (scanf("%s\n", cur)==1) {
ways=0;
memset(chars, 0, sizeof(chars));
if (cur=='#') break;
if (strlen(cur)>1) printf("%10u\n", pos(cur)+1);
else printf("%10u\n", 1);
}
return 0;
}``````

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
nevermind, i figured it out.
it was overflowing, so i switched to long doubles.
works now. Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

### 153 - Permalex

hi, everybody.
I was just wondering if anybody could give me a hint how to solve the problem. I tried to solve it using brute force, i.e. to search through all permutations in ascending order and count the number of permutations before the one given in input. Though the code below works for the examples, I really doubt it will work on online judge because of time limit. Can anybody give me a hint how to solve it in any other way?
[cpp]
#include <fstream>
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>

using namespace std;

// global variables
unsigned long counter = 0;
bool fl = false;
string StrToFind;

// function defenitions
ostream & operator << (ofstream &str,string &s);
istream & operator >> (ifstream &str,string &s);
void GivePermNum(string a,string b);
int main();

int main()
{
string s;

sort(s.begin(),s.end());

while(true)
{
cin>>StrToFind;
if((string)"#" == StrToFind) break;
else
{
s = StrToFind;
sort(s.begin(),s.end());

fl = true;
counter = 0;
GivePermNum(s,(string)"");
cout.setf(ios::right);
cout<<setw(10)<<(counter + 1)<<endl;
}

}

return 0;
}

void GivePermNum(string a,string b)
{
char last = 0;
int i = 0;
string s;

if(0 == a.length())
{
if(StrToFind == b)
fl = false;
else
counter++;

return;
}

else
{
int iLen = a.length();
for(i = 0; i < iLen && fl; i++)
{
if (last != a)
{
last = a;
s = a;
s.erase(s.begin() + i);
GivePermNum(s,b + last);
}

}
}
}

ostream & operator << (ofstream &str,string &s)
{
int i, iLen = s.length();
for(i = 0; i < iLen; str<<s[i++]);
return str;
}

istream & operator >> (ifstream &str,string &s)
{
char c; bool fl = true;
while(fl)
{
cin>>c;
if(c=='\n') fl = false;
else s+=c;
}

return str;
}
[/cpp]
it would be great if you replied this post. really.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
hi, everybody!
anyway, I've solved the problem. thanks to minskcity who gave me the idea.
it would be great if you replied this post. really.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
can you please post the hints he gave you?

Nikolay Archak
New poster
Posts: 6
Joined: Tue Dec 02, 2003 6:43 am
Contact:
Hi!
Your brute force algorithms obviously cant pass the online judge because in the worst case it has to make as much as 2^30 procedure calls . Note, that permutation number is just number of permutations which are lesser than given one (+1). So you just have to count all permutations which are lesser than given.
Permutation a is lesser than permutation b if one of the following is true:

1. a < b
or
2. a==b && a[1..N] < b[1..N]

Number of permutations of first type is easy to calculate
you should just iterate over all characters which are smaller than s and check the number of ways to order the remaining string characters.

For example, for string "cdaab"

number of permutations of first type is
number of permutations starting from a ( remaining characters are 1 'a', 1'b', 1'c', 1'd'
it gives us 4! perms)
+ number of permutations starting from b (remaining characters are 2 'a', 1'c', 1'd'
it gives us 4!/2! perms NOTE THE DUPLICATE 'a' character)

So we have 4! + (1/2)*4! = 36 permutations of first type

To get the number of permutations of second type we can just remove the first character and call ourself recursively (i.e. for string "daab")

So, full calculations for string "cdaab" are as follows:

-- doit called for "cdaab"

+ 1. Number of perms in the following set { d, b, c, a } = 24
+ 2. Number of perms in the following set { d, c, a, a } = 12

-- doit called for "daab"

+ 3. Number of perms in the following set { a, b, d } = 6
+ 4. Number of perms in the following set { a, a, d } = 3

-- doit called for "aab"
-- doit called for "ab"
-- doit called for "b" and returns 0

So, counting together we get 24+12+6+3 (+1 because answers are numbered
starting from 1) == 46

Final hint:

Number of perms in set with x1 character 'a', x2 characters 'b' ...
xi characters ? is equal to the n! / (x1! * x2! * ... * xi!) where n=x1+...+xi.

Be careful calculating this number because you can easily get overflow even using
long long types.
Note, that 30!/(15!*15!) fits to long long BUT 30! DONT
so calculating n! first and then dividing it by each of the smaller factorials will give you wrong result.

There are a lot of ways to optimize this algorithm, but even this solution is fast enough to pass online judge within several milliseconds.

El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands
Ok, I figured out how to fix it. You have to use 'ull' after a 64-bit number.
Example: 2^50 = 1125899906842624ull

*** ORIGINAL POST ***
Can someone who uses the same compiler as the online judge please compile my code? I use g++ v3.3.1 to compile my apps (using Cygwin).
Unfortunately, g++ gives me the following errors:

Code: Select all

``````\$ g++ -o 153 f:/projects/contests/153_permalex/153_permalex.cpp
f:/projects/contests/153_permalex/153_permalex.cpp:41: error: integer constant
is too large for "long" type
f:/projects/contests/153_permalex/153_permalex.cpp:41: error: integer constant
is too large for "long" type
f:/projects/contests/153_permalex/153_permalex.cpp:42: error: integer constant
is too large for "long" type
f:/projects/contests/153_permalex/153_permalex.cpp:42: error: integer constant
is too large for "long" type
f:/projects/contests/153_permalex/153_permalex.cpp:42: error: integer constant
is too large for "long" type
f:/projects/contests/153_permalex/153_permalex.cpp:42: error: integer constant
is too large for "long" type
f:/projects/contests/153_permalex/153_permalex.cpp:42: error: integer constant
is too large for "long" type
f:/projects/contests/153_permalex/153_permalex.cpp:43: error: integer constant
is too large for "long" type``````
It's obvious that the compiler has trouble with the numbers which are bigger than 2^32-1... even though I set the type to be uint64 (which translates to unsigned long long int on a non-Windows machine).

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Hi for all, I got TLE . Could you tell me how to improve my code??

Code: Select all

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

void main()
{
register int i,n;

{
break;

printf("%10d\n",i);
}
}
``````
Thanks in advance Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Antonio, you're using a brute-force method.
That's why you get TLE.

Try using a better algorithm. For example the
algorithm suggested by Nikolay Archak ( see his
post from Dec 11,2003 ) is a much better
algorithm.

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

I had forgotten this post It was long ago.

By the way, I got AC with Nikolay Archak's algorithm.

Thx anyway KvaLe
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm

### WA.

Hi all.
I wrote this program, but it gets WA.
Now I looked Nikolay Archak's algorithm and its and my algorithms is same, but my code gets WA.
PLZ help here is my code:

Code: Select all

``````Program permalex;

Var I, J, K, N, Sol : LongInt;
Ch : Char;
S, SS : String;
A : Array ['a' .. 'z'] Of LongInt;

Function GCD (A, B : LongInt) : LongInt;
Begin
If A = 0 Then GCD := B
Else GCD := GCD (B Mod A, A);
End;

Function Variantebi (N : LongInt) : LongInt;
Var I, J, K, C, DD, Sol : LongInt;
B : Array [1 .. 30] Of LongInt;
D : Array ['a' .. 'z'] Of LongInt;
Begin
FillChar (D, SizeOf (D), 0);
For I := 1 To N Do B [I] := I;
For I := 1 To N Do
If D [S [I]] = 0 Then Begin
For J := 2 To A [S [I]] Do Begin
C := J;
For K := 0 To N Do Begin
If C = 1 Then Break;
DD := GCD (C, B [K]);
C := C Div DD; B [K] := B [K] Div DD;
End;
End;
D [S [I]] := 1;
End;
Sol := 1;
For I := 1 To N Do Sol := Sol*B [I];
Variantebi := Sol;
End;

Begin
While True Do Begin
If S  = '#' Then Break;
SS := S; N := Length (S);
Sol := 0;
FillChar (A, SizeOf (A), 0);
For I := 2 To N Do
For J := 1 To I-1 Do
If S [I] < S [J] Then Begin Ch := S [I]; S [I] := S [J]; S [J] := Ch; End;
For I := 1 To N Do Inc (A [S [I]]);
For K := 1 To N Do Begin
For I := 1 To N Do Begin
If S [I] = SS [K] Then Break;
If ((I = 1) Or (S [I-1] <> S [I])) And (A [S [I]] > 0) Then Begin
Dec (A [S [I]]);
Inc (Sol, Variantebi (N-K));
Inc (A [S [I]]);
End;
End;
Dec (A [SS [K]]);
End;
Inc (Sol);
Str (Sol, S);
N := 10-Length (S);
For I := 1 To N Do Write (' ');
WriteLn (Sol);
End;
End.``````
Giorgi Lekveishvili

KvaLe
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm

### Nobody can help me?

Nobody can help me ?
Giorgi Lekveishvili

mbd01
New poster
Posts: 2
Joined: Mon Sep 26, 2005 8:40 pm

### Compile Error

Hi I have solved prob#153 in my computer. Language- Turbo C 3.0
I also solved Prob#100
solution of Prob#153 is:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

double fact(int x)
{
double p=1;
for(;x>=1;x--)
{
p=p*x;
}
return p;
}

int sortfunction(const void *a, const void *b)
{
return strcmp((char *)a,(char *)b);
}
void trancate(char *s, char *t)
{
int m,i=0,k;
m=strlen(s);
while(s==t && i<=m)
{
i++;
}
for(k=i;k<=m;k++)
{
s[k-i]=s[k];
t[k-i]=t[k];
}
s[k]='\0';
t[k]='\0';
return;
}
double numofperm(char s[],char t)
{
int l,k,sameterm;
double f;
char str;
strcpy(str,s);
l=strlen(s)-1;
f=fact(l);
for(k=0;k<=l+1;k++)
{
if (str[k]==t) {str[k]='1'; break;}
}
k=0;
sameterm=0;
while(str[k]!='\0')
{
if(str[k]==str[k+1])
{
sameterm++;
k++;
while(str[k]==str[k-1] && str[k]!='\0') { sameterm++;k++; }
f=f/fact(sameterm);
sameterm=1;
}
else k++;
}
return f;
}
int getpos(char s[],char t)
{
int k=0;
while(s[k]!=t)
{
k++;
}
return k+1;
}
void modify(char *s, char *t)
{
int k=0;
while(s[k]!=t) k++;
while(s[k+1]!='\0')
{
s[k]=s[k+1];
k++;
}
s[k]='\0';
k=1;
while(t[k]!='\0') { t[k-1]=t[k];k++; }
t[k-1]='\0';
}
void main()
{
char strin,firststr;
double f;
long int pos;
int l;
do{
pos=0;
scanf("%s",strin);
if(strin=='#') break;
strcpy(firststr,strin);
qsort((void *)firststr,strlen(firststr),1,sortfunction);

while(strcmp(firststr,strin))
{
trancate(firststr,strin);

f=numofperm(firststr,strin);
l=getpos(firststr,strin)-1;
pos=pos+ f*l;
modify(firststr,strin);
}
pos=pos+1;
//printf("%s %s",firststr,strin);
printf("%10ld",pos);
}while(1);
return;

}

But after sending it, I got "Compile Error". Can anyone help me?

New poster
Posts: 22
Joined: Wed Aug 17, 2005 3:04 pm

### ..

Hello.. I think you have to check the warning message your program gives.. I compiled it and I have this warning message:
warning C4244: '=' : conversion from 'double' to 'long', possible loss of data
this is related to the following line:

Code: Select all

``pos=pos+ f*l;``
So, you have to make an explicit casting, or to change one of the two variables' type...

Hope this helps...
It's lack of faith that makes people afraid of meeting challanges, and I believe in myself.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

### 153... Need Help...

I'm trying to solve this problem by using next_permutation,but I'm always get Time Limit Exceeded Is there any method to make it run faster ??? Thx... 