充电混乱:Google Code Jam [2014]

Question

我发布此作为以下问题的解决方案,与其他人分享.如果有比这更好的答案,那么请发帖.

问题陈述

Shota农民有问题.他刚刚进入他新建的农舍,但事实证明他的所有设备都没有正确配置插座.作为一名现代农民,Shota拥有大量的智能手机和笔记本电脑,甚至拥有一台平板电脑供他最喜欢的牛Wagyu使用.他总共拥有N different devices.

由于这些设备具有不同的规格并且由各种公司制造,它们每个都需要不同的电流来充电.类似地,房屋中的每个出口输出特定的电流.An electric flow can be represented by a string of 0s and 1s of length L.

Shota希望能够同时为他的所有N个设备充电.巧合的是,他的新房子里正好有N个出口.为了配置来自插座的电流,有一个带L开关的主控制面板.第i个开关从房屋的每个出口翻转电流的第i位.例如,如果来自插座的电流是:

Outlet 0: 10
Outlet 1: 01
Outlet 2: 11

然后翻转第二个开关将重新配置电流:

Outlet 0: 11
Outlet 1: 00
Outlet 2: 10

如果Shota有一个需要流量"11"充电的智能手机,需要流量"10"充电的平板电脑,以及需要流量"00"充电的笔记本电脑,那么翻转第二个开关会让他非常高兴!

Shota聘请Misaki帮助他解决这个问题.她测量了房子出口处的电流,并发现它们都是不同的.决定Shota是否可以同时为他的所有设备充电,如果可能的话,找出需要翻转的最小开关数量,因为开关很大很重而且Misaki不想要翻转超过她需要的东西.

Answer 1

这个问题的棘手部分是可以有多种翻转方式,但我们需要找到涉及最小翻转的方式.

这是我的算法来解决这个问题:

1. 假设有N个设备需要D1...Dn自动充电,电源插座可用输出:M1...Mn位

2. 获取设备所需的XOR功率和插座可用的电源可让您了解要翻转的位数以匹配带电源插座的设备.

3. 因此,一旦我们创建了设备和出口的XOR映射,每个二进制数中的1个数字表示所需的翻转次数.我们需要检查的是,是否可以将每个设备映射到XOR映射中具有相同二进制数的插座.

这是一个例子:

Number of Devices [N] : 3
Number of bits in Electric charge [L] : 2
Power need by Device 1 [D1] : 01
Power need by Device 2 [D2]:11
Power need by Device 3 [D3]:10

Power available at Outlet 1 [T1] : 11
Power available at Outlet 2 [T2] : 00
Power available at Outlet 3 [T3] : 10

XOR MAP

      Devices  D1  D2  D3
Outlets
T1             10  00  01
T2             01  11  10
T3             11  01  00

现在在上面的地图中可以看出,01只有所有设备共享的二进制数用于不同的插座.所以这里的答案是1翻转为01,只有一个1 [1表示需要翻转的数量].如果共享多个二进制数,那么我们将选择具有最小二进制数的数字.

以下是此方法的java方法实现:

private final int totalParams = 2, N = 0, L = 1;

//Params contains value of N[devices] and L[charging bit]
//cn contains power needed by each device
//cs contains power available at outlet
//return value is the number of bits to be flipped. -1 indicates not possible
private int analyseChargeSetUp(int params[], BitSet[] cn, BitSet[] cs) {

        int retVal = -1;

        BitSet ms[] = new BitSet[params[this.N]];

        ArrayList<ArrayList<BitSet>> bxor = new ArrayList<ArrayList<BitSet>>();

        for (int i = 0; i < params[this.N]; i++) {
            BitSet temp = cn[i];

            // System.arraycopy(cs, 0, ms, 0, params[this.N]);

            for (int k = 0; k < params[this.N]; k++)
                ms[k] = (BitSet) cs[k].clone();

            // System.out.println("Size: " + bxor.size());
            bxor.add(i, new ArrayList<BitSet>());

            for (int j = 0; j < params[this.N]; j++) {
                ms[j].xor(temp);
                bxor.get(i).add(j, ms[j]);
            }
        }

        // HashSet<BitSet> evalSet = new HashSet<BitSet>();
        HashMap<BitSet, BitSet> bitMap = new HashMap<BitSet, BitSet>();

        for (ArrayList<BitSet> bl : bxor) {
            for (int j = 0; j < params[this.N]; j++) {
                BitSet temp1 = bl.get(j);
                // if (!evalSet.add(temp1)) {
                if (bitMap.get(temp1) == null) {
                    BitSet temp2 = new BitSet();
                    temp2.set(j);
                    bitMap.put(temp1, temp2);
                } else {
                    bitMap.get(temp1).set(j);
                }
                // }
            }
        }

        BitSet resultGetter = new BitSet(params[this.L]);
        resultGetter.set(0, params[this.L] + 1, true);
        Iterator<BitSet> itr = bitMap.keySet().iterator();
        BitSet temp3 = new BitSet();

        while (itr.hasNext()) {
            temp3 = itr.next();
            if (bitMap.get(temp3).cardinality() == params[this.N]) {
                if (temp3.cardinality() <= resultGetter.cardinality()) {
                    resultGetter = temp3;
                }
            }

        }

        // if (resultGetter.cardinality() == params[this.L])
        // retVal = 0;
        // else if (resultGetter.cardinality() == 0)
        // retVal = -1;
        // else
        if (resultGetter.cardinality() > params[this.L])
            retVal = -1;
        else
            retVal = resultGetter.cardinality();

        return retVal;

    }

Answer 2

好帖子和伟大的解决方案.我不知道Java中的BitSet类,谢谢!
对于实现,不严格需要存储所有XOR映射.实际上,可以逐步计算映射列之间的交集,以便找到所有可能的开关配置.
此外,考虑到l的最大值是40(并且考虑到直到十分钟前我才知道BitSets :)),可以使用long来存储插座和设备的配置.
因此,这是我的解决方案:

String solution(long[] o, long[] d) {

    HashSet<Long> xors = new HashSet<Long>();

    for (int j = 0; j < o.length; j++) {
        xors.add(o[0] ^ d[j]);
    }

    for (int i = 1; i < o.length; i++) {
        HashSet<Long> xors2 = new HashSet<Long>();
        for (int j = 0; j < o.length; j++) { 
            xors2.add(o[i] ^ d[j]);
        }
        for (Iterator<Long> it = xors.iterator(); it.hasNext();) {
            if (!xors2.contains(it.next())) {
                it.remove();
            }
        }
    }

    if (xors.isEmpty()) {
        return "NOT POSSIBLE";
    }

    Integer min = Integer.MAX_VALUE;
    for (long xor : xors) {
        min = Math.min(min, Long.bitCount(xor));
    }

    return min.toString();
}