Maximum k such that A[0]<A[k], A[1]<A[k+1], ..., A[k-1]<A[2*k-1], after sorting each k-sized window

user_16077632 0
Viewed 89

I need the efficient algorithm for this problem (time comlexity less than O(n^2)), please help me:

a[i..j] is called a[i..j] < b[i..j] if a[i]<b[i], a[i+1]<b[i+1], ..., a[j]<b[j] after sorting these 2 arrays.
Given array A[1..n], (n<= 10^5, a[i]<= 1000). Find the maximum of k that A[1..k] < A[k+1..2k]

For example, n=10: 2 2 1 4 3 2 5 4 2 3 the answer is 4

Easily to see that k <= n/2. So we can use brute-forces (k from n/2 to 1), but not binary search.

And I don't know what to do with a[i] <= 1000. Maybe using map???

search sorting algorithm
1 Answers

Use a Fenwick tree with range updates. Each index in the tree represents the count of how many numbers in window A are smaller than it. For the windows to be valid, each element in B (the window on the right) must have a partner in A (the window on the left). When we shift a number x into A, we add 1 to the range, [x+1, 1000] in the tree. For the element shifted from B to A, add 1 in its tree index. For each new element in B, add -1 to its index in the tree. If an index drops below zero, the window is invalid.

For the example, we have:

2 2 1 4 3 2 5 4 2 3
2 2
 |
Tree:
add 1 to [3, 1000]
add -1 to 2
idx  1  2  3  4  5
val  0 -1  1  1  1 (invalid)


2 2 1 4 3 2 5 4 2 3
2 2 1 4
   |
Tree:
add 1 to [3, 1000]
add 1 to 2 (remove 2 from B)
add -1 to 1
add -1 to 4
idx  1  2  3  4  5
val -1  0  2  1  2 (invalid)


2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2
     |
Tree:
add 1 to [2, 1000]
add 1 to 1 (remove 1 from B)
add -1 to 3
add -1 to 2
idx  1  2  3  4  5
val  0  0  2  2  3 (valid)


2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2 5 4
       |
Tree:
add 1 to [5, 1000]
add 1 to 4 (remove 4 from B)
add -1 to 5
add -1 to 4
idx  1  2  3  4  5
val  0  0  2  2  3 (valid)


2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2 5 4 2 3
         |
Tree:
add 1 to [4, 1000]
add 1 to 3 (remove 3 from B)
add -1 to 2
add -1 to 3
idx  1  2  3  4  5
val  0 -1  2  3  4 (invalid)
user_20347870
Related