文章目录

原题

C. Table Compression
time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Little Petya is now fond of data compression algorithms. He has already studied gz, bz, zip algorithms and many others. Inspired by the new knowledge, Petya is now developing the new compression algorithm which he wants to name dis.

Petya decided to compress tables. He is given a table a consisting of n rows and m columns that is filled with positive integers. He wants to build the table a consisting of positive integers such that the relative order of the elements in each row and each column remains the same. That is, if in some row i of the initial table ai, j < ai, k, then in the resulting table ai, j < ai, k, and if ai, j = ai, k then ai, j = ai, k. Similarly, if in some column j of the initial table ai, j < ap, j then in compressed table ai, j < ap, j and if ai, j = ap, j then ai, j = ap, j.

Because large values require more space to store them, the maximum value in a should be as small as possible.

Petya is good in theory, however, he needs your help to implement the algorithm.

Input

The first line of the input contains two integers n and m (, the number of rows and the number of columns of the table respectively.

Each of the following n rows contain m integers ai, j (1 ≤ ai, j ≤ 109) that are the values in the table.

Output

Output the compressed table in form of n lines each containing m integers.

If there exist several answers such that the maximum number in the compressed table is minimum possible, you are allowed to output any of them.

Examples
input
2 2
1 2
3 4
output
1 2
2 3
input
4 3
20 10 30
50 40 30
50 60 70
90 80 70
output
2 1 3
5 4 3
5 6 7
9 8 7
Note

In the first sample test, despite the fact a1, 2 ≠ a21, they are not located in the same row or column so they may become equal after the compression.

分析

第一次看到这个题的反应就是,参考答案。找到若干个网上的答案后,试着尝试读懂程序。2个小时后的感受就是“智商”不够,先补补课。

目前为止,我终于搞懂了该题的解法思路。在这里分享下鄙见。

首先,题意大家都明白了,不再赘述。如果你不懂题意,请自行按下如下按键:Command + d(Windows:ctrl + d)。

好,你懂题意了。为了分析,先简化下。给原题增加个条件:矩阵中的元素保持唯一。所以,我们解决的思路似乎会更简明。

我们将n*m的矩阵分成n*m个子集,也就是说每个子集仅包含一个元素,且各不相同。此时,我们要保证同行和同列相对关系相等。所以,此时我们需要建立一个数组来维护所有子集(一个元素)的大小关系。我们只维护每行和每列的。比如第一行的维护关系如下:

e[3] = {1} // 代表下标为3的子集大于下标为1的子集(注元素下标我们从1开始计)

e[1] = {2} // 同上

这样我们在计算结果时利用动态规划的思想来取得每个压缩后的子集,如下:

dp[3] = max(1, dp[1] + 1); // 因为3集合要比1集合大,所以我们3集合的最小值为1何dp[1] + 1的其中最大的一个

此时你已经动了大致的思路了,这时放开题的条件,允许原始矩阵的元素相同。那么,我们仍然要在之前分析的基础上来进行求解。那么,我们利用并查集的方式来维护每个独立的子集。简单的说,就是原始数据中的第3个元素和第6个元素对我们来说,是属于同一个子集,只不过这个子集里面有两个元素而已。那么我们用p来维护元素的所属子集关系。

程序范例

import java.util.Arrays;
import java.util.Scanner;

/**
* A. Watchmen
* http://codeforces.com/contest/650/problem/A
*
* @author GenialX
*
*/
public class Q1 {
public static void main(String args[]) throws Exception{
Scanner in = new Scanner(System.in);
int pairCount = in.nextInt();
long sum = 0;
int[] x = new int[pairCount];
int[] y = new int[pairCount];
long[] z = new long[pairCount];
for(int i = 0; i < pairCount; i++) {
x[i] = in.nextInt();
y[i] = in.nextInt();
z[i] = (x[i] + 1000000000L);
z[i] *= 10000000000L;
z[i] += y[i];
}

Arrays.sort(x);
Arrays.sort(y);
Arrays.sort(z);;

sum = Q1.getIntSum(x, pairCount);
sum += Q1.getIntSum(y, pairCount);
sum += Q1.getLongSum(z, pairCount);

System.out.println(sum);
in.close();
return ;
}

public static long getLongSum(long[] x, int N) {
long xCnt = 0;
long xLast = Long.MIN_VALUE;
long sum = 0;

for(int i = 0; i < N; i++) {
if(xLast != x[i]) {
sum -= xCnt * (xCnt – 1) / 2;
xLast = x[i];
xCnt = 1;
} else {
xCnt++;
}
}
sum -= xCnt * (xCnt – 1) / 2;

return sum;
}

public static long getIntSum(int[] x, int N) {
long xCnt = 0;
int xLast = Integer.MIN_VALUE;
long sum = 0;

for(int i = 0; i < N; i++) {
if(xLast != x[i]) {
sum += xCnt * (xCnt – 1) / 2;
xLast = x[i];
xCnt = 1;
} else {
xCnt++;
}
}
sum += xCnt * (xCnt – 1) / 2;

return sum;
}

}

文章来源:胡旭博客 => Codeforces Round #345 (Div. 1) C. Table Compression
参考文章:

Share:

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.