ADDED   SRM/572-U/1A.cpp
Index: SRM/572-U/1A.cpp
==================================================================
--- SRM/572-U/1A.cpp
+++ SRM/572-U/1A.cpp
@@ -0,0 +1,127 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+using namespace std;
+typedef long long LL;
+typedef long double LD;
+typedef complex<LD> CMP;
+
+struct UnionFind
+{
+	vector<int> uf, sz;
+	int nc;
+
+	UnionFind(int N): uf(N), sz(N,1), nc(N)
+		{ for(int i=0; i<N; ++i) uf[i] = i; }
+	int size()
+		{ return nc; }
+	int size(int a)
+		{ return sz[Find(a)]; }
+	int Find(int a)
+		{ return uf[a]==a ? a : uf[a]=Find(uf[a]); }
+	bool Union(int a, int b)
+		{
+			a = Find(a);
+			b = Find(b);
+			if( a != b )
+			{
+				if( sz[a] >= sz[b] ) swap(a, b);
+				uf[a] = b;
+				sz[b] += sz[a];
+				--nc;
+			}
+			return (a!=b);
+		}
+};
+
+class NewArenaPassword { public:
+	int minChange(string oldPassword, int K)
+	{
+		int N = oldPassword.size();
+		UnionFind uf(N);
+		for(int i=0; i<K; ++i)
+			uf.Union(i, N-K+i);
+
+		int total = 0;
+		for(int r=0; r<N; ++r) if(uf.Find(r) == r) {
+			map<char,int> freq;
+			for(int i=0; i<N; ++i)
+				if(uf.Find(i) == r)
+					freq[oldPassword[i]]++;
+			vector<int> fff;
+			for(map<char,int>::iterator it=freq.begin(); it!=freq.end(); ++it)
+				fff.push_back(it->second);
+			total += accumulate(fff.begin(), fff.end(), -*max_element(fff.begin(), fff.end()));
+		}
+		return total;
+	}
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const int& Expected, const int& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END	 verify_case(_, NewArenaPassword().minChange(oldPassword, K));}
+int main(){
+
+CASE(0)
+	string oldPassword = "topcoderopen"; 
+	int K = 5; 
+	int _ = 3; 
+END
+CASE(1)
+	string oldPassword = "puyopuyo"; 
+	int K = 4; 
+	int _ = 0; 
+END
+CASE(2)
+	string oldPassword = "loool"; 
+	int K = 3; 
+	int _ = 1; 
+END
+CASE(3)
+	string oldPassword = "arena"; 
+	int K = 5; 
+	int _ = 0; 
+END
+CASE(4)
+	string oldPassword = "amavckdkz"; 
+	int K = 7; 
+	int _ = 5; 
+END
+/*
+CASE(5)
+	string oldPassword = ; 
+	int K = ; 
+	int _ = ; 
+END
+CASE(6)
+	string oldPassword = ; 
+	int K = ; 
+	int _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/572-U/1B.cpp
Index: SRM/572-U/1B.cpp
==================================================================
--- SRM/572-U/1B.cpp
+++ SRM/572-U/1B.cpp
@@ -0,0 +1,167 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+using namespace std;
+typedef long long LL;
+typedef long double LD;
+typedef complex<LD> CMP;
+
+class EllysBulls { public:
+	string getNumber(vector <string> guesses, vector <int> bulls)
+	{
+		vector<int> pTen(1,1);
+		for(int i=0; i<10; ++i)
+			pTen.push_back(pTen.back()*10);
+
+		int Q = guesses.size();
+		int N = guesses[0].size();
+		int B = min(N, 4);
+		int F = N - B;
+		map<string, vector<int> > back;
+		for(int b=0; b<pTen[B]; ++b)
+		{
+			string sig;
+			for(int i=0; i<Q; ++i)
+			{
+				int s = bulls[i];
+				for(int k=0; k<B; ++k)
+					if( (guesses[i][N-1-k]-'0') == b/pTen[k]%10 )
+						--s;
+				if(s>=0)
+					sig += char('0'+s);
+				else
+					goto next;
+			}
+			back[sig].push_back(b);
+		next:;
+		}
+
+		string cand = "";
+		for(int f=0; f<pTen[F]; ++f)
+		{
+			string sig;
+			map<string, vector<int> >::iterator it;
+			for(int i=0; i<Q; ++i)
+			{
+				int s = 0;
+				for(int k=0; k<F; ++k)
+					if( (guesses[i][F-1-k]-'0') == f/pTen[k]%10 )
+						++s;
+				if(s<=bulls[i])
+					sig += char('0'+s);
+				else
+					goto next2;
+			}
+			it = back.find(sig);
+			if( it != back.end() ) {
+				for(int j=0; j<it->second.size(); ++j) {
+					if(!cand.empty())
+						return "Ambiguity";
+					for(int k=0; k<F; ++k)
+						cand += char('0'+f/pTen[F-1-k]%10);
+					for(int k=0; k<B; ++k)
+						cand += char('0'+it->second[j]/pTen[B-1-k]%10);
+				}
+			}
+		next2:;
+		}
+
+		if(cand.empty())
+			return "Liar";
+		return cand;
+	}
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const string& Expected, const string& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END	 verify_case(_, EllysBulls().getNumber(guesses, bulls));}
+int main(){
+
+CASE(0)
+	string guesses_[] = {"1234", "4321", "1111", "2222", "3333", "4444", "5555", "6666", "7777", "8888", "9999"};
+	  vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 
+	int bulls_[] = {2, 1, 1, 0, 2, 0, 0, 0, 1, 0, 0};
+	  vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); 
+	string _ = "1337"; 
+END
+CASE(1)
+	string guesses_[] = {"0000", "1111", "2222"};
+	  vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 
+	int bulls_[] = {2, 2, 2};
+	  vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); 
+	string _ = "Liar"; 
+END
+CASE(2)
+	string guesses_[] = {"666666", "666677", "777777", "999999"};
+	  vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 
+	int bulls_[] = {2, 3, 1, 0};
+	  vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); 
+	string _ = "Ambiguity"; 
+END
+CASE(3)
+	string guesses_[] = {"000", "987", "654", "321", "100", "010"};
+	  vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 
+	int bulls_[] = {2, 1, 0, 0, 1, 1};
+	  vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); 
+	string _ = "007"; 
+END
+CASE(4)
+	string guesses_[] = {"28", "92", "70", "30", "67", "63", "06", "65",
+ "11", "06", "88", "48", "09", "65", "48", "08"};
+	  vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 
+	int bulls_[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
+	  vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); 
+	string _ = "54"; 
+END
+CASE(5)
+	string guesses_[] = {"0294884", "1711527", "2362216", "7666148", "7295642",
+ "4166623", "1166638", "2767693", "8650248", "2486509",
+ "6138934", "4018642", "6236742", "2961643", "8407361",
+ "2097376", "6575410", "6071777", "3569948", "2606380"};
+	  vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 
+	int bulls_[] = {1, 0, 1, 3, 4, 4, 3, 2, 1, 1, 0, 4, 4, 3, 0, 0, 0, 0, 2, 1};
+	  vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); 
+	string _ = "4266642"; 
+END
+/*
+CASE(6)
+	string guesses_[] = ;
+	  vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 
+	int bulls_[] = ;
+	  vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); 
+	string _ = ; 
+END
+CASE(7)
+	string guesses_[] = ;
+	  vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_)); 
+	int bulls_[] = ;
+	  vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); 
+	string _ = ; 
+END
+*/
+}
+// END CUT HERE