Link to problem here
My method for solve this problem is to generate N^2 possible switch combination and from that combination we'll simply check if there's optimum solution. I pick this method because it's the most understandable way in the analysis and some coders use it and get acc. But my code still slow though (didn't pass 8 minute limit). I try to optimize the code but still too slow :(. Is there any way to optimize my code more?
PS: Sorry if this post is bad. This is the first time I'm posting codes(and sorry if my english is bad).
#include <cstdio>
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
using namespace std;
#define LOOP(i,n) for(int i = 0; i < n; i++)
int T,N,Leng;
string outlet[200];
string devices[200];
int main()
{
cin >> T;
LOOP(i,T)
{
set<pair<string,int> > flipSwitch;
set<string> dv;
string dummy;
int best = INT_MAX;
cin >> N >> Leng;
LOOP(j,N)
{
cin >> outlet[j];
}
LOOP(j,N)
{
cin >> devices[j];
dv.insert(devices[j]);
}
LOOP(j,N)
{
LOOP(k,N)
{
string curr = "";
int change = 0;
LOOP(l,Leng)
{
if(outlet[j][l] == devices[k][l])curr += '0';
else{curr += '1';change++;}
}
flipSwitch.insert(make_pair(curr, change));
}
}
for(set<pair<string,int> >::iterator it = flipSwitch.begin(); it != flipSwitch.end(); it++)
{
string flipIt = (*it).first;
set<string> ot;
LOOP(j,N)
{
string x = "";
LOOP(k,Leng)
{
if(flipIt[k] == '0') x += outlet[j][k];
else
{
if(outlet[j][k] == '1')x += '0';
else x += '1';
}
}
ot.insert(x);
}
if(ot == dv)best = min(best,(*it).second);
}
printf("Case #%d: ",i+1);
if(best == INT_MAX)printf("Not Possible\n");
else printf("%d\n",best);
}
return 0;
}
For a quick win you can use long long (or uint64_t) instead of strings to represent the electric flows (and use the ^ operator to flip bits).