Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: K-Anonymous Sequence
Description The explosively increasing network data in various application domains has raised privacy concerns for the individuals involved. Recent studies show that simply removing the identities of nodes before publishing the graph/social network data does not guarantee privacy. The structure of the graph itself, along with its basic form the degree of nodes, can reveal the identities of individuals. To address this issue, we study a specific graph-anonymization problem. We call a graph k-1 other nodes in the graph with the same degree as . And we are interested in achieving vk-anonymous on a graph with the minimum number of graph-modification operations. n nodes out of the entire graph and list their degrees in ascending order. We define a sequence Gk-anonymous if for every element , there exist at least sk-1 other elements in the sequence equal to . To let the given sequence sk-anonymous, you could do one operation only—decrease some of the numbers in the sequence. And we define the cost of the modification the sum of the difference of all numbers you modified. e.g. sequence 2, 2, 3, 4, 4, 5, 5, with k=3, can be modified to 2, 2, 2, 4, 4, 4, 4, which satisfy 3-anonymous property and the cost of the modification will be |3-2| + |5-4| + |5-4| = 3. Give a sequence with Input The first line of the input file contains a single integer Output For each test, output one line containing a single integer—the minimal cost. Sample Input 2 7 3 2 2 3 4 4 5 5 6 2 0 3 3 4 8 9 Sample Output 3 5 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator