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
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby »

Thanx mamun and yiuyuho...

I don't understand what mamun mean for the increment... I've just found that it output more blank line at the end... and nothing more than that (I use mamun's sample input).. so it should give me PE...

And btw what's the difference between this and my code:

Code: Select all

per=(int*)malloc(sizeof(int)*MAX);
dataIndex=(char*)malloc(MAX);
fp=(char**)malloc(sizeof(char*)*MAX);
I mean, what's the side effect by using that method? It's just preserved(? or reserved, sorry my English is very bad) the memory in the main program, isn't it?

And about the strtok, what's it mean?

Code: Select all

p = strtok( dataIndex, " \t" );
Is it MUST EXACTLY (space and tab) or (space or tab)?

Thanx for the reply... just confused what's the difference between yiuyuho's code, my code, and my friend's code... :roll:

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho »

Well, for the malloc,

basically when you do static allocation

int main()
{
int v[1000000];
}

that gives you runtime error because you overflowed the default function data memory (I think, I just know in some compilers it throws runtime). I believe it's not a problem if you make it a global variable, which you did. So I just changed it to malloc for my own comfort. If can prolly use static allocation and still get correct.

p = strtok(dataIndex, " \t");

will skip all spaces OR taps.

so strtok("abbccababcabacde","ab"), will give you "cc","c","cde" after each call.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho »

mamun,

I see, the i went out of bounce after getting the last token and corrupted memory.

Thanks for explainning it further.

yiuyuho

Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby »

Thanx for the reply yiuyuho... I'm just a bit curious about the increment you said above... maybe I should recheck or watch it through my compiler's IDE tools (I use BC 3.1).

I'll try another approach... thanx for the code yiuyuho, it will be my last approach so you can remove it now :) thanx once again

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho »

ye, muaum is right, you should take out the i++ at the for loop, because if you're parsing

"3 1 2"

It is actually {'3',' ','1',' ','2','\0'}

so, when you are handling '2', you take the 2, i++, now dataIndex == '\0', so you will leave you innner while loop. But then you do i++ again for post-incrementation of your outter for loop, now you are looking at things that you should not look at (out of bound). If you are lucky, that memory is also 0 and you leave the loop, otherwise you'll just go off your own program, and try to access outside your programs logical address. In short, it's index out of bound.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Roby wrote:I'm just a bit curious about the increment you said above...

I'll try another approach...
You can get (or already got) AC with your same code if you just remove that i++ ie. change

Code: Select all

for ( i = 0, j = 0; dataIndex[i] != '\n' && dataIndex[i] != '\0'; i++ )
to

Code: Select all

for ( i = 0, j = 0; dataIndex[i] != '\n' && dataIndex[i] != '\0'; )
If you don't understand the reason then you might like to know that reading a string in a char array makes the element, at index just after the string's last character, to be NULL not the rest of the array.

Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby »

Thanx mamun n yiuyuho... I've just found that through my compiler IDE tools but yiuyuho already gave the explanations... what a big mistake of mine :oops:

I've posted again like mamun said above and got AC with 0.008 seconds. Thanx mamun for the correction... :D the burden has gone! :D

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

comment on 482

Post by sakhassan »

Hope these things will help u to code simply:
1. u can use scanf for taking input followed by a char variable for the space or new line
2. char output[10001][80] will be enough; :wink:

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

482 - Help me! Plz!! Check my code!

Post by Backbone »

Hi! I was trying to resolve 482 problem, but first OJ give me RE, so I resolve RE but Now OJ give me WA, well, I hope that you can help me!


#include <iostream>
#include <vector.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#define MAX 1000000

void burbuja(vector<float> floating,vector<int> index)
{
int i,j,auxi;
float auxf;
for(i=0; i!=index.size()-1; i++)
{
for(j=i+1; j!=index.size(); j++)
if(index>index[j])
{
auxi=index[j];
index[j]=index;
index=auxi;

auxf=floating[j];
floating[j]=floating;
floating=auxf;
}
}
for(i=0; i!=floating.size(); i++)
cout<<floating<<"\n";
}

using namespace std;
main()
{
char *numeros1,*numeros2,linea1[MAX],linea2[MAX];
int casos,tam=0,i,permuta=0;
vector <int> index;
vector <float> floating;

cin>>casos;
getchar();
while(casos--!=0)
{
gets(linea1);
gets(linea1);
gets(linea2);
numeros1=strtok(linea1," ");
while(numeros1!= NULL)
{
index.push_back(atoi(numeros1));
numeros1=strtok(NULL," ");
}

numeros2=strtok(linea2," ");
while(numeros2!= NULL)
{
floating.push_back(atof(numeros2));
numeros2=strtok(NULL," ");
}
burbuja(floating,index);
index.clear();
floating.clear();
}
}

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

Post by kolpobilashi »

why getting WA???can't find out the mistake

Code: Select all

cut..
thanx in advance...
Last edited by kolpobilashi on Thu Nov 09, 2006 5:17 pm, edited 1 time in total.
Sanjana

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

The numbers in array seems to be under 4000, but the line length is more than 4000.
So gets(s1), gets(s2) is over-flowing.

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

Post by kolpobilashi »

thanx a lot.. :D i increased the input string size upto 20000 and got AC
Sanjana

linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

Post by linux »

I used 15 characters long string and handled 10000 different numbers as strings. So try to handle more t get AC.
Solving for fun..

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

reading input 482

Post by temper_3243 »

http://acm.uva.es/p/v4/482.html

Well this is a general problem i am facing for these kind of inputs and parsing. The above is just an example

for this problem i am reading input using fgets then using strtok to parse the input and then collecting them into an array but somehow my code is going into infinite loop or TLE. Is there an elegant way of solving this problem.

Code: Select all


  back:
    fgets(str, MAX, stdin);
    if (str[0] == '\n' || (str[0] == '\r' && str[1] == '\n')) {
            goto back;
    }

    sv = str;
    y = str;
    while ((z = strtok(y, " ")) != NULL) {
            if((k=strtoul(z,NULL,10))>0)
                    arr[i++] = k - 1;
            y = NULL;
      }



My complete code which is TLE

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 10000
char str[MAX];
int arr[MAX];
char fl[MAX][100];
void swap(int *a, int *b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}
void swapl(char a[][100], char b[][100])
{
	char tmp[100];
	strcpy(tmp, *a);
	strcpy(*a, *b);
	strcpy(*b, tmp);
}

int main()
{
	int i, no, j, k, tmp, len;
	char *y, *z, *sv;
      final:
	fgets(str, MAX, stdin);
	if (str[0] == '\n' || (str[0] == '\r' && str[1] == '\n')) {
		goto final;
	}
	no = strtoul(str, NULL, 10);
	while (no--) {

		memset(str, 0, sizeof(str));
		memset(arr, 0, sizeof(arr));
		i = 0;
	      back:
		fgets(str, MAX, stdin);
		if (str[0] == '\n' || (str[0] == '\r' && str[1] == '\n')) {
			goto back;
		}

		sv = str;
		y = str;
		while ((z = strtok(y, " ")) != NULL) {
			if((k=strtoul(z,NULL,10))>0)
				arr[i++] = k - 1;
			y = NULL;
		}
		j = 0;

	      newback:
		fgets(str, MAX, stdin);
		if (str[0] == '\n' || (str[0] == '\r' && str[1] == '\n')) {
			goto newback;
		}
		y = str;
		while ((z = strtok(y, " ")) != NULL) {
			len = strlen(z);
			if(len > 0){
			if (z[len - 1] == '\n')
				z[len - 1] = '\0';
			}
			strcpy(fl[j++], z);
			y = NULL;
		}
		for (k = 0; k < i; k++) {
			if (arr[k] != k) {
				while (arr[k] != k) {
					tmp = arr[k];
					swap(&arr[k], &arr[tmp]);
					swapl(&fl[k], &fl[tmp]);
				}
			}
		}

		for (k = 0; k < i; k++)
			printf("%s\n", fl[k]);

		if (no != 0)
			printf("\n");
	}
	return 0;
}


PsyCSIEIC
New poster
Posts: 1
Joined: Sun Apr 08, 2007 6:42 am

482 [Presentation Error]

Post by PsyCSIEIC »

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1000
#define LEN 13000

char indexarraytemp[LEN];
int indexarray[MAX];
char arraytemp[LEN];
char* array[MAX];

int main (void){
    int n,i,j,k;
    char* p;


    while (scanf("%d",&n)==1){
        for (i=0;i<n;i++){
            scanf("\n");
            fgets(indexarraytemp,LEN,stdin);

            for (j=0,p=strtok(indexarraytemp," ");p;j++,p=strtok(NULL," ")){
                indexarray[j] = atoi(p)-1;
            }

            fgets(arraytemp,LEN,stdin);

            for (k=0;k<MAX;k++){
                array[k]=NULL;
            }

            for (k=0,p=strtok(arraytemp," ");p;k++,p=strtok(NULL," \n")){
                array[indexarray[k]] = p;
            }

            if (i>0){
                printf("\n");
            }

            for(k=0;k<j;k++){
                if(array[k]==NULL){
                    continue;
                }
                printf("%s\n",array[k]);
            }

        }
    }

    return 0;
}
Why do I get Presentation Error ?
Please tell me ,thanks !

Post Reply

Return to “Volume 4 (400-499)”