1353E - K-periodic Garland - CodeForces Solution

brute force dp greedy *1900

Please click on ads to support us..

Python Code: 

for _ in range(int(input())):
    n, k = map(int, input().split())
    s = input()
    ans = []
    for i in range(k):
        c = t = 0
        for j in range(i, n, k):
            if s[j] == '1':
                c += 1
            else:
                c -= 1
            t = min(t, c)
            ans += c - t,
    print(s.count('1') - max(ans))

C++ Code: 

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;

        cin >> n >> k;

        string s;

        cin >> s;

        // int pre[n];
        vector<int> pre(n, 0);
        for (int i = 0; i < n; i++)
        {
            if (i == 0)
                pre[i] = s[i] - '0';
            else
                pre[i] += pre[i - 1] + (s[i] - '0');
        }

        vector<int> sum(n, 0);
        for (int i = n - 1; i >= 0; i--)
        {
            int xr = (s[i] - '0') ^ 1;
            if (i + k - 1 < n)
            {
                xr += pre[i + k - 1] - pre[i];
            }
            else
            {
                xr += pre[n - 1] - pre[i];
            }
            if (i + k < n)
            {
                xr += sum[i + k];
            }
            int r = pre[n - 1] - pre[i] + (s[i] - '0');
            sum[i] = min(r, xr);
        }
        int cnt = 1e15;
        for (int i = 0; i < n; i++)
        {
            int s = sum[i];
            if (i)
                s += pre[i - 1];

            cnt = min(cnt, s);
        }
        cout << cnt << endl;
    }
    // int i = 0, j = n - 1;
    // while (i < n && s[i] == '0')
    //     i++;
    // while (j >= 0 && s[j] == '0')
    //     j--;
    // if (j < i)
    // {
    //     cout << "0" << endl;
    //     continue;
    // }
    // int total = 0;
    // for (int l = i; l <= j; l++)
    // {
    //     if (s[l] == '1')
    //     {
    //         total++;
    //     }
    // }
    // vector<int> rem(k + 1, 0);
    // for (int l = i; l <= j; l++)
    // {
    //     if (s[l] == '1')
    //     {
    //         rem[(l - i) % (k)]++;
    //     }
    // }
    // int ans = 1e6;
    // cout << total << endl;
    // cout << (j - i + 1) / k << endl;

    // for (int l = 0; l < k; l++)
    // {
    //     cout << rem[l] << " ";
    //     ans = min(ans, (j - i + 1) / k - rem[l] + total - rem[l]);
    //     cout << ans << " ";
    // }
    // cout << ans << endl;
}


Comments

Submit
0 Comments
More Questions

e-maze-in
Bricks Game
Char Sum
Two Strings
Anagrams
Prime Number
Lexical Sorting Reloaded
1514A - Perfectly Imperfect Array
580A- Kefa and First Steps
1472B- Fair Division
996A - Hit the Lottery
MSNSADM1 Football
MATCHES Playing with Matches
HRDSEQ Hard Sequence
DRCHEF Doctor Chef
559. Maximum Depth of N-ary Tree
821. Shortest Distance to a Character
1441. Build an Array With Stack Operations
1356. Sort Integers by The Number of 1 Bits
922. Sort Array By Parity II
344. Reverse String
1047. Remove All Adjacent Duplicates In String
977. Squares of a Sorted Array
852. Peak Index in a Mountain Array
461. Hamming Distance
1748. Sum of Unique Elements
897. Increasing Order Search Tree
905. Sort Array By Parity
1351. Count Negative Numbers in a Sorted Matrix
617. Merge Two Binary Trees