Competitive-Programming/k_complete.cpp at master · Code-Cube-NITP/Competitive-Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*


*/

#include<bits/stdc++.h>
#definefastioios_base::sync_with_stdio(false); cin.tie(NULL)
#defineendl'\n'
#defineintlonglongint
usingnamespacestd;
#definepii pair <int, int>
#definepb push_back
#definedeb(x) cout << #x << "" << x << endl
#definedeb2(x, y) cout << #x << "" << x << "" << #y << "" << y << endl
#defineLoop(s, e, itr) for (int itr = s; itr < e; itr++)
#defineloop(n) for(int i = 0; i < n; i++)
#definevin vector<int>
#definew(t) int tc; cin >> tc; for(int t = 1; t <= tc; t++)
#definevec vector

int32_tmain(){
 fastio;
int n, k;
 string str;
 vec<vec<char>> table;
w(t){
 cin >> n >> k;
 cin >> str;
 table = vec<vec<char>>(k/2, vec<char>(2*(n/k)));
for(int i = 0; i < k/2; i++){
for(int j = 0; j < n/k; j++){
 table[i].pb(str[k*j+i]);
 table[i].pb(str[k*j+k-1-i]);
 }
 }
// for(auto i : table){
// for(auto j : i) cout << j << " ";
// cout << endl;
// cout << i.size() << endl;
// }

int ans = 0;
for(auto i : table){
int count[26] = {0};
for(auto j : i){
 count[j-'a']++;
 }
int max = 0;
Loop(0, 26, p) if(count[p] > max) max = count[p];
 ans += 2*(n/k) - max;
// deb(ans);
 }
if(k%2){
int count[26] = {0};
// deb(k/2);
for(int i = 0; i < n/k; i++){
// deb(i);
 count[str[i*k + (k/2)]-'a']++;
// deb(str[i*k + (k/2)]);
 }
int max = 0;

Loop(0, 26, z) if(count[z] > max) max = count[z];
// deb(max);
 ans += (n/k - max);
 }
 cout << ans << endl;
 }
}