Olympiad hobby. Warm up

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

I decided that it would be nice to share with you the algorithms, thoughts, results, as well as get a 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 the court. For many, in my opinion, such an hour of unloading will be very useful, but someone will just be interested to compete and come up with their own algorithm.

I will take tasks from the website 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 at random and always bring what I have started to the final decision, which will be marked by an “Accepted” mark (Accepted). 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, as we obtain the conditions for the tasks in English.

So, we will start with a simple task from the set “For Beginners” for warm-up to test our abilities.

Briefly translate the condition of the problem (free translation):
The government decided to tag all people so that they could be monitored. To do this, a tiny computer is implanted in each person’s left wrist. This computer has all kinds of personal information, as well as a transmitter for controlling movement.
Each computer contains a unique identification code, consisting of no more than 50 characters, built from lowercase English letters (26 letters). The character set for the code is selected unsystematically.
Suppose that 3 characters “a”, 2 characters “b” and 1 character “c” were selected as the character set. Under these conditions, 60 different identification codes can be built.

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 to help generate these identification codes. The program should accept a sequence of characters (no more than 50 lowercase 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 print “No Successor”.
The input will contain a series of lines, each of which will represent an identification code. The symbol "#" will mean the end of the input. The
output should contain one next code for each input code.

If abaacb is fed to the input , then our program should respond ababac .

In this place, those interested should roll up the article and try to solve the problem on their own. I guarantee that when you get "Accepted", you will feel a light spiritual lift and get a boost of vigor.

Obviously, this is a problem from the field of "permutations", i.e. ababac is the next lexicographic rearrangement after abaacb . In my opinion then this algorithm is described very well, so we particularly understand it will not. Let us write out for ourselves the main steps of the algorithm:
  1. At the first step of the program, moving from the end of the array, compare the neighboring elements, if the previous (by location in the array) element is larger than the next, move on, if less, stop and remember its number (m), this element will be changed.
  2. Elements to the left of the mth are not mutable. Among the elements on the right, you need to select the element (k), which should take the place of the mth. This is the smallest element among those that are larger than the mth.
  3. We change the mth and kth elements.
  4. It remains to sort in ascending order the elements to the right of the new mth element, but since they are ordered in descending order, just wrap them.

The main thing that you must 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 evaluate how long our program will work under the worst conditions, so as not to jump over a time limit of 3 seconds. Suppose 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 increasing order). At the second step, the search for the minimum is carried out - this is N comparisons. In the third and fourth steps, we swap N elements, which will require N read / write operations to the array. As a result, we get 2N comparisons and N rewrites. Provided that N is not more than 50 (task condition), the operation of our algorithm will take a few milliseconds.

Well, let's go take it . My C ++ solution can be downloaded here .

Acccepted (0.008). Good luck to you too!

Also popular now: