Given an array with n integers, and you are given two indices i and j (i ≠ j) in the array. You have to find two integers in the range whose difference is minimum. You have to print this value. The array is indexed from 0 to n-1...
This problem easy version : http://lightoj.com/volume_showproblem.php?problem=1100 But , If The input numbers in range [-10^9 , 10^9] , How to solve it ?
I solved easy version just iterating the range :P
Notice, the answer is Min(a[i], a[i + 1], ..., a[j]) — Max(a[i], a[i + 1], ..., a[j]).
Wrong idea :(
In case abs(x — y) instead of x — y just took twice same number. I haven't account and can't read problem statement :(
First compress the numbers and also store a reverse mapping
Use Mo's algorithm and keep two sets S1 and S2 and an array count1[] and map count2[]
S1 stores the elements in L , R
S2 stores all the consecutive differences in L to R had the elements in this range been sorted (element[i] — element[i-1])
count1[i] stores the number of times i is in S1 count2[i] stores the number of times i is in S2
answer is always the lowest element of S2 while applying Mo's after you have moved the pointers for a certain query .
Can you please explain , How to the deletion of MO's algorithm will work.. In case of insertion, It is easy .. But deletion ??
Say count1[i] has become 0 . Here i is the compressed value of some element whose value is say RM[i] . So this element i would be contributing to S2 . Let i2 be the element just above i present in set S1 and i1 be the element just below i present in set S1 (Which can be easily done by STL functions) . So now we have to do :
count2[RM[i2] — RM[i]]-- , count2[RM[i] — RM[i1]]-- , count2[RM[i2] — RM[i1]]++ .
Of course if any of count2[X] becomes zero after subtracting you erase X from S2 .
Notice that integers itself are small enough. They are between 1 and 1000. So, if |i-j|>=1000 there would be at least to equal integers in that range (Dirichlet principle). In other case you can just sort them and find an answer iterating.
UPD. Sorry, I forgot about larger range of numbers...
He is asking for the solution when the integers are in range [-10^9 , 10^9] .
I just got AC using Mo's algorithm (code). After that I locked the problem and opened the judge solution and I felt stupid because it really really simple. The main idea is that the integers are in range [1,1000] so there are at most 1000 unique numbers so if R-L+1>1000 in the current query, then we have a repeating number and the answer is 0. So the author checks whether the current interval's length in greater than 1000 and if yes, he prints 0. Otherwise, he loops from L to R, counts the integers as we do in counting sort and with one traversal of the array with the counted integers he finds the answer :)
UPD: Actually he doesn't do as in counting sort. He takes the numbers in the interval and sorts them using std::sort :)
Topicstarter is asking solution for another problem where constraints are [-10^9, 10^9].
Oh, I missed that, sorry. Actually, my solution won't work in this case(because of the array cnt[1024]) but it can be changed(as StoneCold_ already pointed out) and it will work.
Take high-five, bro! Same above, missed about range in topic :)