SRM572Div1Easy.cpp

#include <vector>
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
#include <list>
#include <algorithm>
#include <sstream>
#include <set>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <numeric>

#define INF (1<<29)
#define EPS 1e-6

using namespace std;

class NewArenaPassword {

public:
    int
    diff(string a,string b)
    {
        int N = (int)a.size();
        int ans = 0;
        for (int i=0; i<N; ++i) {
            if (a[i] != b[i]) {
                ++ans;
            }
        }
        return ans;
    }

    int
    diff(string a,string b,int d)
    {
        int N = (int)a.size();
        int ans = 0;
        map<char, int> m;
        for (int i=0; i<d; ++i) {
            m.clear();
            m[a[i]]++;
            for (int j=i; j<N; j+=d) {
                m[b[j]]++;
            }
            int sum = 0;
            int mx = 0;
            for (map<char, int>::iterator it = m.begin(); it != m.end() ; ++it) {
                sum += (*it).second;
                mx = max(mx,(*it).second);
            }
            ans += sum - mx;
        }
        return ans;
    }

    int
    minChange(string oldPassword, int K)
    {
        int N = (int)oldPassword.size();
        if (2*K <= N) {
            string s = oldPassword.substr(0,K);
            string l = oldPassword.substr(N-K,K);
            return diff(s, l);
        }
        else {
            string s = oldPassword.substr(0,K);
            string l = oldPassword.substr(N-K,K);
            return diff(s,l,N-K);
        }
    }
};