Olympiad hobby. Divide and rule

Good Monday everyone. If Monday is not the most pleasant day for you, then I suggest you relax a bit and feel my hobby. My hobby is solving Olympiad programming tasks: shakes up the brain, stirs the imagination and energizes (though not always positive). Do not believe? Try it yourself, just honestly try to solve the task, get the long-awaited Accepted, and enjoy the received emotions.

Today, the case threw us task number 10474 . This is the task of the ability to use simple algorithms in time, so do not expect something complicated and cunning from it. If you are not interested in solving problems at the expense of a couple of standard algorithms, then skip the topic, and welcome everyone under the cat. We are waiting for a couple of algorithms, the choice of the most convenient solution, and, of course, Accepted!


I choose the task randomly. If a too simple task comes across, or a task that I cannot imagine how to solve, then after several days of torment, I choose another one. But seriously, in addition to the randomness, I try to choose a variety of tasks in order not to dwell on one thing. It may seem to someone that my choice is not very good, I ask you to treat this condescendingly, because this is not my job, but just a hobby, therefore it happens that the tasks are too simple or too typical.
')
Let us, if we come across an easy task, then we will find its fastest or most beautiful solution, then it will not seem to us that we have wasted time. Well, do not forget to share your decisions, which certainly can be more beautiful and faster than mine. Maybe we even manage to invent an algorithm that nobody knows yet, because the audience in Habré is decent;)

The task

Let's get down to business. As I said, today we will solve the problem № 10474
I give a free translation of the conditions of the problem:

Raju and Meena love to play Marbles (presumably the name of the game). They have a lot of plates with numbers. At the beginning, Raju places the plates one after the other in the order of increasing numbers. Then Meena asks Raju to find the number of the first tablet with some number. She counts up to three. If Raju calls the correct number, he gets a point, otherwise Meena receives a point. After a certain number of attempts, the game stops and the one with the most points wins. Today you have a chance to play like Raju. As advanced guys, you use a computer. But do not underestimate Meena, she wrote a program to track the time you spend getting the correct answer. You need to write a program that will help you play the role of Raju.

Input data:
Several tests are possible, but not more than 65. The test begins with two numbers: N is the number of tablets and Q is the number of Meena requests. Then follow N lines containing the numbers written on the N tablets. These numbers are not ordered. Next come Q lines with queries. None of the incoming numbers exceed 10,000, and all numbers are non-negative.
Input ends when N and Q are 0.

Output:
The time limit of the algorithm: 3 seconds.
For each test the serial number of the test is displayed.
One line is output for each request. The format of the string depends on whether the requested number is found among the labels or not. Two options:

• "X found at y" if the first label with the number x is found at position y. Positions are numbered as follows: 1, 2, 3 ...
• “X not found” if there is no sign with the number x.

Example:
Enter:
4 1
2
3
five
one
five
5 2
one
3
3
3
one
2
3
0 0

Conclusion:
CASE # 1:
5 found at 4
CASE # 2:
2 not found
3 found at 3

This task belongs to the class of algorithmic problems, and more specifically to the section "Divide and conquer."

This is a little hint for everyone. Now I recommend creating your own solution, without reading further. Then you will be interested to compare the result with mine.

Our task: to sort the plates with numbers and find the number of the first plate with any number. Two variants of solving this problem occurred to me (besides a simple search for a number with the determination of the number of smaller numbers — that is, in the forehead). Therefore, we will consistently consider both options and determine which is better and why.

Decision

Option 1

I decided that it was worth ordering the array, and then finding the number in it. I know that now many will call me "Kepom." On the site, where I take the problem, the main criterion for the quality of the solution is the program execution time. To speed up the execution time of our algorithm, we will use a quick sort, as well as a binary search in the array. Those. To solve the problem, we consistently implement the algorithm for quickly sorting the input array with numbers, and then the binary search algorithm.

Knowledge of these algorithms, and most importantly, the ability to implement them, is useful in real programming, so I recommend that you familiarize yourself with the algorithms to those who have never implemented them, especially both of them are very simple.

The quick sort algorithm is perfectly described here . I just give a brief description of the steps:
1. In the array selects some element - the reference. Usually they take the central element, but there are cases when it is better to choose some other elements, it depends on the properties of the array.
2. All elements less than the reference number are moved to the left side of the array, and the elements are larger than the reference number to the right. So we divide the array into two subsets. To the left of the support element are elements less than the reference, on the right vice versa.
3. In both subarrays, all steps are performed again if the number of elements is at least two.

Quick sorting has modifications that speed up its work. If you are interested, then try to implement the modification and check the acceleration of the algorithm in practice.

The binary search algorithm in an ordered array is even simpler.
1. Select the central element of the array, which divides the array into two subarrays.
2. If the selected element is greater than the desired one, then continue the search in the left subarray in the same pattern. If less, then right.
As a result, we quickly get to the desired item.

The only thing you need to pay attention to is that a binary search will lead us not necessarily to the first occurrence of the desired number, if there are plates with the same numbers. It is necessary to implement a binary search procedure so that the index of the first occurrence of the desired number is determined.

The first solution: Accepted 0.368

Option 2

If you pay attention to the restriction that is described in the condition: none of the input numbers exceed 10,000, then another solution appears. Before entering numbers on the plates, we can create an array of M for 10,000 elements.
M [i] = 0 if there is no label with the number i
M [i] = r, where r is the number of plates with the number i

We can fill this array immediately when entering numbers. When filling the array, we determine the number of unique numbers.

Next, we will create two more arrays (or an array of structures, if you prefer). The first array of elements will contain unique numbers in ascending order. The second array of positions will contain the position where positions [i] is the number of the first position of the number elements [i]. We can fill these arrays with a single pass through the array M.
0. pos = 0 is the current position, j = 0 is the number of the current unique number
1. We are looking for M [i]! = 0
2. Enter the new number in the elements [j] = i
3. positions [i] = pos
4. Shift pos on M [i], j ++
5. If we have not passed all 10,000 numbers (or you can remember the maximum, to speed up the work), then go to step 1

Now we have the elements array, where we will again search for numbers using a binary search. The answer will be issued from the positions array with the index of the found number in the elements array.

The second solution: Accepted 0.248

Why was the second option faster than the first? The main difference between these two approaches is that in the second version we abandoned the sorting, which is the most time consuming. Instead of wasting time on sorting, we stole more RAM than was required. And a binary search is conducted in an array with a smaller number of elements in cases where there are labels with the same numbers.
The second option would not be applicable if the input numbers were limited only by the capacity of 4 bytes. At the Olympiad, it is sometimes worth paying attention to these kinds of conditions, which are often created by hinting at alternative solutions to the problem.

Why does the task relate to the “Divide and Conquer” section of the algorithms? Because both algorithms used relate to this section, because in quick sorting we divided the array into two parts, and then sorted it, and in the binary search we constantly narrowed down the search by dividing the desired area in half.

This problem has other solutions, try to find a solution that will be faster. It would be interesting to compare the first solution with other sorting algorithms. If you are implementing the first option with a different sorting, write in the comments. Let's try to collect our own statistics of the speed of the various sorts.
You can check your decision here (registration is required).

PS site http://uva.onlinejudge.org/ , whence the task was taken from me, I suddenly stopped loading into FF. I'm not sure that this is exactly the browser problem, but in other browsers the site opens. Keep in mind if you suddenly encounter the same problem.

My solutions, as always, can be downloaded: option 1 and option 2 .

Accepted (0.248). Good luck!

UPD: Thanks to the prompts of Mr. dimoclus , I managed to speed up the second option to Accepted (0.108) ( download )
UPD: Also, please pay attention to the decision of Mr. KapJI , the execution speed of which is 0.104

UPD: Aleksey, a habra reader, managed to get the best time (0.052) among all users of the uva.onlinejudge.org site. Here is his decision. My congratulations!
PS who has an extra invite, do not take pity for Alexey, I think he has something to share with us.