153 - Permalex

[broderic]

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

Code: Select all

#include <stdio.h>

unsigned ways;
int chars[26];

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

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

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

int main () {
  char cur[31];

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

[broderic]

nevermind, i figured it out.
it was overflowing, so i switched to long doubles.
works now.

[Experimenter]

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]

[Experimenter]

hi, everybody!
anyway, I've solved the problem. thanks to minskcity who gave me the idea.

[junbin]

can you please post the hints he gave you?

[Nikolay Archak]

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[0] < b[0]
or
2. a[0]==b[0] && 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[0] 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]

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]

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;
 register char guardada[31],cad[31]; 

 while( gets(cad) ) 
 { 
   if( strcmp(cad,"#")==0 ) 
     break; 

   n=strlen(cad); 
   sscanf(cad,"%s",guardada);
   sort(cad,cad+n);

   for(i=1; strcmp(cad,guardada)!=0;++i) 
    next_permutation(cad,cad+n); 

   printf("%10d\n",i);
 } 
} 

Thanks in advance

[Sedefcho]

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]

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]

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
    ReadLn (S);
    If S [1] = '#' 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.

[KvaLe]

Nobody can help me ?

[mbd01]

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[31];
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[0]) 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[31],firststr[31];
double f;
long int pos;
int l;
do{
pos=0;
scanf("%s",strin);
if(strin[0]=='#') break;
strcpy(firststr,strin);
qsort((void *)firststr,strlen(firststr),1,sortfunction);

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

f=numofperm(firststr,strin[0]);
l=getpos(firststr,strin[0])-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?

[Fadia Ismael]

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...

[jan_holmes]

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...