qih8b's blog

By qih8b, 3 months ago, In English

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;
}

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it