SRM591 Div2 Med/ c++ ver

ConvertibleStrings.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class ConvertibleStrings {
public:
  int leastRemovals(string A, string B) {
    string AB = "ABCDEFGHI";

    set<char> s(AB.begin(), AB.end());
    vector<char> v(s.begin(), s.end());
        
    int minimum = 60;
    do{
      int c = count(v, A, B);
      minimum = min(minimum, c);

    }while(next_permutation(v.begin(), v.end()));

    return minimum;
  }

  int count(vector<char> v, string A, string B){
    int c = 0;
    for(unsigned i = 0; i < A.size(); ++i) {
      if (v[A[i] - 'A'] != B[i]){
        c++;
      }
    }
    return c;
  }
};


// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit-pfx 2.1.9
#include <iostream>
#include <string>
#include <vector>
#include <ctime>
#include <cmath>
using namespace std;
bool KawigiEdit_RunTest(int testNum, string p0, string p1, bool hasAnswer, int p2) {
	cout << "Test " << testNum << ": [" << "\"" << p0 << "\"" << "," << "\"" << p1 << "\"";
	cout << "]" << endl;
	ConvertibleStrings *obj;
	int answer;
	obj = new ConvertibleStrings();
	clock_t startTime = clock();
	answer = obj->leastRemovals(p0, p1);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p2 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p2;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	string p0;
	string p1;
	int p2;
	
	{
	// ----- test 0 -----
	p0 = "DD";
	p1 = "FF";
	p2 = 0;
	all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	p0 = "AAAA";
	p1 = "ABCD";
	p2 = 3;
	all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	p0 = "AAIAIA";
	p1 = "BCDBEE";
	p2 = 3;
	all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	p0 = "ABACDCECDCDAAABBFBEHBDFDDHHD";
	p1 = "GBGCDCECDCHAAIBBFHEBBDFHHHHE";
	p2 = 9;
	all_right = KawigiEdit_RunTest(3, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// Let X and Y be two strings of equal length, consisting of uppercase English letters only.
// The two strings are called convertible if there is a permutation P of the English alphabet with the following property:
// if each character c in the string X is replaced by the character P(c), we obtain the string Y.
// (In other words, X and Y are convertible iff the following holds: whenever two letters of X are equal, the corresponding two letters of Y must be equal, and vice versa.)
// 
// For example, consider the string "ABCA".
// We can choose to replace each 'A' by a 'F', each 'B' by a 'B', and each 'C' by a 'G', obtaining the string "FBGF".
// Thus the strings "ABCA" and "FBGF" are convertible.
// The strings "ABCA" and "EFGH" are not convertible, because the two 'A's in the first string must correspond to the same letter in the second string.
// The strings "ABCA" and "EEEE" are not convertible, because different letters in the first string must correspond to different letters in the second string.
// 
// You are given two strings A and B of the same length.
// These strings only contain English letters from 'A' to 'I', inclusive.
// (That is, only the first 9 letters of the alphabet are used.)
// 
// You want to change A and B into two strings that are convertible.
// The only allowed change is to choose some indices (possibly none) and to remove the characters at those indices from each of the strings.
// (I.e., the removed characters must be at the same positions in both strings. For example, it is not allowed to only remove character 0 of A and character 3 of B.)
// For example, if A="ABAC", B="AHHA" and the chosen indices are 0 and 2, then the resulting strings will be "BC" and "HA".
// Our goal is to choose as few indices as possible, given that after the erasing we want to obtain two convertible strings.
// Compute and return the smallest possible number of chosen indices.
// 
// 
// DEFINITION
// Class:ConvertibleStrings
// Method:leastRemovals
// Parameters:string, string
// Returns:int
// Method signature:int leastRemovals(string A, string B)
// 
// 
// CONSTRAINTS
// -A will contain between 1 and 50 characters, inclusive.
// -A and B will be of the same length.
// -A will contain characters from 'A' to 'I' only.
// -B will contain characters from 'A' to 'I' only.
// 
// 
// EXAMPLES
// 
// 0)
// "DD"
// "FF"
// 
// Returns: 0
// 
// The given strings are convertible without any removals. Any mapping with 'D' mapped to 'F' changes A to B.
// 
// 1)
// "AAAA"
// "ABCD"
// 
// Returns: 3
// 
// We can choose any three indices.
// 
// 2)
// "AAIAIA"
// "BCDBEE"
// 
// Returns: 3
// 
// One possible triple of indices is (1, 2, 5) (0-based indices).
// 
// 
// 3)
// "ABACDCECDCDAAABBFBEHBDFDDHHD"
// "GBGCDCECDCHAAIBBFHEBBDFHHHHE"
// 
// Returns: 9
// 
// 
// 
// END KAWIGIEDIT TESTING
//Powered by KawigiEdit-pfx 2.1.9!