## 941 - Permutations

Moderator: Board moderators

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Contact:

### 941 - Permutations

Why TLE??? My method is anough to avoid TLE. I think there is some buck in my code.please help......

Code: Select all

#include<stdio.h>
#include<string.h>
typedef long long dt;

dt count,n;
char si[50];

dt gcd(dt h1,dt h2)
{
dt h3;
while(h2!=0)
{
h3=h1%h2;
h1=h2;
h2=h3;
}

return h1;

}

void make(dt h1,char te[50])
{
dt k,i,j,p[50],ar[50],y,yy,z,mul,y1,fa;

k=strlen(te);
for(i=0;i<26;i++)
p[i]=0;
for(i=0;i<k;i++)
p[te[i]-'a']++;

for(i=0;i<k;i++)
if(i==k-1||te[i+1]!=te[i])
{
for(j=2;j<=k-1;j++)
ar[j]=j;
for(j=0;j<26;j++)
if(p[j]>1)
{y=p[j];
if(j==(te[i]-'a'))
y--;
fa=y;
for(y1=2;y1<=fa;y1++)
{  y=y1;
for(z=2;z<=k-1;z++)
if(ar[z]>1)
{
yy=gcd(ar[z],y);
ar[z]=ar[z]/yy;
y=y/yy;
if(y==1)
break;
}
}
}

mul=1;
for(j=2;j<=k-1;j++)
mul=mul*ar[j];

if(mul+count>=n)
{
break;
}

count=count+mul;

}

if(mul+count>=n)
{
si[h1]=te[i];

z=0;
for(j=0;j<k;j++)
if(j!=i)
{te[z]=te[j];z++;}

if(z!=0)
{
te[z]='\0';
make(h1+1,te);
}
else
{
si[h1+1]='\0';
}

}
}
int main()
{

dt cas,cas1,i,j,t;
char c,sa[50];
scanf("%lld",&cas);

for(cas1=1;cas1<=cas;cas1++)
{

scanf("%s %lld",sa,&n);

n++;

t=strlen(sa);
for(i=0;i<t-1;i++)
for(j=0;j<t-1-i;j++)
if(sa[j]>sa[j+1])
{
c=sa[j];
sa[j]=sa[j+1];
sa[j+1]=c;
}

count=0;
make(0,sa);

printf("%s\n",si);

}
return 0;
}
SHAKIL

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I think this problem doesnt have any input set. Try submitting an empty code.

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india
@jan
empty code is accepted while my valid solution timeout.

kalgorithmist
New poster
Posts: 1
Joined: Sun Jul 10, 2011 12:55 pm

### Re: 941 - Permutations

Hi, why this gives Time Limit Exceeded?

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

void mySwap (char &a, char &b)
{
char tmp = a;
a = b;
b = tmp;

}

class Permuter
{

public:
Permuter ()
{
this->word_ = "";

}

void setWord (const std::string &word)
{
this->word_ = word;
}

std::vector <std::string> getPermutations ()
{
std::sort (this->permutations.begin (), this->permutations.end ());
return this->permutations;
}

void permute ()
{

this->sortWord ();

this->internalPermute (0);

}

private:
std::string word_;

void sortWord ()
{

std::sort (this->word_.begin (), this->word_.end ());

}

std::vector <std::string> permutations;

void internalPermute (int start)
{
if (start == (int) this->word_.length () - 1)
{
this->permutations.push_back (this->word_);
return ;
}

else
{
for (int i = start; i < (int) this->word_.length (); i++)
{
mySwap (this->word_.at (start), this->word_.at (i));

internalPermute (start + 1);

mySwap (this->word_.at (start), this->word_.at (i));
}
}
}

};

int main ()
{
int numberOfTimes = 0;

std::cin >> numberOfTimes;

for (int i = 0; i < numberOfTimes; i++)
{
std::string word = "";

std::cin >> word;

int position = 0;

std::cin >> position;

Permuter permuter;

permuter.setWord (word);

permuter.permute ();

std::cout << permuter.getPermutations ().at (position) << "\n";
}

std::cout << std::flush;

return 0;
}

maurizzzio
New poster
Posts: 5
Joined: Wed Jul 20, 2011 9:02 pm

### Re: 941 - Permutations

Your code is O(n!), of course it'll give TLE, just try this input

Code: Select all

1
abcdefghijklmnopqrst
2432902008176639999
Output:

Code: Select all

tsrqponmlkjihgfedcba
My code gives the answer in no time so try another algo

GarrettO
New poster
Posts: 1
Joined: Fri Nov 22, 2013 11:46 pm

### Re: 941 - Permutations

I'm getting a TLE with this code, but I don't know how to make it run any faster.

Any feedback regarding the JAVA implementation would be appreciated.

Thank you!

Code: Select all

// UVA #941 Permutations

import java.util.*;
import java.math.*;

public class Main
{
char[] strIn;
StringBuilder sorted;
BigInteger permNum;
int length;
BigInteger[] factorial = new BigInteger[20];
BigInteger[] quotRem;
int index;
int target;

public static void main(String[] args)
{
Main mySolution = new Main();
mySolution.begin();
}

void begin()
{
calculateFactorials();
Scanner conIn = new Scanner(System.in);
int numCases = conIn.nextInt();

for(int i = 0; i < numCases; i++)
{
strIn = conIn.next().toCharArray();
index = length = strIn.length;
Arrays.sort(strIn);
sorted = new StringBuilder(new String(strIn));
permNum = new BigInteger(conIn.next());
if(permNum.equals(BigInteger.ZERO)) System.out.println(sorted);
else
{
index = length - 1;
quotRem = permNum.divideAndRemainder(factorial[index--]);
target = new Integer(quotRem[0].toString());
System.out.print(sorted.charAt(target));
sorted.deleteCharAt(target);

while(index > 0)
{
quotRem = quotRem[1].divideAndRemainder(factorial[index--]);
target = new Integer(quotRem[0].toString());
System.out.print(sorted.charAt(target));
sorted.deleteCharAt(target);
}
System.out.println(sorted);
}
}
}

void calculateFactorials()
{
factorial[1] = new BigInteger("1");
factorial[2] = new BigInteger("2");
for(int i = 3; i < 20; i++)
{
factorial[i] =
factorial[i - 1].multiply(new BigInteger(new Integer(i).toString()));
}
}
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 941 - Permutations

Check input and AC output for thousands of problems on uDebug!

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

### Getting WA

i think my code gives right output for all input except this input:
input:
1
abcdefghijklmnopqrst
88888888888888888
AC output:
aorshnpkdlmiqtgfejbc
MY output:
aorshnpkdlmiqtgfebcj
can anyone help me to fix the bug of my code???

Code: Select all

#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;
string s;
long long int n;
void solution() {
vector<long long int>factorial;
long long int len=s.size();
//cout<<len<<endl;
long long int f=1;
factorial.push_back(0);
for(int i=1;i<=len;i++) {
f*=i;
factorial.push_back(f);
}
//cout<<factorial[20]<<endl;
long long int cur_len=len;
long long int p,index;
string temp=s;
//cout<<temp<<endl;
while(cur_len>1) {

p=factorial[cur_len]/cur_len;
index=floor(n/p);
if(index>=cur_len) {
index=index%cur_len;
//cout<<index<<endl;
}
cout<<temp[index];
//cout<<"temp "<<temp<<endl;
//cout<<temp[index];
temp.erase(index,1);
cur_len--;
}
cout<<temp[0];
}

int main()
{
long long int test;
cin>>test;
while(test--) {
s.clear();
cin>>s;
sort(s.begin(),s.end());
cin>>n;
solution();
cout<<endl;
}
return 0;
}