MixingColors--SRM621 DIV2

 Problem Statement for MixingColors

 

Definition

Class:	MixingColors
Method:	minColors
Parameters:	int[]
Returns:	int
Method signature:	int minColors(int[] colors)
(be sure your method is public)

Notes

-

XOR (exclusive or) is a binary operation, performed on two numbers in binary notation. First, the shorter number is prepended with leading zeroes until both numbers have the same number of digits (in binary). Then, the result is calculated as follows: for each bit where the numbers differ the result has 1 in its binary representation. It has 0 in all other positions.

-

For example 15 XOR 55 is performed as follows. First, the numbers are converted to binary: 15 is 1111 and 55 is 110111. Then the shorter number is prepended with leading zeros until both numbers have the same number of digits. This means 15 becomes 001111. Then 001111 XOR 110111 = 111000 (the result has ones only in the positions where the two numbers differ). Then the result can be converted back to decimal notation. In this case 111000 = 56, so 15 XOR 55 = 56.

Constraints

-

colors will contain between 1 and 50 elements, inclusive.

-

Each element of colors will be between 1 and 1,000,000,000, inclusive.

-

All elements of colors will be distinct.

Examples

0)

{1, 7, 3}

Returns: 3

Obviously, Danica can just buy the three colors she needs. However, there are also other optimal solutions. For example, she could buy colors 1, 2, and 4 instead. Then, she can mix these colors as follows:

• She already has color 1.
• She can obtain color 3 by mixing colors 1 and 2: we have 1 XOR 2 = 3.
• She can obtain color 7 by first mixing colors 1 and 4 to produce color 5 (as 1 XOR 4 = 5), and then mixing colors 5 and 2 (as 5 XOR 2 = 7).

1)

{10}

Returns: 1

Danica should buy color 10 only.

2)

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

Returns: 4

Danica can, for instance, buy colors 11, 13, 14, and 15.

3)

{534, 251, 76, 468, 909, 410, 264, 387, 102, 982, 199, 111, 659, 386, 151}

Returns: 10

4)

{4, 8, 16, 32, 64, 128, 256, 512, 1024}

Returns: 9

 

 

 

SRM621 1000分 第3题算法解答_____________________________________________________________________________

 

看了算法解释，真心佩服，自己数学融汇贯通的能力差啊。当时怎么也想不出来。

 

数学原理：求rank，即通过最大线性无关组获得，计算机解法，高斯消元法(Gauss Elimination)

矩阵A的秩=rank(A) = rank({A1,A2, .... Am});

 

每一个数字，都可以表示为一个二进制向量，如3={0,1,1}，向量的纬度 m =  最大数的位数（直接用32也可以）

 

以{3,5,6}为例：

于是：矩阵A = {3,5,6} =

0 1 1

1 0 1

1 1 0

 

采用高斯消元法：注，这个时候的消元不是通过线性加减，而是异或准则

0 1 1   

1 0 1   

1 1 0

 选择主行（即第A(0,0)!=0即可）交换

1 1 0

0 1 1

1 0 1

 

第0行与第2行异或——》第2行

1 1 0

0 1 1

0 1 1

 

第1行与第二行异或

1 1 0

0 1 1

0 0 0

 

于是，对角线上不为0的个数= rank(A)=2,所以答案为2

 

 

 

import java.util.*;
/**
 * User: Free
 * Date: 14-5-20
 * Time: 下午11:51
 */
public class MixingColors {
    public int minColors(int[] colors) {
        int len = colors.length;
        Arrays.sort(colors);
        int max = 1;
        int maxCount = 31;
        maxCount = Integer.toBinaryString(colors[colors.length - 1]).length();
        int i = 0;
        byte[][] A = new byte[colors.length][maxCount];
        for (; i < colors.length; i++) {
            String bits = Integer.toBinaryString(colors[i]);
            for (int j = 0; j < bits.length(); j++) {
                A[i][maxCount - bits.length() + j] = (byte) (bits.charAt(j) - '0');
            }
            for (int j = 0; j < maxCount - bits.length(); j++) {
                A[i][j] = 0;
            }
        }
        //gauss elimination
        // process  Row =r,Col=c,A[r][c]==0
        int r = 0;
        int c = 0;
        int pivot;
        for (r = 0; r < colors.length; r++) {
            do {
                if (c >= maxCount)
                    break;
                for (pivot = r; pivot < colors.length; pivot++) {
                    if (A[pivot][c] == 1) {
                        break;
                    }
                }
                if (pivot < colors.length) {
                    //swap ROW　pivot,r
                    if (pivot != r) {
                        for (int j = c; j < maxCount; j++) {
                            byte t = A[pivot][j];
                            A[pivot][j] = A[r][j];
                            A[r][j] = t;
                        }
                    }
                    //eliminate;
                    for (int curRow = r + 1; curRow < colors.length; curRow++) {
                        if (A[curRow][c] != 0) {
                            //XOR
                            for (int j = c; j < maxCount; j++) {
                                A[curRow][j] ^= A[r][j];
                            }
                        }
                    }
                    c++;
                    break;
                } else {
                    c++;
                }
            } while (true);

        }
        //calc rank(A)
        int rankRow = 0;
        for (int row = 0; row < A.length; row++) {
            for (int col = 0; col < A[0].length; col++) {
                if (A[row][col]
                        != 0) {
                    rankRow++;
                    break;
                }
            }
        }
        return rankRow;
    }
    public static void main(String args[]) {
        MixingColors mix = new MixingColors();
        System.out.println(mix.minColors(new int[]{4, 8, 16, 32, 64, 128, 256, 512, 1024}));
//        System.out.println(mix.minColors(new int[]{3, 5, 6}));
//        System.out.println(mix.minColors(new int[]{1, 3, 4, 5, 6, 8}));
//        System.out.println(mix.minColors(new int[]{534, 251, 76, 468, 909, 410, 264, 387, 102, 982, 199, 111, 659, 386, 151}));
//
//        System.out.println(mix.minColors(new int[]{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912}));
    }

}