Зарядка хаоса: замятие кода Google [2014]

Ответ 1

Трудная часть в этом вопросе состоит в том, что может быть несколько способов перевернуть, но нам нужно найти способ, который включает минимальные флипы.

Вот мой алгоритм для решения этой проблемы:

• Предположим, что есть N устройств, требующих биты D1...Dn для зарядки себя, а выходы питания доступны с выходами: M1...Mn bits

• Возьмите XOR мощности, требуемой устройством и мощностью, доступной на выходе, и вы получите представление о количестве бит, которые нужно перевернуть, чтобы соответствовать устройству с розеткой.

• Итак, как только мы создали карту устройств и точек 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 flip как 01, так как только один [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;

    }

Ответ 2

хорошая почта и отличное решение. Я не знал о классе BitSet на Java, спасибо!
Для реализации сохранение всей карты XOR строго не требуется. Фактически, можно постепенно вычислить пересечение столбцов карт, чтобы найти все возможные конфигурации коммутаторов.
Кроме того, учитывая, что максимальное значение для l было 40 (и учитывая, что я не знал о BitSets до десяти минут назад:)), можно использовать длинные точки для хранения конфигураций розеток и устройств.
Таким образом, это мое решение:

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

Ответ 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) Решение.

Ответ 4

static int flipRecursion(List<String> i, List<String> d, int bit, int flip) {
        int f = 100000;
        // recusion ending here
        if (bit > d.get(0).length()) {
            if (isMatch(i, d)){
                return flip;
            } else {
                return f;
            }
        }
//      if (flip == f){
//          return flip;
//      }
        //noflip
        f = flipRecursion(i, d, bit+1, flip);
        //flip
        List<String> in = new ArrayList<>(i);
        in = flipBit(bit, in);
        return Math.min(flipRecursion(in, d, bit+1, flip+1), f);
    }