2015-06-05

[ACM 題目] 優勢商品

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

一份產品有很多屬性，把每一個屬性當作一個維度，當成 $D$ 個維度的向量，當維度越多時絕對支配 (各方面都是最好的) 的機率就越低。若把 $D = 2$，就是在二維空間中的支配點 (Zerojudge d555 平面上的極大點)。由於絕對優勢的產品隨著維度增加而變少，定義出一種相對優勢產品，給定一個 $K$，若 $p_i$ 支配 (k-dominate) $p_j$，必須滿足下列三條：

$\exists S' \subseteq S, |S'| = K$
$\forall s_r \in S', p_i.s_r \geq p_j.s_r$
$\exists s_t \in S', p_i.s_t > p_j.s_t$

用中文解釋這幾條數學公式，假設有 6 個維度的產品，目標 $K = 5$，則表示要在 6 的維度中任意挑選 5 個維度比較，若存在一種挑法可以支配，則可以說 $p_i$ k-dominate $p_j$

例如現在有 8 台筆記型電腦，共有 6 種屬性可以比較，數值越大越好。

Notebook	CPU	RAM	HDD	HDD S.	Q.	VRAM
$N_1$	3	3	5	6	6	8
$N_2$	9	4	9	7	7	9
$N_3$	8	4	7	9	2	7
$N_4$	5	6	8	9	5	9
$N_5$	9	7	9	6	2	4
$N_6$	6	6	6	5	3	5
$N_7$	5	7	3	8	4	6
$N_8$	4	4	8	6	6	4

若要判斷 $N_2$ 是否支配 $N_3$，從中挑取 (CPU, RAM, HDD, HDD S., Q.) 這 5 個屬性比較，得到 $N_2$ 勝過於 $N_3$。最後可以發現到 $N_2$ 這產品可以支配 $N_1, N_3, N_5, N_6, N_8$。

現在問題來了，要找到不被任何產品支配的產品 (k-dominant skyline)。如上表 8 項產品的情況，只會有 $N_2, N_4$。

Input

第一行會有一個整數 $T$ 表示有多少組測資。

每一組測資第一行會有三個整數 $N, D, K$，分別表示產品數量、產品屬性種類、以及支配比較的屬性種類。接下來會有 $N$ 行數據，每一行上會有 $D$ 個整數 $s_j$ 表示一個產品的屬性，產品按照輸入順序編號。

$N < 1024$
$0 < D, K < 8$
$0 < s_j < 1000$

Output

對於每組測資輸出一行，輸出該組測資所有的 k-dominant skyline 的產品編號，由小到大輸出。若不存在則輸出 NONE。

Sample Input

4
2 3 1
20 20 20
20 20 20
2 5 1
20 5 20 20 20
5 20 20 20 20
4 6 5
9 4 9 7 7 9
9 7 9 6 5 4
9 6 9 8 3 3
1 2 3 9 2 2
8 6 5
3 3 5 6 6 8
9 4 9 7 7 9
8 4 7 9 2 7
5 6 8 9 5 9
9 7 9 6 2 4
6 6 6 5 3 5
5 7 3 8 4 6
4 4 8 6 6 4

Sample Output

Case #1: 1 2
Case #2: NONE
Case #3: 1
Case #4: 2 4

Solution

這是一篇論文題目 k-dominant skyline set，網路上提出不少算法，看起來都是有容錯率。

這一題只是介紹題，沒有強求高效算法計算，直接 $O(N^2)$ 的比較，稍微優化一下就可以。若要快一點，按照總和由大排到小，從概念上總和越大，表示支配別人的機率越高，那麼根據這種貪心思路去篩選，可以減少很多不必要的比較，速度會更快些。

#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 1024;
int N, D, K;
vector< vector<int> > C;
struct Product {
    int v[8], id;
    bool operator<(const Product &a) const {
        return sum() > a.sum();
    }
    int sum() const {
        int s = 0;
        for (int i = 0; i < D; i++)
            s += v[i];
        return s;
    }
    int domain(Product &u) {
        for (auto &x : C) {
            int h1 = 1, h2 = 0;
            for (auto &e : x) {
                h1 &= v[e] >= u.v[e];
                h2 |= v[e] >  u.v[e];
            }
            if (h1 && h2)   return 1;
        }
        return 0;
    }
} item[MAXN];
int used[MAXN];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &D, &K);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < D; j++)
                scanf("%d", &item[i].v[j]);
            item[i].id = i;
        }
        sort(item, item+N);
        
        C.clear();
        for (int i = 0; i < (1<<D); i++) {
            if (__builtin_popcount(i) == K) {
                vector<int> A;
                for (int j = 0; j < D; j++) {
                    if ((i>>j)&1)
                        A.push_back(j);
                }
                C.push_back(A);
            }
        }
        
        vector<Product> filter;
        vector<int> ret;
        for (int i = 0; i < N; i++)
            used[i] = 0;
        for (int i = 0; i < N; i++) {
            if (used[i] == 0) {
                filter.push_back(item[i]);
                for (int j = i+1; j < N; j++) {
                    if (used[j] == 0 && item[i].domain(item[j]))
                        used[j] = 1;
                }
            }
        }
        for (int i = 0; i < filter.size(); i++) {
            int ok = 1;
            for (int j = 0; j < N && ok; j++) {
                if (item[j].domain(filter[i]))
                    ok = 0;
            }
            if (ok == 1)
                ret.push_back(filter[i].id);
        }
        
        sort(ret.begin(), ret.end());
        printf("Case #%d:", ++cases);
        for (int i = 0; i < ret.size(); i++)
            printf(" %d", ret[i]+1);
        puts(ret.size() ? "" : " NONE");
    }
    return 0;
}

Morris' Blog