ICCT20WC - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Div-2 Contest

Author: Dharanendra L V
Tester: Dharanendra L V
Editorialist: Dharanendra L V

DIFFICULTY:

Easy

PREREQUISITES:

None.

PROBLEM:

Given two integers N, K and a binary string S, for each character having 0 at index i, find the nearest index j having character 1 and find the sum |i - j| + k for all the valid i.

EXPLANATION:

For each i, find the nearest 1 to its left or if not found then assign the value INT_MAX, let’s denote it as L(i) and find the nearest 1 to its right, let’s denote it as R(i) or if not found then assign the value INT_MAX. Let’s denote the final answer as ans then find the minimum of L(i) and R(i) and add it to ans and add K for every i. And at last print the value of ans. Which can be done in O(N) i.e. Linear pass.

SOLUTIONS:

Setter's Solution 
#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;
        
        vector<int> Left(n), Right(n);
        int cnt = 0;
        bool hasOne = false;
        for (int i = 0; i < n; ++i)
        {
            if (s[i]=='1')
            {
                hasOne = true;
                cnt = 0;
                Left[i] = 0;
            }
            else if (hasOne)
            {
                cnt++;
                Left[i] = cnt;
            }
            else
                Left[i] = INT_MAX;
        
        }
        
        hasOne = false;
        for (int i = n-1; i >= 0; --i)
        {
            if (s[i]=='1')
            {
                hasOne = true;
                cnt = 0;
                Right[i] = 0;
            }
            else if (hasOne)
            {
                cnt++;
                Right[i] = cnt;
            }
            else
                Right[i] = INT_MAX;
        }
        
        int sum = 0;
        for (int i = 0; i < n; ++i)
        {
            if (s[i] != '1')
            {
                sum += min(Left[i], Right[i]);
            } 
            sum += k;
        }
        
        cout << sum << endl;
    }
    
    return 0;
}

Feel free to share your approach here. Suggestions are always welcomed. :slight_smile:

1 Like