algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.cpp (3513B)


      1 #include <iostream>
      2 #include <vector>
      3 #include <unordered_set>
      4 #include <unordered_map>
      5 #include <algorithm>
      6 #include <queue>
      7 
      8 #define ll long long
      9 
     10 using namespace std;
     11 
     12 // binary string s of length n
     13 // can do this any number of times (including zero):
     14     // choose an integer 1 <= i <= n and replace s_i with & or | of s_1, s_2, ..., s_i
     15 // find minimum number of operations to sort s in ascending order
     16 
     17 // 4
     18 // 0011
     19 // already sorted, 0
     20 
     21 // 4
     22 // 1000
     23 // 1
     24 // 1001
     25 // 1011
     26 // 1111
     27 // 3 ops
     28 
     29 // idea: for each zero that follows leading ones, they must be flipped one by one. 
     30     // is the question just how many zeroes follow the first one?
     31     // not quite. in cases where there's a one after some zeroes, that one can be flipped
     32     // is the answer then min(zeroesAfterFirstOne, onesAfterFirstZero)?
     33 
     34 // stepwise, do we just flip every one until the final sequence of zeroes?
     35 
     36 
     37 // 5
     38 // 01000
     39 // 00000
     40 
     41 
     42 // 8
     43 // 01001101
     44 // 00001101
     45 // 00000101
     46 // 00000001
     47 // sum = 3
     48 
     49 
     50 // 7
     51 // 0101010
     52 // 0001010
     53 // 0000010
     54 // 0000000
     55 
     56 
     57 // 7
     58 // 0111101
     59 // 0111111
     60 // steps: 1
     61 
     62 
     63 // feels like some sort of inequality exists here
     64 // is there something about the number of remaining zeroes and ones?
     65     // like how many ones are there? If there are more ones then zeroes, only flip zeroes as needed?
     66 
     67 // how many more ones are there after the current positions?
     68     // if there are more ones than zeroes, then we skip over the remaining runs of 
     69 // should we start from the end instead?
     70     // if we start from the end:
     71 
     72 // the question here is this:
     73     // where do we draw the boundary between ones and zeroes
     74     // this position is the spot where there are more 
     75     // can we compute this incrementally?
     76         // like we say what if we drew the line here and then everything on the left must be zeroes and right ones.
     77             // this seems to be on the right track, but we also want to remove all leading zeroes. 
     78         // leading ones can't be flipped so if first position is a one then we just count zeroes
     79 
     80 int countZeroes(string& st) {
     81     int res = 0;
     82     for(int i = 0; i < st.size(); ++i) {
     83         if(st[i] == '0') {
     84             res += 1;
     85         }
     86     }
     87     return res;
     88 }
     89 
     90 
     91 int stripLeadingZeroes(string& st) {
     92     int leadingZeroes = 0;
     93     for(int i = 0; i < st.size(); ++i) {
     94         if(st[i] == '1') {
     95             leadingZeroes = i;
     96             break;
     97         }
     98     }
     99     st = st.substr(leadingZeroes);
    100     return leadingZeroes;
    101 }
    102 
    103 int main() {
    104 
    105     int testCases, n;
    106     string st;
    107     cin >> testCases;
    108 
    109     for(int z = 0; z < testCases; ++z) {
    110 
    111         cin >> n;
    112         cin >> st;
    113 
    114         // we just count zeroes because everything must become one in such cases.
    115         if(st[0] == '1') {
    116             cout << countZeroes(st) << endl;
    117             continue;
    118         }
    119 
    120         int stripped = stripLeadingZeroes(st);
    121         
    122         int trailingZeroes = countZeroes(st);
    123         int leadingOnes = 0;
    124 
    125         int best = trailingZeroes;
    126 
    127         for(int i = 0; i < st.size(); ++i) {
    128             // what would happen if everyting before, and including the current, index had to be zeroes
    129             // and everything after had to be ones?
    130             if(st[i] == '1') {
    131                 leadingOnes += 1;
    132             } else {
    133                 trailingZeroes -= 1;
    134             }
    135             int currentCost = leadingOnes + trailingZeroes;
    136             if(currentCost < best || best == -1) {
    137                 best = currentCost;
    138             }
    139         }
    140 
    141         cout << best << endl;
    142         
    143     }
    144 }