解題區►出題解題

[ACM 題目] 優勢商品

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

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

Solution

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

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

1