153 - Permalex

[Jan]

Read the post given by Nikolay Archak in the following forum...

http://online-judge.uva.es/board/viewto ... hlight=153

If you are still facing problems, I will help you.

[IRA]

I don't know why do I got WA!?
Please give me some input and output data to test my program.
Or help me to find the mistake.....Please
Thanks in advance...

Code: Select all

Acc

[ImLazy]

Maybe you didn't deal with the empty lines.
I've just solved this problem. Try this testcase. I generated it randomly.
Input:

Code: Select all

h
ghum
aylnlfdx
ircvs
xg
bw
fnqduxwf
fozvsrtkj
r
pggxrpnr
ystmwcysy
cqpe
ikeffmzni
kkas
w
renz
ycxfxtls
ypsf
dpooef
zbcoeju
pvabo


o
ylfpbn
ljvrvip
amyehwqn
rq
mxujjloov
owuxwh
sncbxcok
fzkvatxd

lyjyhfi
jswnkkufn
xx
rzb
nmgq
oketlyhn
oa
gz

cddiute
ojwa
yz
vsc
psajlf
gubfaao
lzy
n
#

Output:

Code: Select all

         1
         2
      2367
        32
         2
         1
      4212
     15090
         1
      1947
     23846
         6
     40332
         6
         1
        13
     17903
        22
        59
      4333
        91
         1
         1
         1
       659
       833
      2046
         2
     39961
        96
     16640
     14716
         1
      1773
     17573
         1
         4
        15
     26723
         2
         1
         1
        12
        16
         1
         6
       580
      1771
         2
         1

[sds1100]

kind imlazy
사실은 짱꺠 ㅋㅋ

[gradientcurl]

hello have tried permalex. my method is to sort the initial string and permutate till a match is found (using strcmp)
any other shorter way? can't seem to figure out the trick (especially those who manage to have 0 CPU time)

Code: Select all

#include <cstdio>
#include <cstring>
#define MAXLENGTH 32
using namespace std;

bool nextPer(char a[],int length)
{
	register int index,next_min;
	char tmp;
	for(index=length-2;index>=0;index--)
		if(a[index]<a[index+1])
			break;
	if(index<0)
		return false;
	next_min=index+1;
	for(int i=index+1;i<length;i++)
		if(a[i]>a[index]&&a[i]<a[next_min])
			next_min=i;
	tmp = a[index];
	a[index] = a[next_min];
	a[next_min] = tmp;
	
	for(int i=index+1;i<length-1;i++)
	{
		next_min = i;
		for(register int j=i+1;j<length;j++)
			if(a[j]<a[next_min])
				next_min=j;
		tmp = a[i];
		a[i] = a[next_min];
		a[next_min] = tmp;
	}
	return true;
}

int main()
{
	char string[MAXLENGTH],orig[MAXLENGTH],tmp;
	int index,length;

	while(scanf("%s",string),*string!='#')
	{
		length = strlen(string);
		strcpy(orig,string);
		for(int i=0;i<length-1;i++)
		{
			index = i;
			for(int j=i+1;j<length;j++)
				if(string[j]<string[index])
					index = j;
			tmp = string[index];
			string[index] = string[i];
			string[i] = tmp;
		}
		index = 1;
		do
		{
			if(!strcmp(string,orig))
				break;
			index++;
		}while(nextPer(string,length));

		printf("%10d\n",index);
	}	
	return 0;
}

[Jan]

Search your problem first. And dont open a new thread if there is one already.
Read the post given by Nikolay Archak in the following thread...
http://online-judge.uva.es/board/viewto ... hlight=153

[sabir]

i solve this problem by counting.my algo is follow.
get input;copy to another,sort 2nd one,then compare if 1st elements in
2nd str is smaller then 1st elements in 1st str then get rest of data from 2nd str,again sort and compare as before and did it recursevely.
i have passed all sample input in board but wrong answer.
give some critical input.

sorry for my poor english.
thnx.

[nymo]

Thanks Nikolay Archak ! Your explanation helps

[soddy]

I am having a strange kind of problem...n i have no clue

if the input is

Code: Select all

xzbcoeju
aboygp
eylfp
npljvrvi

my output is correct

Code: Select all

     34573
        11
        21
      8782

but if i change the first input like this

Code: Select all

xzbcoejuvp
aboygp
eylfp
npljvrvi

then my output for last value goes wrong

Code: Select all

   3225844
        11
        21
      2930

i dont understand why....i m not using any global variable so different inputs are independent of each other

Code: Select all

Code Removed

[mmonish]

>>soddy
I compile ur code on my MSVC++ compiler & test those 2 sets of input & i get the correct output;
Here u use string & vector type variable. After each test case u should clear each variable.

Hope this helps.

[soddy]

i already tried clearing each variable before a new test case....but still the problem persists.....i dont think clearing variables is the problem since i am initializing new variables for every test case
n i dont know y its working fine on VC++.....i am using cygwin compiler and getting wrong n i hv also tried submitting to online judge and got WA

problem is occuring for very few test cases....i tried a set of 500 test cases and got 3 results wrong but if i try those 3 test cases individually, i am getting correct result.....and i am not using any variable wid previously stored value....dont know y is it happening

[soddy]

I had left the problem and after a few months i tried again and got Accepted in 0.00 time(14th rank) ...things change with time

[Shafaet_du]

Its easier to write the whole thing in java bigint than trying to optimize the intermediate calculation. some io:

Code: Select all

sdfretf
gggfrtttereee
dfffrrrdfdf
zzffffferrrre
aaseajwelrkjlsdj
ewrwerjwelrjwe
#

output:

Code: Select all

     1826
   1801379
      1130
    535920
1468380809
   3265624

[ChrisC]

I am currently working on permalex 153 and my c++ code is being rejected for being "wrong/incorrect"
my current guess is that I am not accounting for some fringe cases
I tried most of the strings given in the forum and got correct results

Code: Select all

using namespace std;
#include <iostream>
#include <stdlib.h>
#include <string>
#include <new>
#include <algorithm>
#include <iomanip>

/*
currently suffering the dreaded wrong output
-I know it works for arrays of length 1-5 (regardless of character values)
-I have looked on the help board and tried other peoples input and I have gotten identical output
-I am assuming either I am messing up the output or messing up some fringe cases
*/

int permutations(string);

//finds the permutations of a sorted string (does not double count)
int permutations(string list)
{
	int length=list.length();
	long int sum =1;
	if (length==0)
		return(0);
	if (length == 1)
		return(sum);

	for(int counter=2; counter<=length;counter++)
	{
		sum=sum*counter;
	}
	
	int count=1;
	for(int j=1;j<length;j++)
	{
		if(list[j-1]==list[j])
		{

			count++;
			sum=sum/count;
		}
		else
			count=1;
		
	}
	return(sum);
	
}

//runs the program
int main()
{
	string tested;
	cin>>tested;
	string test="#";
	while( tested!=test)
	{
		int length=tested.length();
		string sorted =tested;
		sort(sorted.begin(), sorted.end());
		long int sum=1;
		
		
		for(length;length>1;length--)
		{
			int i=0;
			while(sorted[i]!=tested[0])	//test for first letter and find its place
			{
				string temp=sorted;
				temp.erase(i,1);
				sum+=permutations(temp);
				while(sorted[i]==sorted[i+1])
				{
					i++;
				}
				i++;
			}
			
			tested.erase(0,1);
			sorted.erase(i,1);
		}
		std::cout << std::right << std::setw(11) << sum << std::endl;

		cin>>tested;
	}
}

any help would be appreciated

[brianfry713]

The width should be 10 not 11.