Solution of Problem C — Educational Round 171

Revision en2, by antareep9035, 2024-10-31 19:33:49

This solution uses queue and deque. The primary concept is that starting from the last '1', we take all the zeroes that are before the previous '1'. If the previous digit is '1', then we take the last '0' that is available. If we have no '0's left, we take the first '1' that is available to us. To implement this process, we can store the indices of '0's in a queue and the indices of '1's in a deque. The time complexity is O(n).

Code(C++): ~~~~~

include <bits/stdc++.h>

using namespace std;

define ll long long

define pb push_back

define dd double

define ff float

define ss string

define ins insert

define vv vector

//Function to solve problem starts ll solve(ss s, ll n){ queue q; deque dq; for(ll i = n — 1; i >= 0; i --){ if(s[i] == '0'){ q.push(i); } else{ dq.pb(i); } } ll ans = 0; for(ll i = n — 1; i >= 0; i --){ if(s[i] == '1'){ if(! dq.empty()) dq.pop_front(); if(! q.empty()){ ans += (i + 1); q.pop(); while(q.front() > dq.front() && ! q.empty()){ q.pop(); } } else{ if(! dq.empty()){ ans += (i + 1); dq.pop_back(); } } } } ll total = (n * (n + 1)) / 2; return total — ans; }

//Function to solve problem ends

//main function starts

int main(){ ll t; cin >> t; while(t --){ ll n; cin >> n; ss s; cin >> s; cout << solve(s, n) << endl; } return 0; }

//main function ends ~~~~~

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English antareep9035 2024-10-31 19:39:03 0 (published)
en7 English antareep9035 2024-10-31 19:38:04 30
en6 English antareep9035 2024-10-31 19:37:28 65
en5 English antareep9035 2024-10-31 19:36:32 30
en4 English antareep9035 2024-10-31 19:35:37 8 Tiny change: 'e all the zeroes that are' -> 'e all the '0's that are'
en3 English antareep9035 2024-10-31 19:34:27 6
en2 English antareep9035 2024-10-31 19:33:49 61
en1 English antareep9035 2024-10-31 19:33:08 1704 Initial revision (saved to drafts)