Algorithm to find weighted ranking?

Question

I want to find the rank of a person based on different parameters and each parameter has different weights assigned to them.

For e.g. Suppose if there are three items a, b and c, these items could have any value between 0 to 10,00,000. There are weights assigned to them a = 0.3 , b=0.2, c=0.1. Suppose there are 10,000 people have these items with different quantity. Suppose a person X have items a=2200, b = 4000, c= 1280. Then how could I find the rank of person x within 10,000 people that where he lies.

Please let me know if needs more details.

Immediate help appreciated.

Answer 1

First, calculate the weighted points of all persons. That is,

P[i] = Wa * a[i] + Wb * b[i] + Wc * c[i];

Then sort all P[i] by its values.

You can define and use the custom compare function to get rank easily.

    for (int i = 0; i < n; i++) rank[i] = i;
    sort (rank, rank + n, [P](int i, int j) {
        return P[i] < P[j];
    });

In case of dynamic insert and get rank operation, you have to use order-statistics tree. Then you can get the performance result of O(logn) for both operations.

Please refer codeforces and this article for more details.