doraemongrapes's blog

How to solve this hard problem about counting ?
By doraemongrapes, 10 years ago, In English

We have an array of integer a[1], a[2], ... , a[N] and a number M.

We take a version of selection sort like this:

for i := 1 to M do
    for j := i + 1 to N do
         if (a[i] > a[j]) then swap(a[i], a[j])

After the program end, count the number of swap operator in it.

Limitation:

1 <= M <= N <= 105

abs(ai) <= 109

Example:

Input:

4 2
3 2 -1 -4

Output:

5

Explain:

After first loop of j: -4 3 2 -1

After second loop of j: -4 -1 3 2

So the number of swap operator is 5.

  • Vote: I like it
  • +34
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 9   Vote: I like it -8 Vote: I do not like it

We can solve this problem by divide-and-conquer.

First, we consider solving the region of [1, n]. For solving this region, we can divide it into two regions, [1, n / 2] and [n / 2 + 1, n].

For each region, we just recursively run the "solve" function to count how many (i, j) pairs that satisfy i < j and Ai > Aj.

What I've said is, we suppose that the solve function can give us the right answer of the region [l, r].

What we should actually do is merge two regions after solving them.

Due to the function is correct, we could just do not consider the (i, j) pairs inside the region, but between two regions that we should merge.

Okay, let us consider how to merge the regions. We suppose after merging, the big region is sorted. We could do this by merge sort.

While doing merge sort, we just have to calculate the (i, j) pairs between the two regions. So we can use two integers indicating the position that we have scanned. For example, we have two regions: 1 3 5 7 and 2 4 6 8. Then, if the first pointer is pointed to 5, we should just consider how many numbers are smaller than five in the second region. So we move the pointer in the second region to 4. So we can solve this problem in just O(n) time complexity.

We just have to do this: solve(l, r) m = (l + r) >> 1 solve(l, m) solve(m + 1, r) merge_and_calculate(l, m, m + 1, r)

So we can get the answer in

Unable to parse markup [type=CF_TEX]

complexity.

Why? We could easily know that T(n) = 2 × T(n / 2) + O(n). Through some mathematical analysis, we could get

Unable to parse markup [type=CF_TEX]

This is my code, hope it'll help:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define gi gI()

using namespace std;

typedef long long ll;

inline ll gI() {
    ll p = 0, flag = 1;
    char c = getchar();
    while ((c < '0' || c > '9') && c != '-') c = getchar();
    if (c == '-') flag = -1, c = getchar();
    while ('0' <= c && c <= '9') p = p * 10 + (c - '0'), c = getchar();
    return p * flag;
}

int const MAXN = 100001;

int n, A[MAXN];
int L[MAXN], R[MAXN];
int ans = 0;

void merge(int l1, int r1, int l2, int r2) {
    //printf("Call Stack(%d, %d, %d, %d)\n", l1, r1, l2, r2);
    memcpy(L + 1, A + l1, sizeof(int) * (r1 - l1));
    memcpy(R + 1, A + l2, sizeof(int) * (r2 - l2));
    int i = l1, j = l2, pos;
    while (i < r1) {
	while (A[i] > A[j] && j < r2) ++ j;
	ans += j - l2;
	++ i;
    }
    i = 1, j = 1, pos = l1;
    while (i <= r1 - l1 && j <= r2 - l2) {
	if (i == r1 - l1 + 1) A[pos++] = R[j++];
	else if (j == r2 - l2 + 1) A[pos++] = L[i++];
	else {
	    if (L[i] < R[j]) A[pos++] = L[i++];
	    else A[pos++] = R[j++];
	}
    }
    //rep(i, l1, r2) printf("A[%d] = %d\n", i, A[i]);
}

void solve(int l, int r) {
    if (l + 1 >= r) return;
    int mid = (l + r) >> 1;
    solve(l, mid);
    solve(mid, r);
    merge(l, mid, mid, r);
}

int main() {
    n = gi;
    rep(i, 1, n) A[i] = gi;
    solve(1, n + 1);
    cout << ans << endl;
    //rep(i, 1, n) printf("A[%d] = %d\n", i, A[i]);
    return 0;
}

UPD. Sorry about misreading the problem.

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How come after the second loop of j, the array becomes -1 -4 3 2 ? According to the pseudocode, shouldn't it become -4 -1 3 2 ?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

During contest, no one solved this problem. It is hard.

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

did anyone figured out the solution ?

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

Does this idea work for the problem? (Maybe I did some mistake in the code) :

My code is wrong and the problem is that after the i-th step when we want to rebuild the minimum-stack, some new elements between i and index.back() will be added. We can handle this by answering this queries :

  • What's the rightmost element greater than X in [L,R].

And it can be done using segment tree.

Code
→ Reply