8ca6d3c288 2013-12-15 kinaba: #include <iostream> 8ca6d3c288 2013-12-15 kinaba: #include <sstream> 8ca6d3c288 2013-12-15 kinaba: #include <iomanip> 8ca6d3c288 2013-12-15 kinaba: #include <vector> 8ca6d3c288 2013-12-15 kinaba: #include <string> 8ca6d3c288 2013-12-15 kinaba: #include <map> 8ca6d3c288 2013-12-15 kinaba: #include <set> 8ca6d3c288 2013-12-15 kinaba: #include <algorithm> 8ca6d3c288 2013-12-15 kinaba: #include <numeric> 8ca6d3c288 2013-12-15 kinaba: #include <iterator> 8ca6d3c288 2013-12-15 kinaba: #include <functional> 8ca6d3c288 2013-12-15 kinaba: #include <complex> 8ca6d3c288 2013-12-15 kinaba: #include <queue> 8ca6d3c288 2013-12-15 kinaba: #include <stack> 8ca6d3c288 2013-12-15 kinaba: #include <cmath> 8ca6d3c288 2013-12-15 kinaba: #include <cassert> 8ca6d3c288 2013-12-15 kinaba: #include <tuple> 8ca6d3c288 2013-12-15 kinaba: using namespace std; 8ca6d3c288 2013-12-15 kinaba: typedef long long LL; 8ca6d3c288 2013-12-15 kinaba: typedef complex<double> CMP; 8ca6d3c288 2013-12-15 kinaba: 8ca6d3c288 2013-12-15 kinaba: class PalindromeMatrix { public: 8ca6d3c288 2013-12-15 kinaba: int minChange(vector <string> A, int rowCount, int columnCount) 8ca6d3c288 2013-12-15 kinaba: { 8ca6d3c288 2013-12-15 kinaba: const int H = A.size(), W = A[0].size(); 8ca6d3c288 2013-12-15 kinaba: vector<vector<int>> cpp, rpp; 8ca6d3c288 2013-12-15 kinaba: { 8ca6d3c288 2013-12-15 kinaba: vector<int> cp(W-columnCount, 0); cp.resize(W, 1); 8ca6d3c288 2013-12-15 kinaba: do cpp.push_back(cp); while(next_permutation(cp.begin(), cp.end())); 8ca6d3c288 2013-12-15 kinaba: vector<int> rp(H-rowCount, 0); rp.resize(H, 1); 8ca6d3c288 2013-12-15 kinaba: do rpp.push_back(rp); while(next_permutation(rp.begin(), rp.end())); 8ca6d3c288 2013-12-15 kinaba: } 8ca6d3c288 2013-12-15 kinaba: 8ca6d3c288 2013-12-15 kinaba: int best = 99999999; 8ca6d3c288 2013-12-15 kinaba: for(auto& cp: cpp) 8ca6d3c288 2013-12-15 kinaba: { 8ca6d3c288 2013-12-15 kinaba: int c_score = 0; 8ca6d3c288 2013-12-15 kinaba: for(int x=0; x<W; ++x) if(cp[x]) 8ca6d3c288 2013-12-15 kinaba: for(int y=0; y<H-1-y; ++y) 8ca6d3c288 2013-12-15 kinaba: c_score += maj(A[y][x], A[H-1-y][x]); 8ca6d3c288 2013-12-15 kinaba: 8ca6d3c288 2013-12-15 kinaba: vector<int> r_score_0(H), r_score_3(H), r_score_4(H); 8ca6d3c288 2013-12-15 kinaba: for(int y=0; y<H; ++y) 8ca6d3c288 2013-12-15 kinaba: for(int x=0; x<W-1-x; ++x) 8ca6d3c288 2013-12-15 kinaba: if(!cp[x] && !cp[W-1-x]) { 8ca6d3c288 2013-12-15 kinaba: r_score_0[y] += maj(A[y][x], A[y][W-1-x]); 8ca6d3c288 2013-12-15 kinaba: r_score_3[y] += maj(A[y][x], A[y][W-1-x]); 8ca6d3c288 2013-12-15 kinaba: r_score_4[y] += maj(A[y][x], A[y][W-1-x]); 8ca6d3c288 2013-12-15 kinaba: } else { 8ca6d3c288 2013-12-15 kinaba: if(cp[x] && cp[W-1-x]) 8ca6d3c288 2013-12-15 kinaba: r_score_3[y] += maj(A[y][x],A[H-1-y][x],A[y][W-1-x],A[H-1-y][W-1-x]) 8ca6d3c288 2013-12-15 kinaba: - maj(A[y][x],A[H-1-y][x]) - maj(A[y][W-1-x],A[H-1-y][W-1-x]); 8ca6d3c288 2013-12-15 kinaba: else if(cp[x]) 8ca6d3c288 2013-12-15 kinaba: r_score_3[y] += maj(A[y][x],A[H-1-y][x],A[y][W-1-x]) - maj(A[y][x],A[H-1-y][x]); 8ca6d3c288 2013-12-15 kinaba: else 8ca6d3c288 2013-12-15 kinaba: r_score_3[y] += maj(A[y][x],A[H-1-y][W-1-x],A[y][W-1-x]) - maj(A[y][W-1-x],A[H-1-y][W-1-x]); 8ca6d3c288 2013-12-15 kinaba: r_score_4[y] += maj(A[y][x],A[H-1-y][x],A[y][W-1-x],A[H-1-y][W-1-x]) 8ca6d3c288 2013-12-15 kinaba: - (cp[x] ? maj(A[y][x],A[H-1-y][x]) : 0) - (cp[W-1-x] ? maj(A[y][W-1-x],A[H-1-y][W-1-x]) : 0); 8ca6d3c288 2013-12-15 kinaba: } 8ca6d3c288 2013-12-15 kinaba: 8ca6d3c288 2013-12-15 kinaba: for(auto& rp: rpp) { 8ca6d3c288 2013-12-15 kinaba: int score = c_score; 8ca6d3c288 2013-12-15 kinaba: for(int y=0; y<H; ++y) if(rp[y]) { 8ca6d3c288 2013-12-15 kinaba: if(!rp[H-1-y]) score += r_score_3[y]; 8ca6d3c288 2013-12-15 kinaba: else score += (y<H-1-y ? r_score_4 : r_score_0)[y]; 8ca6d3c288 2013-12-15 kinaba: } 8ca6d3c288 2013-12-15 kinaba: best = min(best, score); 8ca6d3c288 2013-12-15 kinaba: } 8ca6d3c288 2013-12-15 kinaba: } 8ca6d3c288 2013-12-15 kinaba: return best; 8ca6d3c288 2013-12-15 kinaba: } 8ca6d3c288 2013-12-15 kinaba: 8ca6d3c288 2013-12-15 kinaba: static int maj(char a, char b, char c, char d) { 8ca6d3c288 2013-12-15 kinaba: int cnt = (a=='0')+(b=='0')+(c=='0')+(d=='0'); 8ca6d3c288 2013-12-15 kinaba: return cnt<2?cnt:4-cnt; 8ca6d3c288 2013-12-15 kinaba: } 8ca6d3c288 2013-12-15 kinaba: static int maj(char a, char b, char c) { 8ca6d3c288 2013-12-15 kinaba: int cnt = (a=='0')+(b=='0')+(c=='0'); 8ca6d3c288 2013-12-15 kinaba: return cnt<2?cnt:3-cnt; 8ca6d3c288 2013-12-15 kinaba: } 8ca6d3c288 2013-12-15 kinaba: static int maj(char a, char b) { 8ca6d3c288 2013-12-15 kinaba: return a!=b; 8ca6d3c288 2013-12-15 kinaba: } 8ca6d3c288 2013-12-15 kinaba: }; 8ca6d3c288 2013-12-15 kinaba: 8ca6d3c288 2013-12-15 kinaba: // BEGIN CUT HERE 8ca6d3c288 2013-12-15 kinaba: #include <ctime> 8ca6d3c288 2013-12-15 kinaba: double start_time; string timer() 8ca6d3c288 2013-12-15 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 8ca6d3c288 2013-12-15 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 8ca6d3c288 2013-12-15 kinaba: { os << "{ "; 8ca6d3c288 2013-12-15 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 8ca6d3c288 2013-12-15 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 8ca6d3c288 2013-12-15 kinaba: void verify_case(const int& Expected, const int& Received) { 8ca6d3c288 2013-12-15 kinaba: bool ok = (Expected == Received); 8ca6d3c288 2013-12-15 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 8ca6d3c288 2013-12-15 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 8ca6d3c288 2013-12-15 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 8ca6d3c288 2013-12-15 kinaba: #define END verify_case(_, PalindromeMatrix().minChange(A, rowCount, columnCount));} 8ca6d3c288 2013-12-15 kinaba: int main(){ 8ca6d3c288 2013-12-15 kinaba: 8ca6d3c288 2013-12-15 kinaba: CASE(0) 8ca6d3c288 2013-12-15 kinaba: string A_[] = {"0000" 8ca6d3c288 2013-12-15 kinaba: ,"1000" 8ca6d3c288 2013-12-15 kinaba: ,"1100" 8ca6d3c288 2013-12-15 kinaba: ,"1110"}; 8ca6d3c288 2013-12-15 kinaba: vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); 8ca6d3c288 2013-12-15 kinaba: int rowCount = 2; 8ca6d3c288 2013-12-15 kinaba: int columnCount = 2; 8ca6d3c288 2013-12-15 kinaba: int _ = 1; 8ca6d3c288 2013-12-15 kinaba: END 8ca6d3c288 2013-12-15 kinaba: CASE(1) 8ca6d3c288 2013-12-15 kinaba: string A_[] = {"0000" 8ca6d3c288 2013-12-15 kinaba: ,"1000" 8ca6d3c288 2013-12-15 kinaba: ,"1100" 8ca6d3c288 2013-12-15 kinaba: ,"1110"}; 8ca6d3c288 2013-12-15 kinaba: vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); 8ca6d3c288 2013-12-15 kinaba: int rowCount = 3; 8ca6d3c288 2013-12-15 kinaba: int columnCount = 2; 8ca6d3c288 2013-12-15 kinaba: int _ = 3; 8ca6d3c288 2013-12-15 kinaba: END 8ca6d3c288 2013-12-15 kinaba: CASE(2) 8ca6d3c288 2013-12-15 kinaba: string A_[] = {"01" 8ca6d3c288 2013-12-15 kinaba: ,"10"}; 8ca6d3c288 2013-12-15 kinaba: vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); 8ca6d3c288 2013-12-15 kinaba: int rowCount = 1; 8ca6d3c288 2013-12-15 kinaba: int columnCount = 1; 8ca6d3c288 2013-12-15 kinaba: int _ = 1; 8ca6d3c288 2013-12-15 kinaba: END 8ca6d3c288 2013-12-15 kinaba: CASE(3) 8ca6d3c288 2013-12-15 kinaba: string A_[] = {"1110" 8ca6d3c288 2013-12-15 kinaba: ,"0001"}; 8ca6d3c288 2013-12-15 kinaba: vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); 8ca6d3c288 2013-12-15 kinaba: int rowCount = 0; 8ca6d3c288 2013-12-15 kinaba: int columnCount = 0; 8ca6d3c288 2013-12-15 kinaba: int _ = 0; 8ca6d3c288 2013-12-15 kinaba: END 8ca6d3c288 2013-12-15 kinaba: CASE(4) 8ca6d3c288 2013-12-15 kinaba: string A_[] = {"01010101" 8ca6d3c288 2013-12-15 kinaba: ,"01010101" 8ca6d3c288 2013-12-15 kinaba: ,"01010101" 8ca6d3c288 2013-12-15 kinaba: ,"01010101" 8ca6d3c288 2013-12-15 kinaba: ,"01010101" 8ca6d3c288 2013-12-15 kinaba: ,"01010101" 8ca6d3c288 2013-12-15 kinaba: ,"01010101" 8ca6d3c288 2013-12-15 kinaba: ,"01010101"}; 8ca6d3c288 2013-12-15 kinaba: vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); 8ca6d3c288 2013-12-15 kinaba: int rowCount = 2; 8ca6d3c288 2013-12-15 kinaba: int columnCount = 3; 8ca6d3c288 2013-12-15 kinaba: int _ = 8; 8ca6d3c288 2013-12-15 kinaba: END 8ca6d3c288 2013-12-15 kinaba: CASE(5) 8ca6d3c288 2013-12-15 kinaba: string A_[] = {"000000000000" 8ca6d3c288 2013-12-15 kinaba: ,"011101110111" 8ca6d3c288 2013-12-15 kinaba: ,"010001010101" 8ca6d3c288 2013-12-15 kinaba: ,"010001010101" 8ca6d3c288 2013-12-15 kinaba: ,"011101010101" 8ca6d3c288 2013-12-15 kinaba: ,"010101010101" 8ca6d3c288 2013-12-15 kinaba: ,"010101010101" 8ca6d3c288 2013-12-15 kinaba: ,"011101110111" 8ca6d3c288 2013-12-15 kinaba: ,"000000000000" 8ca6d3c288 2013-12-15 kinaba: ,"000000000000"}; 8ca6d3c288 2013-12-15 kinaba: vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); 8ca6d3c288 2013-12-15 kinaba: int rowCount = 5; 8ca6d3c288 2013-12-15 kinaba: int columnCount = 9; 8ca6d3c288 2013-12-15 kinaba: int _ = 14; 8ca6d3c288 2013-12-15 kinaba: END 8ca6d3c288 2013-12-15 kinaba: CASE(6) 8ca6d3c288 2013-12-15 kinaba: string A_[] = {"11111101001110" 8ca6d3c288 2013-12-15 kinaba: ,"11000111111111" 8ca6d3c288 2013-12-15 kinaba: ,"00010101111001" 8ca6d3c288 2013-12-15 kinaba: ,"10110000111111" 8ca6d3c288 2013-12-15 kinaba: ,"10000011010010" 8ca6d3c288 2013-12-15 kinaba: ,"10001101101101" 8ca6d3c288 2013-12-15 kinaba: ,"00101010000001" 8ca6d3c288 2013-12-15 kinaba: ,"10111010100100" 8ca6d3c288 2013-12-15 kinaba: ,"11010011110111" 8ca6d3c288 2013-12-15 kinaba: ,"11100010110110" 8ca6d3c288 2013-12-15 kinaba: ,"00100101010100" 8ca6d3c288 2013-12-15 kinaba: ,"01001011001000" 8ca6d3c288 2013-12-15 kinaba: ,"01010001111010" 8ca6d3c288 2013-12-15 kinaba: ,"10100000010011"}; 8ca6d3c288 2013-12-15 kinaba: vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); 8ca6d3c288 2013-12-15 kinaba: int rowCount = 6; 8ca6d3c288 2013-12-15 kinaba: int columnCount = 8; 8ca6d3c288 2013-12-15 kinaba: int _ = 31; 8ca6d3c288 2013-12-15 kinaba: END 8ca6d3c288 2013-12-15 kinaba: /* 8ca6d3c288 2013-12-15 kinaba: CASE(7) 8ca6d3c288 2013-12-15 kinaba: string A_[] = ; 8ca6d3c288 2013-12-15 kinaba: vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); 8ca6d3c288 2013-12-15 kinaba: int rowCount = ; 8ca6d3c288 2013-12-15 kinaba: int columnCount = ; 8ca6d3c288 2013-12-15 kinaba: int _ = ; 8ca6d3c288 2013-12-15 kinaba: END 8ca6d3c288 2013-12-15 kinaba: CASE(8) 8ca6d3c288 2013-12-15 kinaba: string A_[] = ; 8ca6d3c288 2013-12-15 kinaba: vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); 8ca6d3c288 2013-12-15 kinaba: int rowCount = ; 8ca6d3c288 2013-12-15 kinaba: int columnCount = ; 8ca6d3c288 2013-12-15 kinaba: int _ = ; 8ca6d3c288 2013-12-15 kinaba: END 8ca6d3c288 2013-12-15 kinaba: */ 8ca6d3c288 2013-12-15 kinaba: } 8ca6d3c288 2013-12-15 kinaba: // END CUT HERE