充電混沌：谷歌代碼果醬[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個出口。爲了配置來自插座的電流，有一個帶L開關的主控制面板。第i個開關翻轉房屋內每個出口的電流的第i位。例如，如果從出口的電流是：

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

然後翻轉所述第二開關將重新配置電流：

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

如果將太具有需要流動「11」到智能電話充電，需要流量「10」充電的平板電腦和需要流量「00」充電的筆記本電腦，然後翻轉第二個開關將使他非常高興！

Misaki被Shota僱傭來幫助他解決這個問題。她測量了房子網點的電流，發現它們都不一樣。決定Shota是否有可能同時爲他的所有設備充電，如果可能的話，找出需要翻轉的開關的最小數量，因爲這些開關很大很重，Misaki不想要翻轉更多比她需要的東西。

Answer 1

這個問題棘手的部分是，可以有多種方式來翻轉，但我們需要找到涉及最小翻轉的方式。

這裏是我的算法來解決這個問題：

1. 比方說有N個設備需要D1...Dn位到自身充電和電源插座可與輸出：M1...Mn位

2. 採取的XOR設備所需的電力和電源插座上可用的電源可讓您瞭解要翻轉的位數，以便將設備與電源插座相匹配。

3. 因此，一旦我們創建了設備和插座的XOR映射，每個二進制數的1的numbr指示需要的翻轉次數。我們需要檢查的是，是否可以將每個設備映射到異或映射中具有相同二進制數的插座。

下面是一個例子：

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

#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 *升）溶液。

Answer 3

不錯的文章和很好的解決方案。我不知道Java中的BitSet類，謝謝！
對於存儲所有XOR映射的實現並非嚴格需要。事實上，可以逐步計算地圖列之間的交集，以便找到所有可能的開關配置。
此外，考慮到l的最大值是40（並且考慮到我直到10分鐘前才知道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(); 
} 

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