light42's blog

By light42, 9 years ago, In English

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;
}
  • Vote: I like it
  • -3
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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).