充电混乱: Google Code Jam [2014]

Question

我将此作为以下问题的解决方案，与其他人分享。如果有比这更好的答案，请做帖子。

Problem Statement

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

由于这些设备有不同的规格，并且是由各种公司制造的，它们每一个都需要不同的电流来充电。同样，房子里的每个插座都输出一个特定的电流。An electric flow can be represented by a string of 0s and 1s of length L.

Shota希望能够同时为他的所有N台设备充电。巧合的是，他的新房子里正好有N家分店。为了配置来自插座的电流，有一个带有L开关的主控制面板。第一开关从房子的每个插座中翻转电流的第一位。例如，如果从插座流出的电流是：

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. 以设备所需功率的异或和插座上可用的电源为例，您可以了解要翻转的位数以匹配设备和电源插座。
3. 因此，一旦我们创建了设备和插座的异或映射，每个二进制数中的1s就表示需要翻转的数量。我们需要检查的是，是否可以将每个设备映射到具有相同二进制数字的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类，谢谢！

对于实现来说，存储所有的异或映射并不是严格需要的。实际上，可以逐步计算映射列之间的交集，以便找到所有可能的开关配置。

此外，考虑到l的最大值为40 (考虑到10分钟前我还不知道BitSets )，就可以使用longs来存储插座和设备的配置。

因此，这是我的解决办法：

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();
}

Answer 3

#include <iostream>
using namespace std;
#include<algorithm>
#include<stdio.h>
int main() {
long long int t,i,n,l,j,k,cur,m=0,count,max,q,w;
    char a[159][50],b[159][50];
    long long int d[159],e[159],f[159],flag,g;
cin>>t;
while(t--)
{
    cin>>n>>l;max=100;
    flag=0;
    m++;
    for(i=0;i<n;i++)``
    cin>>a[i];
    for(i=0;i<n;i++)
    cin>>b[i];
    for(i=0;i<n;i++)
    {
        d[i]=e[i]=0;long long int h=1;
        for(j=l-1;j>=0;j--)
        {
        if(a[i][j]=='0')
        q=0;
        else 
        q=1;
        if(b[i][j]=='0')
        w=0;
        else 
        w=1;

        d[i]+=q*h;
        e[i]+=w*h;
        h*=2;
        }
    }
    cur=0;
    sort(d,d+n);
    sort(e,e+n);
    for(i=0;i<n;i++)
    {
        flag=1;count=0;
        g=d[0]^e[i];

        for(k=0;k<n;k++)
        f[k]=d[k]^g;
        sort(f,f+n);
        for(k=0;k<n;k++)
        if(f[k]!=e[k])
        {
            flag=0;
            break;
        }

        for(k=0;k<l;k++)
        {
        if(g%2==1)
        count++;
        g=g/2;
        }
        if(flag==1)
        {
            if(max>count)
            max=count;
            cur=1;
        }

    }
    if(cur)
    printf("Case #%lld: %lld\n",m,max);
    else
    printf("Case #%lld: NOT POSSIBLE\n",m);
}
// your code goes here
return 0;
}

O(n^2 log(n)+ n*l)解。