EXTRAN - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Kamil Dębowski
Testers: Sergey Kulik
Editorialist: Pawel Kacprzak

DIFFICULTY:

Simple

PREREQUISITES:

Sorting, basic programming

PROBLEM:

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.

QUICK EXPLANATION:

Sort the given sequence and notice that there is sufficient to check 3 separated cases defining X.

EXPLANATION:

Subtask 1

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.

Subtask 2

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:

  1. X + 1 is smaller than the minimum element of B
  2. X - 1 is larger than the maximum element of B
  3. 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.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

1 Like
2

sum of 1 to n numbers is n(n+1)/2 . so if 5 to 15 is the correct sequence then its sum is (1 to 15) - (1 to 4). So calc sum of the inputs you are given. In the sum one number is odd man out. While giving the inputs you also have to calculate min, nextmin, max and next max.

if inputsum - min is equal to sum ( nextmin to max ) then return min.
else if inputsum-max == sum( min to nextmax ) then return max
else return inputsum - sum(min to max).

time complextiy is o(n) and you avoided sorting.

1 Like
3

wow,it looks great but please show me ur code.thanks

4

Thanks.

https://www.codechef.com/viewsolution/13023864

5

Hey,
Can anyone please help me out to understand why my code gives NZEC runtime error

InputReaderNew13 in = new InputReaderNew13(System.in);
PrintWriter pw = new PrintWriter(System.out);
IOUtilsNew13 io = new IOUtilsNew13();

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            
    int T = in.readInt();
    int N ;
    long a[];
    long ans=0;
    while(T--!=0)
    {
        N = in.readInt();
        a = new long[N];
        //StringTokenizer st = new StringTokenizer(br.readLine()," ");
        String so[] = br.readLine().split(" ");
        
        
        for (int i = 0; i < N; i++)
        {	
            
                a[i] = Long.parseLong(so[i]);
        }
        
        Arrays.sort(a);
        for(int i=0;i<N-1;i++)
        {
            if(a[i]==a[i+1])
            {
                ans = a[i];
                break;
            }
        }
        if(a[0]+1 != a[1])
            ans = a[0];
        else if(a[N-2]+1 != a[N-1])
            ans = a[N-1];
        pw.println(ans);
    }
    pw.flush();