spoj (Ambiguous Permutations)

Question

I was solving a simple problem on spoj called Ambiguous Permutations(http://www.spoj.com/problems/PERMUT2/), it worked fine when I tested for small inputs, but on submission it shows runtime error - segmentation fault. I'm not able to figure it out (though I've wasted a lot of time, and gained frustration only). Please help.

#include <iostream>
#include <stdlib.h>
#include <string.h>

char arr1[200000];//stores original string.
char arr2[200000];//stores inverse permutation.

long int n;

using namespace std;

int main()
{
    while (1)
    {
        cin >> n;
        if (n == 0)
        {
            exit(0);
        }
        getchar();
        gets(arr1);
        //creating inverse permutation.
        for (long int i = 0; i < 2 * n - 1; i++)
        {
            if (i % 2 == 1)
            {
                arr2[i] = ' ';
            }
            else
            {
                arr2[2 * (arr1[i] - '0') - 2] = i / 2 + '1';
            }
        }
        arr2[2 * n - 1] = '\0';
        //comparing string with it's inverse permutation.
        if (strcmp(arr1, arr2) == 0)
        {
            cout << endl << "ambiguous";
        }
        else
        {
            cout << endl << "not ambiguous";
        }
    }
    return 0;

}

http://stackoverflow.com/questions/1694036/why-is-the-gets-function-dangerous-why-should-it-not-be-used — Neil Kirk, Mar 29 '15 at 14:01
Instead of reserving space for 400000 characters, why don't you use `std::string` which will allocate the appropriate amount of memory? — Neil Kirk, Mar 29 '15 at 14:02

ArnonZ · Accepted Answer · 2015-03-30T10:12:47.600

The problem is that you are using a char array to represent integers, and your code assumes that each number is represented by one char (note for example checking i % 2 == 1 to determine whether number or space).
Hence, any number bigger than 9 will cause correctness / memory problems.

If you'll use integer arrays it will be a lot easier.

You'll stop worrying about the space character ' ', won't need to decrement '0' char from the cells, and won't need your loops to run till 2 * n - 1.

I think it is much clearer this way:

#include <iostream>

using namespace std;

const int MAX_SIZE = 1000;

int arr1[MAX_SIZE];
int arr2[MAX_SIZE];
int size = 0;

bool areArrsEqual()
{
    for (int i = 0; i < size; ++i)
    {
        if (arr1[i] != arr2[i])
        {
            return false;
        }
    }
    return true;
}

int main()
{
    cin >> size;

    while (size > 0 && size <= MAX_SIZE)
    {
        for (int i = 0; i < size; ++i)
        {
            cin >> arr1[i];
        }

        // creating inverse permutation.
        for (int i = 0; i < size; i++)
        {
            // if (arr[i] - 1 >= size) ==> illegal input.
            arr2[arr1[i] - 1] = i + 1;
        }

        // comparing permutation with it's inverse permutation.
        if (areArrsEqual())
        {
            cout << "ambiguous" << endl;
        }
        else
        {
            cout << "not ambiguous" << endl;
        }
        cin >> size;
    }
    return 0;
}

Output:

4
1 4 3 2
ambiguous
5
2 3 4 5 1
not ambiguous
1
1
ambiguous
13
1 2 3 4 5 6 7 8 9 10 11 12 13
ambiguous
0

Thanks, I got the problem (and my way of solving was unnecessarily complicated) — Infinity, Mar 30 '15 at 11:13

spoj (Ambiguous Permutations)

1 Answers1