in Competitive programming

SPOJ PALIN solution

Solution for problem http://www.spoj.com/problems/PALIN/ from SPOJ website.

Sometimes I stuck solving some problems from there (usually because my code either add unneeded new line or doesn’t add needed new line and I am finding what is wrong by trial and error), so here is working solution for PALIN that can save you time if you encounter some strange Wrong Answer or NZEC errors.

The idea is to add 1 to lower digits position of big input number, until they start to form palindrome from boundaries to center of number. There are also checks for special cases when we have numbers like 9998, 9999 or palindrome as input.

Solution below can be optimized even more (e.g. reversenum could be removed if you do some tiny modifications of traversals in addOne and solve functions, so you would have less memory consumption).

C++ Solution:

#include <bits/stdc++.h>

using namespace std;

int N, len;
char num[1000001];
char reversenum[1000001];

bool isPalindrome(char* num)
{
    int start = 0, end = len-1;
    while (start < end) {
        if (num[start++] != num[end--]) {
            return false;
        }
    }

    return true;
}

int addOne(char* num, int len)
{
    ++num[0];
    for (int i = 0, iend = len; i < iend && num[i] > '9'; ++i) {
        num[i] = i == 0 ? '0' : (num[i] - '9') - 1 + '0';
        if (i+1 == len) {
            ++len;
            num[i+1] = '1'; 
        } else {
            ++num[i+1];
        }
    }

    return len;
}

int solve()
{
    len = addOne(num, len); // To ignore palindromes in input
    if (!isPalindrome(num)) { // Check for 999...99 case immediately, so we guarantee that len will not change
        for (int i = 0, iend = len/2; i <= iend; ++i) {
            for (;num[i] != num[len-i-1];) addOne(num + i, len - i);
        }
    }

    for (int i = len - 1; i >= 0; --i) {
        cout << num[i];
    }
    cout << endl;
}

int main()
{
    scanf("%d\n", &N);

    char c;

    for (; N > 0 && !feof(stdin); --N) {
        len = 0;
        while ((c = fgetc(stdin)) != '\n' && c != EOF) reversenum[len++] = c;
        for (int i = 0; i < len; ++i) num[i] = reversenum[len-i-1];
        solve();
    }

    return 0;
}

 

Bruteforce solution in C++:

(it will hit TLE on SPOJ, but you can use it to verify your algorithm)

#include <bits/stdc++.h>

using namespace std;

int N, len;
char num[1000001];
char reversenum[1000001];

bool isPolyndrome()
{
    int start = 0, end = len-1;
    while (start < end) {
        if (num[start++] != num[end--]) {
            return false;
        }
    }

    return true;
}

int solve()
{
    do {
        // Add +1 to number
        ++num[0];
        for (int i = 0, iend = len; i < iend && num[i] > '9'; ++i) {
            if (i+1 == len) ++len;
            num[i] = i == 0 ? '0' : (num[i] - '9') + '0';
            ++num[i+1];
        }
    } while (!isPolyndrome());

    for (int i = len - 1; i >= 0; --i) {
        cout << num[i];
    }
    cout << endl;
}

int main()
{
    scanf("%d\n", &N);

    char c;

    for (; N > 0 && !feof(stdin); --N) {
        len = 0;
        while ((c = fgetc(stdin)) != '\n' && c != EOF) reversenum[len++] = c;
        for (int i = 0; i < len; ++i) num[i] = reversenum[len-i-1];
        solve();
    }

    return 0;
}

 

Write a Comment

Comment