Olympiad hobby. Warm up

As a hobby, I solve programming olympiad puzzles. It helps to distract from everyday problems, allowing for another hour to leave the world in your own astral. My brain, thanks to this hobby, is in constant sports form.

I decided that it would be nice to share with you the algorithms, reflections, results, and also to receive high-quality criticism of my ways of solving problems.
We will take the task, disassemble it in parts, analyze, invent various solutions, choose the best one, and then bring the “great judges” to court. For many, in my opinion, such an hour of unloading will be very useful, but it will just be interesting for someone to compete and invent their own algorithm.

I will take the tasks from http://uva.onlinejudge.org/ , where there is a fairly large collection of tasks for every taste, and there you can check your solution. I will choose randomly and always bring what I have begun to the final decision, which will be marked by the “Accepted” rating. To solve these problems, we need knowledge of one of the programming languages: c, c ++, java, pascal, as well as patience, logic and basic knowledge of the English language, since The conditions of the tasks we receive in English.
')
So, we begin with a simple task from the “For beginners” set for a warm-up to test our abilities.

Briefly translate the condition of the problem (free translation):

The government decided to tag all the people so that they could be followed. To do this, a tiny computer is implanted in each left wrist. This computer has all kinds of personal information, as well as a transmitter to monitor movement.
Each computer contains a unique identification code consisting of no more than 50 characters, constructed from lowercase letters of the English alphabet (26 letters). The character set for the code is chosen randomly.
Suppose that 3 characters “a”, 2 characters “b” and 1 character “c” were chosen as the character set. Under these conditions, 60 different identification codes can be constructed.

abaabc
abaacb
ababac

These are 3 of the possible codes, based on the above conditions, listed in alphabetical order.
You need to write a program that helps generate these identification codes. The program must accept a sequence of characters (no more than 50 lower case letters that can be repeated) and print the next identification code in alphabetical order, if one exists. If the given code is the last (in alphabetical order) for a given set of characters, then you need to type "No Successor".
The input will contain a series of lines, each of which will represent an identification code. The "#" symbol will mark the end of the input
The output should contain one following code for each input code.

If abaacb is input , then our program should answer ababac .

In this place, those interested should minimize the article and try to solve the problem on their own. I guarantee that when you get "Accepted", you will feel a slight emotional lift and get a boost of energy.

Obviously, this is a task from the “permutation” domain, i.e. ababac is the next permutation in lexicographical order after abaacb . In my opinion, this algorithm is described very well here, so we will not particularly analyze it. Let us write for ourselves the basic steps of the algorithm:

1. At the first step of the program, moving from the end of the array, we compare the neighboring elements, if the previous element (by location in the array) is greater than the next one, move further, if less, stop and remember its number (m), this element will be changed.
2. Elements to the left of the m-th, do not change. Among the elements standing on the right, you need to select the element (k), which should take the place of the m-th. This is the minimum element among those that are greater than mth.
3. Change the m-th and k-th elements.
4. It remains to arrange in ascending order the elements to the right of the new m-th element, but since they are ordered descending, just wrap them.

The main thing that you need to remember to take into account is that if we could not find the next permutation, then we need to return “No Successor”.

It remains only to estimate how long our program will work under the worst conditions, in order not to skip over the time limit of 3 seconds. Suppose that N is the number of characters in the input sequence. Under the worst conditions, in the first step, the program will have to perform N comparisons (all elements are arranged in ascending order). In the second step, the search for the minimum is conducted - this is another N comparisons. In the third and fourth steps, we swap N elements in places, which will require N read / write operations to the array. As a result, we obtain 2N comparisons and N rewrites. Provided that N is not greater than 50 (the condition of the problem), the operation of our algorithm will take a few milliseconds.

Well, let's go to pass . My solution in C ++ can be downloaded here .

Accepted (0.008). Good luck and you!