153 - Permalex

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

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

153

Post by broderic » Sun Jun 23, 2002 12:01 am

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
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada

Post by broderic » Sun Jun 23, 2002 11:33 pm

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

Post by Experimenter » Fri Jul 04, 2003 11:43 am

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

Post by Experimenter » Thu Jul 10, 2003 9:33 am

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

Post by junbin » Thu Dec 11, 2003 7:03 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:

Post by Nikolay Archak » Thu Dec 11, 2003 8:37 am

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

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
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands

Post by El-idioto » Thu Mar 11, 2004 3:06 am

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

Post by Antonio Ocampo » Thu Jan 06, 2005 10:49 pm

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 :wink:

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon May 16, 2005 2:28 pm

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

Post by Antonio Ocampo » Tue May 17, 2005 12:10 am

Hi Sedefcho

I had forgotten this post :-? It was long ago.

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

Thx anyway :lol:

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

WA.

Post by KvaLe » Tue Jun 14, 2005 9:05 pm

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

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

Nobody can help me?

Post by KvaLe » Tue Jun 28, 2005 9:35 am

Nobody can help me :( ?
Giorgi Lekveishvili

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

Compile Error

Post by mbd01 » Wed Sep 28, 2005 10:17 pm

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
New poster
Posts: 22
Joined: Wed Aug 17, 2005 3:04 pm

..

Post by Fadia Ismael » Thu Sep 29, 2005 12:21 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...

Post by jan_holmes » Sat Dec 17, 2005 1:10 pm

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

Post Reply

Return to “Volume 1 (100-199)”