10098 - Generating Fast

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

qwerfv
New poster
Posts: 3
Joined: Sat Nov 05, 2005 6:44 pm
Location: Taiwan

Post by qwerfv » Sun Nov 06, 2005 12:27 pm

Thanks to chunyi81 and tywok's advice
I realized what's wrong and........
I get AC now.... :P

Backbone
New poster
Posts: 5
Joined: Sun May 21, 2006 8:40 am

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

Post by Backbone » Wed Sep 27, 2006 8:46 am

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


User avatar
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

Post by algoJo » Fri Feb 23, 2007 6:50 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Feb 23, 2007 7:22 pm

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

Post by rezaeeEE » Sun Jun 17, 2007 1:04 am

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[10];
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

Post by tgoulart » Sun Jun 17, 2007 3:57 am

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

Post by Zvid » Sat Jul 26, 2008 1:37 pm

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

Post by mf » Sat Jul 26, 2008 10:40 pm

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

Post by GUC.HassanMohamed » Wed Sep 10, 2008 2:27 am

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?

Thanks in advance.

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

Efficient Java IO..Please Help

Post by GUC.HassanMohamed » Wed Sep 10, 2008 2:38 am

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 {
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		int times = new Integer(br.readLine());
		String in;
		for(int i  = 0; i < times;i++){
			in = br.readLine();
			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
Location: Dhaka,Bangladesh

Re: Efficient Java IO..Please Help

Post by lnr » Wed Oct 08, 2008 6:43 am

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

Post by abhiramn » Sun May 17, 2009 9:48 am

Code: Select all

#include<stdio.h>
char temp[12];
int arr[130],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. :cry:

dodouuu
New poster
Posts: 9
Joined: Tue Mar 24, 2009 7:50 pm

Re: 10098 - Generating Fast, Sorted Permutation

Post by dodouuu » Sat Jul 04, 2009 8:17 pm

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

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


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

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

Re: 10098 - Generating Fast, Sorted Permutation

Post by uDebug » Tue Jun 03, 2014 12:14 pm

Replying to follow the thread.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

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

10098 why getting RE??

Post by sajal2k8 » Thu Jul 24, 2014 9:14 am

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

using namespace std;

int main()
{
int a,b=0,c;
string str[10000],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;
}
I am getting runtime error. Please help. Thank You in advance.

Post Reply

Return to “Volume 100 (10000-10099)”