941 - Permutations

[shakil]

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;
}

[Jan]

I think this problem doesnt have any input set. Try submitting an empty code.

[mukeshtiwari]

@jan
empty code is accepted while my valid solution timeout.

[kalgorithmist]

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]

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]

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]

Try using BufferedReader and BufferedWriter

[LazyTym]

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;
}

thanks in advanced