Hello November

Hello November!

I guess for once I should write about a problem I've solved with my team mates in a recent contest. This problem is interesting because it was not expected to run in time limit but it did (probably because the test data for the problem is randomly generated rather than specialised test data designed to break algorithm I have listed). I know no one will be interested but I don't care.

Given an array of integers A of size at most 200,000 (1 <= A[i] <= 10,000) and Q queries (Q <= 15,000) where each query is of the form l, r. For each query, find the minimum |A[i]-A[j]| where l <= i, j <= r.

Now, if we are to find the maximum absolute difference, it will be easy as we just need to find the maximum and minimum integer in the interval. Each query can be easily solved by using a segment tree (with segment tree, we can even support a dynamic version) or dynamic programming in O(log n).

For the above question, I have no idea how to do it except by sorting the numbers in the interval and doing a linear scan. We realised that the range of A[i] is actually quite limited. So, if the difference of l and r is large ( > 10,000), by pigeonhole principle, the answer for the query is 0. For the other case, we just did counting sort to sort the elements in the interval and followed by a linear scan. A rough estimate that we had was that this algorithm will take at least 150 million operations on the worst test data (A = 1,2,...,10,000 with 15,000 queries of l = 1 and r = 10,000). There is supposed to be 10 test cases for this question. However, we managed to get it accepted at 4h 38min and that brought us to rank 5 in the contest. It is not too bad given our lousy start and our extremely large number of wrong submissions to problem A.