Page 1 of 3

153

Posted: Sun Jun 23, 2002 12:01 am
by 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;
}

Posted: Sun Jun 23, 2002 11:33 pm
by broderic
nevermind, i figured it out.
it was overflowing, so i switched to long doubles.
works now. :)

153 - Permalex

Posted: Fri Jul 04, 2003 11:43 am
by 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]

Posted: Thu Jul 10, 2003 9:33 am
by Experimenter
hi, everybody!
anyway, I've solved the problem. thanks to minskcity who gave me the idea.

Posted: Thu Dec 11, 2003 7:03 am
by junbin
can you please post the hints he gave you?

Posted: Thu Dec 11, 2003 8:37 am
by 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 .
: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.

Posted: Thu Mar 11, 2004 3:06 am
by 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).

Posted: Thu Jan 06, 2005 10:49 pm
by 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 :wink:

Posted: Mon May 16, 2005 2:28 pm
by 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.

Posted: Tue May 17, 2005 12:10 am
by 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 :lol:

WA.

Posted: Tue Jun 14, 2005 9:05 pm
by 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.

Nobody can help me?

Posted: Tue Jun 28, 2005 9:35 am
by KvaLe
Nobody can help me :( ?

Compile Error

Posted: Wed Sep 28, 2005 10:17 pm
by 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?

..

Posted: Thu Sep 29, 2005 12:21 pm
by 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...

153... Need Help...

Posted: Sat Dec 17, 2005 1:10 pm
by jan_holmes
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... :)