### qih8b's blog

By qih8b, 3 months ago,

I can't understand why my solution for this problem is not work K-periodic Garland https://codeforces.com/problemset/problem/1353/E The official solution uses DP. I want to implement without DP. The solution is to minimize the number of moves. vr is the vector of lamps at positions %k. In the official solution vr is t_i. The minimum number of moves to make vr K-periodic and turn off all other lamps.

int main() {
int T, total;
int moves;
int n, k;
int diff = 0;
cin >> T;
vector<int> solutions;
while (T--) {
total = 0;
cin >> n >> k;
string _s;
cin >> _s;
vector<bool> s(_s.size());
for (int i = 0; i < _s.size(); ++i) {
s[i] = _s[i] - '0';
total += s[i];
}
int best = 10000000;
int best_overall = 1000000;
for (int rem = 0; rem < k; rem++) {
vector<bool> vr;
for (int lamp = 0; lamp < n; lamp += k) {
vr.push_back(s[lamp]);
}
vector<int> ps0(vr.size()+1), ps1(vr.size()+1);
for (int i = 0; i < vr.size(); i++) {
ps0[i + 1] = ps0[i] + (vr[i] == 0);
ps1[i + 1] = ps1[i] + (vr[i] == 1);
}
diff = 0;
for (int right = 0; right < vr.size(); right++) {
moves = ps0[right] + total - ps1[right] + diff;
best = min(best, moves);
diff = min(diff, ps1[right] - ps0[right]);
}
best_overall = min(best, best_overall);
cout << "best: " << best << endl;
}
solutions.push_back(best_overall);
}
for (auto &x : solutions)
cout << x << endl;
return 0;
}