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

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 482 Permutation Arrays

Post by lbv » Mon Mar 11, 2013 10:57 am

fade36776 wrote:i m still getting WA. please help.
Since this problem doesn't have an explicit specification for how large n could be, and the size in characters of each line, it's risky to make assumptions and declare fixed-size arrays to hold the data. However, take the time to read the previous comments from this forum thread. The post made by bill8124 on Jul 27, 2012, for example, has some useful information.

Alternatively, you could write a program that doesn't make any assumptions in the size of the input (using C++ structs like strings, vectors, etc.)

Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

Re: 482 Permutation Arrays

Post by Munchor » Wed Mar 20, 2013 10:16 pm

brianfry713 wrote:It looks like you misunderstood the problem. Don't sort an array of doubles, just keep them as strings. Permute the strings according to the index array.
brianfry713, take a look at this example case:

Code: Select all

1

3 1 2
32.0 54.7 -2
I sort the values and I get "-2", "32.0", "54.7". Then the "3 1 2" means - "first print the third (54.7), then the first (-2) then the second (32.0). I definitely have to sort them, it's not just printing out the third, the first and the second from the order of input.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 482 Permutation Arrays

Post by brianfry713 » Thu Mar 21, 2013 11:36 pm

That's not what the problem is asking. Don't sort the doubles, keep them as strings
"32.0" should be the third element in the new array.
"54.7" should be the first element in the new array.
"-2" should be the second element in the new array.
Check input and AC output for thousands of problems on uDebug!

Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

Re: 482 Permutation Arrays

Post by Munchor » Sat Mar 30, 2013 2:19 am

brianfry713 wrote:That's not what the problem is asking. Don't sort the doubles, keep them as strings
"32.0" should be the third element in the new array.
"54.7" should be the first element in the new array.
"-2" should be the second element in the new array.
Thank you, I completely misunderstood the problem!

hello
New poster
Posts: 25
Joined: Sun Mar 10, 2013 7:29 pm

Re: 482 Permutation Arrays

Post by hello » Mon Oct 28, 2013 2:06 pm

Got RE... :(

Code: Select all

    //bismillahhirrahmanirrahim
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#define zero(arr) memset(arr,0,sizeof(arr));
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n,k) for(int i=m;i<n;i=i+k)

#define VI vector<int>
#define VVI vector< VI >
#define VIit VI::iterator

#define pb(a) push_back(a)
#define SI(a) scanf("%d",&a)
#define SU(a) scanf("%u",&a)
#define SHD(a) scanf("%hd",&a)
#define SHU(a) scanf("%hu",&a)
#define SLLD(a) scanf("%lld",&a)
#define SLLU(a) scanf("%llu",&a)
#define SF(a) scanf("%f",&a)
#define SLF(a) scanf("%lf",&a)
#define SC(a) scanf("%c",&a)
#define SS(a) scanf("%s",a)
#define swp(type, a, b) {type x=a; a=b; b=x;}
#define read(in) freopen("in.txt","r",stdin);
#define write(out) freopen("out.txt","w",stdout);
using namespace std;

string s1;
int arr[100000];
int main()
{
    //read(in);
    int cases,flag=0;
    SI(cases);
    getchar();
    getchar();
    while(cases--){

    getline(cin,s1);
    s1+="-1";
    istringstream iss(s1);
    int index=1;
    while(1){
        iss >> arr[index++];
        if(arr[index-1]==-1)break;
    }
    string s;
    vector<string> V(index-1);
    FOR(i,1,index-1,1){
        cin>>s;
        V[arr[i]]=s;
    }
    getchar();
    if(flag)puts("");
    flag=1;
    FOR(i,1,index-1,1)cout<<V[i]<<endl;
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 482 Permutation Arrays

Post by brianfry713 » Mon Oct 28, 2013 8:08 pm

Don't use a single getchar() and count on it to be a newline, that won't work if there is trailing whitespace on a line.
Check input and AC output for thousands of problems on uDebug!

Kenpachi24
New poster
Posts: 20
Joined: Wed Oct 30, 2013 7:06 pm

Re: 482 Permutation Arrays

Post by Kenpachi24 » Wed Dec 11, 2013 12:56 am

I have WA. I think that's by output of the blank lines; accept suggestions (I know should use any data structure, but I think that does not affect WA)

Code: Select all

remove by AC 
Last edited by Kenpachi24 on Sat Dec 14, 2013 4:04 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 482 Permutation Arrays

Post by brianfry713 » Wed Dec 11, 2013 11:02 pm

The outputs of two consecutive cases will be separated by a blank line. Don't print an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

Kenpachi24
New poster
Posts: 20
Joined: Wed Oct 30, 2013 7:06 pm

Re: 482 Permutation Arrays

Post by Kenpachi24 » Thu Dec 12, 2013 7:36 am

I delete the line "System.out.println()" and even I Have WA

What do you recommend?

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

Re: 482 Permutation Arrays

Post by uDebug » Thu Dec 12, 2013 8:13 am

brianfry713 shared this information with me and I found it incredibly useful to solve this problem.
My AC code on 482 assumes a line is less than 100,000 characters and there are up to 10,000 numbers on a line.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

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

Re: 482 Permutation Arrays

Post by uDebug » Thu Dec 12, 2013 8:15 am

Kenpachi24 wrote:I delete the line "System.out.println()" and even I Have WA

What do you recommend?
I just now ran your program and this is the output I see

Code: Select all

54.7
-2.0
32.0
Looking at your code and at this line

Code: Select all

double arreglo[]=new double[1000000];
This is probably what's causing things to trip up.

Look at the sample input / output more carefully. There's both

Code: Select all

32.0

and

Code: Select all

-2
Your code prints the extra ".0"after "-2".

Does this suggest taking another approach to the problem?
Last edited by uDebug on Thu Dec 12, 2013 9:19 am, edited 1 time in total.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

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

Re: 482 Permutation Arrays

Post by uDebug » Thu Dec 12, 2013 8:40 am

Also, for anyone else wondering about or having formatting issues. My AC code for the following input

Code: Select all

3

3 1 2
32.0 54.7 -2

3 2 1
2 5 6.0

1
7.0
gives the following output

Code: Select all

54.7
-2
32.0

6.0
5
2

7.0

There is a blank line after every set of output. However, as mentioned several times before, there is no blank line after the last set of output.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Kenpachi24
New poster
Posts: 20
Joined: Wed Oct 30, 2013 7:06 pm

Re: 482 Permutation Arrays

Post by Kenpachi24 » Sat Dec 14, 2013 4:02 am

:D AC

thank you very much ( brianfry713 - v1n1t) by the observations and clarifications; definitely I should use String; and the problem of the blank line I was misinterpreting

again, thank you very much

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

Re: 482 Permutation Arrays

Post by uDebug » Sat Dec 14, 2013 7:15 am

Kenpachi24 wrote::D AC
Well done! I'm glad you figured it out!
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 482 Permutation Arrays

Post by jddantes » Sat Mar 08, 2014 9:07 am

What's wrong with mine?

Code: Select all


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main()
{
    int cases;
    char x;
    scanf("%d%c",&cases,&x);
    int e;
    for(e=0; e<cases; e++)
    {
        char buff[50];
        fgets(buff, 50, stdin);

        char * word_list[100500];
        memset(word_list,0, sizeof(word_list));

        //printf("Input indices:\n");
        char scan_index[100500];
        fgets(scan_index, 100500, stdin);

        char scan_values[100500];
        fgets(scan_values,100500, stdin);
        scan_values[strlen(scan_values) - 1] = 0;

        int index;

        FILE *stream_index;
        FILE *stream_values;
        stream_index = fmemopen(scan_index, strlen(scan_index), "r");
        stream_values = fmemopen(scan_values, strlen(scan_values), "r");
       

        while(fscanf(stream_index, "%d", &index)!=EOF)
        {
          //  printf("Index is %d\n", index);

            char word[1000];
            fscanf(stream_values, "%s", word);
           // printf("Word is %s\n", word);

            word_list[index] =(char *)malloc(sizeof(word));
            strcpy(word_list[index], word);

           // printf("Word in list is %s\n",word_list[index]);

            //getchar();
        }

        fclose(stream_index);
        fclose(stream_values);

        int i;
        for(i=1; word_list[i]; i++)
        {
            printf("%s\n",word_list[i]);
            free(word_list[i]);
        }
        printf("\n");


    }



    return 0;
}



Post Reply

Return to “Volume 4 (400-499)”