Sorting, basic programming
We call a sequence of integers nice if and only if they can be arranged into a sequence of distinct consecutive numbers.
The problem can be described as the following process: initially, there was a sequence B consisting of N-1 integers, which was a nice sequence. Then, number X was inserted somewhere into B to form a new sequence A. We know that A is not a nice sequence, i.e. integers in A cannot be arranged into a sequence of distinct consecutive numbers. The task is to for a given sequence B found the number X, which was inserted into B to form B. It is guaranteed that there exists one unique answer to the problem and N \geq 3.
Sort the given sequence and notice that there is sufficient to check 3 separated cases defining X.
In the first subtask we know that N is at most 1000, so one possible solution is to iterate over all numbers in A, and for each such number check if A without that number is a nice sequence.
Let’s assume that we want to check that A without its i-th element, i.e. A[i] is a nice sequence. If it is, then we know that the answer to the problem is A[i], because the answer is guaranteed to be unique. In order to check if A without A[i] is a nice sequence, we can build a new sequence C which have all elements from A except A[i], sort C in ascending order and check if all two consecutive elements of sorted C are consecutive integers. Notice that since it’s guaranteed that the answer exists and it’s unique, then there exists i such that A without A[i] is a good sequence and it will be found by the above process because it checks all i. The time complexity per a single test case is O(N \cdot N \cdot \log N), because for each of N choices of i we perform a sort of N-1 elements followed by a linear check over these elements, and it is enough to get accepted. This complexity can be slightly improved to O(N^2) by sorting the input sequence at the beginning.
In the second subtask, N can be at most 10^5, so the method used for the first subtask is too slow here.
Let’s consider a sequence B, i.e. the sequence into X was inserted to form A. The main observation is since we know that B was nice, then there are just 3 possible cases to check:
- X + 1 is smaller than the minimum element of B
- X - 1 is larger than the maximum element of B
- X is equal to one of the elements of B
Notice that the above 3 cases indeed cover all possibilities. In order to prove that, let m be the smallest element of B and let M be the largest element of B. We know that X cannot be equal to m-1, because then A would be a nice sequence and we know it’s not. Similarly, X cannot be equal to M+1, because then A would also be a nice sequence. Now, each integer except m-1 and M+1 falls into one of the above 3 cases, so the only remaining thing to do is to check which of these cases is true. In order to do that, at the beginning we sort A. Then checking cases 1 and 2 is very easy - just compare two smallest elements and two largest elements of A. To check if the third case is true, we can just iterate over sorted sequence A and check if any two its consecutive elements are equal. The total time complexity of this method is O(N \cdot \log N) and it’s dominated by the sorting phase.