## 10098 - Generating Fast

Moderator: Board moderators

qwerfv
New poster
Posts: 3
Joined: Sat Nov 05, 2005 6:44 pm
Location: Taiwan
Thanks to chunyi81 and tywok's advice
I realized what's wrong and........
I get AC now.... Backbone
New poster
Posts: 5
Joined: Sun May 21, 2006 8:40 am

### 10098-Generating_Fast_Permus TLE!!!!!!!!!

Hi!!!, ahm i hope that anybody here can help me! I got TLE for this Prob, and I don't know where is my error!!! Thanks in advance!!!

Code: Select all

``````#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
int n;
string linea;
scanf("%d",&n);
fflush(stdin);
while(n--)
{
getline(cin,linea);
sort(linea.begin(),linea.end()-1);
do
cout<<linea<<endl;
while(next_permutation( linea.begin(),linea.end() ));
cout<<endl;
}
}

``````

algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am
I thought I'm right...
but the judges said WA...
can anybody post some critical i/o set??
thanks before..
and is this i/o set are correct?
INPUT

Code: Select all

``````3
ACba
AcB
bCA
``````
OUTPUT

Code: Select all

``````ACab
ACba
AaCb
AabC
CAab
CAba
CaAb
CabA
CbAa
CbaA
aACb
aAbC
aCAb
aCbA
abAC
abCA
bACa
bAaC
bCAa
bCaA
baAC
baCA

ABc
AcB
BAc
BcA
cAB
cBA

ACb
AbC
CAb
CbA
bAC
bCA

``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Your output is not correct, because for 'ACba' you have a total of 4! = 24 permutations. But your output has 22 of them. And the permutations are

Output:

Code: Select all

``````ACab
ACba
AaCb
AabC
AbCa
AbaC
CAab
CAba
CaAb
CabA
CbAa
CbaA
aACb
aAbC
aCAb
aCbA
abAC
abCA
bACa
bAaC
bCAa
bCaA
baAC
baCA``````
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

rezaeeEE
New poster
Posts: 25
Joined: Fri May 11, 2007 3:45 pm

### why PE

i get PE in this problem.

can any body help me

Code: Select all

``````#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

char st;
string s;

int main()
{
int n;
cin>>n;
string s;

for(int N=0;N<n;N++)
{
cin>>s;

for(int i=0;i<s.length();i++)
st[i]=s[i];

sort(st,st+s.length());

for(int i=0;i<s.length();i++)
printf("%c",st[i]);

printf("\n");

while(next_permutation(st,st+s.length()))
{
for(int i=0;i<s.length();i++)
printf("%c",st[i]);
printf("\n");
}

if(N<n-1)
printf("\n");

}

return 0;
}
``````
thanks

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil
There must be a blank line after the last set too.
Thiago Sonego Goulart - UFMG/Brazil

Zvid
New poster
Posts: 1
Joined: Sat Jul 26, 2008 1:23 pm

### Re: 10098 - Generating Fast, Sorted Permutation

I'm getting TLE in this problem. Can anyone help me?

Code: Select all

``````#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main () {
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
string s;
cin >> s;
sort(s.begin(),s.end());
do {
cout << s << endl;
} while (next_permutation(s.begin(),s.end()));
cout << endl;
}
}``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10098 - Generating Fast, Sorted Permutation

iostreams are quite slow. Use scanf/printf instead cin and cout.

GUC.HassanMohamed
New poster
Posts: 3
Joined: Fri Aug 22, 2008 5:22 pm

### Re: 10098 - Generating Fast, Sorted Permutation

Hello everbody,

I have passed this problem using C++ after getting TLE when trying to take the IO using cin-cout
and I tried to pass it with java (my default language) but I can't and I think the problem is in the I/O
specially for the output as outputting 10! lines (3628800) requires efficient IO.
However, I have seen many people passing it with java so any suggestions for the IO?

GUC.HassanMohamed
New poster
Posts: 3
Joined: Fri Aug 22, 2008 5:22 pm

Hello everybody,

I am having difficulties solving some problems using Java (TLE) but it passes after reimplementing it in C++
like (http://icpcres.ecs.baylor.edu/onlinejud ... oblem=1039) and I am pretty sure that this issue concerns the IO so I wonder if anybody could help me to enhance my IO efficiency.

Any help would be appreciated.

Here is my solution to the problem I mentioned using Java:

Code: Select all

``````import java.io.*;
import java.util.*;

class Main {
public static void main(String[] args)throws IOException {
String in;
for(int i  = 0; i < times;i++){
if(i != 0)
System.out.println("");
char [] ch = in.toCharArray();
Arrays.sort(ch);
System.out.write((new String(ch)+"\n").getBytes());
while(j_next_permutation(ch))
System.out.write((new String(ch)+"\n").getBytes());
}
}
public static boolean j_next_permutation(char [] a) {
int F = 0, L = a.length, I = a.length;
if (F == L || F == --I) return false;
for (;;) {
int Ip = I;
if (a[--I] < a[Ip]) {
int J = L;
for (; !(a[I] < a[--J]););
char tmp = a[I]; a[I] = a[J]; a[J] = tmp;
for (int i = Ip; i < ((L - Ip) % 2 == 0 ? Ip + (L - Ip) / 2 : Ip + (L - Ip) / 2 + 1); ++i) {
char tm = a[i]; a[i] = a[a.length - 1 - i + Ip]; a[a.length - 1 - i + Ip] = tm;
}
return true;
}
if (I == F) {
for (int i = 0; i < ((L - F) % 2 == 0 ? (L - F) / 2 : (L - F) / 2 + 1); ++i) {
int tm = a[i]; a[i] = a[a.length - 1 - i]; a[a.length - 1 - i] = a[i];
}
return false;
}
}
}
}
``````

lnr
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm

To GUC.HassanMohamed

Taking input seems alright to me.
May be taking input in java is slower than C or C++.

abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm

### Re: 10098 - Generating Fast, Sorted Permutation

Code: Select all

``````#include<stdio.h>
char temp;
int arr,len;
void perm(int index)
{
int i;
if(index==len)
{
printf("%s\n",temp);
return;
}
for(i=47;i<124;++i)
if(arr[i])
{
temp[index]=i;
--arr[i];
perm(index+1);
++arr[i];
}
}
int main()
{
int n,i,t=0;
char ch;
for(scanf("%d%*c",&n);n--;)
{
for(i=47;i<124;arr[i]=0,++i);
for(len=0;(ch=getchar())!='\n';++arr[ch],++len);
temp[len]='\0';
if(t)
putchar('\n');
else
t=1;
perm(0);
}
return 0;
}
``````
My program gives correct output for all the test cases on the forum. Still, I am getting a WA. Please help. dodouuu
New poster
Posts: 9
Joined: Tue Mar 24, 2009 7:50 pm

### Re: 10098 - Generating Fast, Sorted Permutation

if(t)
putchar('\n');
else
t=1;

these four lines delete and put printf("\n"); below perm(0); just like

perm(0);
printf("\n");

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 10098 - Generating Fast, Sorted Permutation

Check input and AC output for over 7,500 problems on uDebug!

sajal2k8
New poster
Posts: 16
Joined: Mon Nov 18, 2013 5:15 pm

### 10098 why getting RE??

Here is my code:
#include <iostream>
#include<algorithm>

using namespace std;

int main()
{
int a,b=0,c;
string str,s,q,r;
char ch;
cin>>a;
for(int i=0;i<a;i++)
{
cin>>s;
for(int k=0;k<s.length()-1;k++)
{
for(int l=k+1;l<s.length();l++)
{
if(s[k]>s[l])
{
ch=s[l];
s[l]=s[k];
s[k]=ch;
}
}
}
do
{

str=s;
b++;

}while(std::next_permutation(s.begin(),s.end()));
sort(str,str+b);
for(int j=0;j<b;j++)
{
cout<<str[j]<<endl;
}
if(i!=a-1)
cout<<endl;
b=0;
}
return 0;
}