482 - Permutation Arrays

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

Moderator: Board moderators

Post Reply
yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Post by yatsen » Fri Jan 04, 2002 6:34 am

I was confused by the sample input & sample output. Is the sample output right? I think it should be -2 32.0 54.7
And I got Runtime Error (SIGSEGV)
What is wrong with my program.

Sample Input
3 1 2
32.0 54.7 -2
Sample Output
54.7
-2
32.0

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jan 06, 2002 9:13 pm

Perhaps your array is not big enough?
I have used an array with 1000000 elements.
The integers on the first line of input are the indizes from the array, which is wanted. In the same order appear the elements of this array. You have to reorder the elements so that their indizes are ordered.

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Location: Dhaka, Bangladesh
Contact:

wrong sample input and output

Post by Shahid » Mon Apr 22, 2002 12:06 pm

hi,
i also guess the sample input and output given in the problem description is wrong and yasten is right. Can anyone plz confirm me about the matter?

thwe right output for the sample input:

3 1 2
32.0 54.7 -2


should be:
-2
32.0
54.7

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Apr 22, 2002 7:26 pm

No, it is ok. The description says:
"Then, we have the relationship between x and x' that x'pi = xi."
That means that at position i there is the index value for x after permutation, for example if you have
2 1
-2 2
then -2 has to be at position 2 in the reordered array and 2 at position 1.
For the sample input there is p1=3, therefore in the permutated array there should be at position 3 the same value as at position 1, and so on.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Fri Apr 26, 2002 4:11 am

The right output for the sample input:

3 1 2
32.0 54.7 -2

should be:
54.7
-2
32.0

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Thu Dec 12, 2002 3:20 pm

can any1 tell me what the problem is in my program.
thanks in adv.

:oops: :oops:

Code: Select all

[cpp]
#include<stdio.h>
#include<stdlib.h>
#define N 10000
main()
{
	int n,z,i,l,k,m,b[N];
	char ch,c[50],d[N][20];
	scanf("%d",&n);
	scanf("%c",&ch);
	for(z=0;z<n;z++)
	{
		k=0;
		while(1)
		{
			m=0;
			while(1)
			{
				scanf("%c",&ch);
				if(ch=='\n' && k) break;
				if(ch==' ') break;
				if(ch!='\n' && ch!=' ')c[m++]=ch;
			}
			c[m]=0;
			b[k++]=atoi(c);
			if(ch=='\n') break;
		}
		for(i=0;i<k;i++)
			scanf("%s",d[i]);
		l=1;
		for(m=0;m<k;m++)
		{
			for(i=0;i<k;i++)
				if(b[i]==l)
				{
					printf("%s\n",d[i]);
					l++;
					break;
				}
		}
		if(z!=(n-1)) printf("\n");
	}
	return 0;
}[/cpp]
[/b]
"Everything should be made simple, but not always simpler"

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

2 anupam

Post by the LA-Z-BOy » Fri Dec 13, 2002 12:07 am

well, well, this problem is very good one (!) for handling the input. anyway, now let's talk 'bout your code here.

while taking the index array in the first part, you're incrementing k (the number of array element) all the time, even if a whitespace occurs!

Code: Select all

b[k++]=atoi(c); 
it should be rather,

Code: Select all

	if (m)
		b[k++]=atoi(c); 
that is you should only increment k when you got a number. Secondly, your check in the inner while loop

Code: Select all

if(ch=='\n' && k) break; 
should be simply

Code: Select all

if(ch=='\n') break; 
i think this causes a time limit exceed.
Again the check in the outer while loop should be,

Code: Select all

if(ch=='\n' && k) break; 
rather than

Code: Select all

if(ch=='\n') break; 
it should help :wink:.
___________
the LA-Z-BOy

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Sat Dec 14, 2002 7:05 am


thanks u very much.
after wasting a lot of time and taking your advices in mind i got it ac.
thanks again.
"Everything should be made simple, but not always simpler"

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Mon Dec 16, 2002 7:38 pm

Before editing: "Can someone give me any tricky tests? My program should handle whitespace without problems at all...but it gets WA :cry: "

Found my error...AC :lol:
Constants for my program
=> Max numbers: 100000
=> Max length per number: 100

Hope this will help others

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Tue Dec 17, 2002 5:58 am

junjieliang wrote: Found my error...AC :lol:
Constants for my program
=> Max numbers: 100000
=> Max length per number: 100

Hope this will help others
my solution that got accepted assumes
=> Max numbers: 32000
=> Max len per number: 55 (54)

but later when i worked with anupam's code i got the upper bound more accurate
=> Max numbers: 2000
=> Max len per number: 15 (14)

Max bound may be lower than this even, I haven't tried .
___________
the LA-Z-BOy

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Wed Dec 18, 2002 10:37 am

i got rte because i didn't consider the break case properly.
please check my preveous program that is corrected by a great helper.
i think you will understand.
thanks.
"Everything should be made simple, but not always simpler"

Hunter
New poster
Posts: 9
Joined: Wed Feb 12, 2003 10:50 am
Location: Alaska

482 Permutation Arrays - WA, RE <SIGSEGV>

Post by Hunter » Wed Feb 12, 2003 10:58 am

Guys, please check my 482 code downhere:

[cpp]#include <stdio.h>
#include <math.h>
#include <string.h>

char str[10000],n[1000][10000],chr;
int len,count,ten,temp,i,j,k,sum[10000],m,cas;

void main ()
{
scanf ("%d",&m); cas=0;
scanf ("%c",&chr); //to handle an <Enter> after inputting the m

while (cas<m)
{
cas++; count=1; k=0; temp=0;
while (scanf ("%c",&chr)==1)
{
if (chr==' ' || chr=='\n')
{
temp++; len=strlen(str); sum[temp]=0;
for (i=len-1;i>=0;i--)
{
switch (str)
{
case '0': {sum[temp]+=0; break;} case '5': {sum[temp]+=5*pow(10,ten); break;}
case '1': {sum[temp]+=1*pow(10,ten); break;} case '6': {sum[temp]+=6*pow(10,ten); break;}
case '2': {sum[temp]+=2*pow(10,ten); break;} case '7': {sum[temp]+=7*pow(10,ten); break;}
case '3': {sum[temp]+=3*pow(10,ten); break;} case '8': {sum[temp]+=8*pow(10,ten); break;}
case '4': {sum[temp]+=4*pow(10,ten); break;} case '9': {sum[temp]+=9*pow(10,ten); break;}
}
ten++;
}
for (i=0;i<len;i++)
{
str='\0';
}
k=0;; count++; ten=0;
}
else {str[k]=chr; k++;}

if (chr=='\n') break;
}

for (i=1;i<=temp;i++)
{
scanf ("%s",n[sum]);
}

for (i=1;i<=temp;i++)
{
printf ("%s\n",n);
}
if (cas<m) printf ("\n");
scanf ("%c",&chr); //to handle the printf ("\n");
}
}[/cpp]
I played with the first and the last "scanf ("%c",&chr);" and I got either RE <SIGSEGV> or WA...
I think I've gone wrong handlin' the input... An <Enter> after the previous input is always
taken by the "scanf ("%c",&chr);" as a '\n' character, so it just passed with the wrong input ('\n')...
Anybody, please tell me how to overcome this. Or maybe found me another mistake(s)???

Thank's!

Hunter
New poster
Posts: 9
Joined: Wed Feb 12, 2003 10:50 am
Location: Alaska

Please reply...

Post by Hunter » Mon Feb 17, 2003 10:45 am

Heey... isn't there any solved this problem yet?
Please gimme answers... Really need it!!!

Thank you.

Hunter
New poster
Posts: 9
Joined: Wed Feb 12, 2003 10:50 am
Location: Alaska

Answer meeee....

Post by Hunter » Sun Mar 16, 2003 7:12 am

It's been a long time...
Why there's still no answer?
I grew the array to a million but nothing happened but another 0.023 SIGSEGV RE!!
Why??!

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Mon Mar 17, 2003 9:19 pm

u'd better try to use struct and store every number as string (important! bcoz
u need to print exactly the same as input) and corresponding indices and sort
the array according to the indices. u can use qsort for sorting.
following code might help:
[c]
typedef struct
{
int index;
char num[20];
} array;

array a[100000];
[/c]

good luck :)
-sohel

Post Reply

Return to “Volume 4 (400-499)”