482 - Permutation Arrays

[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...

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

mamun,

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

Thanks for explainning it further.

yiuyuho

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

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]

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]

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

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

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

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

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

Code: Select all

cut..

thanx in advance...

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

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

[linux]

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

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

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 !