Monday, September 15, 2014

UVa Problem 146 - ID Codes

Problem:

Please find the problem here.

Solution:

This is simply the next permutation problem. Thanks to the hint on Competitive Programming, there is a simple call in C++ library named next_permutation that can solve the problem, and therefore I used it.

Suppose we are not given the next_permutation code, how would I solve it? First, note that in order to find the least significant digit to increase, but you can't just increase a digit because this is a permutation, one also need to change another digit to change as well. Surely we don't want to alter the more significant digits, so we can only pick the less significant ones.

Formally, one scan from right to left, trying to find a digit such that there is a larger digit to its right. If such a digit does not exist, we can conclude there is no successor. Otherwise, change that digit to the least larger one found on the right, and sort the rest of the digits, that gives the answer.

For example, the successor of 1, 2, 3, 3 is 1, 3, 2, 3, this is done by noting 2 < 3, so we switch 2 to 3, and just sort [2, 3], which give [2, 3]

As a more exotic scenario, let's look at 1, 4, 3, 2, its successor is 2, 1, 3, 4, this is done by noting 1 < 2, so we switch 1 to 2, and just sort [1, 4, 3], which gives [1, 3, 4].

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=82

#include "UVa146.h"

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int UVa146()
{
    vector<char> line;
    while (!cin.eof())
    {   
        char c = cin.get();
        if (c != -1)
        {
            if (c != '\r' && c != '\n')
            {
                if (c == '#')
                {
                    break;
                }
                line.push_back(c);
            }
            else
            {
                if (next_permutation(line.begin(), line.end()))
                {
                    for (vector<char>::iterator i = line.begin(); i != line.end(); i++)
                    {
                        cout << *i;
                    }
                    cout << endl;
                }
                else
                {
                    cout << "No Successor" << endl;
                }
                line.clear();
            }
        }
    }

    return 0;
}

No comments :

Post a Comment