PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: triggered_code
Tester: jay_1048576
Editorialist: iceknight1093
DIFFICULTY:
2594
PREREQUISITES:
Greedy algorithms
PROBLEM:
You’re given a large integer A in binary representation as a string of length N.
Find two binary strings B and C such that A = B-C, and the sum of counts of ones in B and C is minimized.
EXPLANATION:
For convenience, this explanation will treat A, B, C as if they were reversed and 0-indexed, so that A_i corresponds to whether 2^i is set in A or not and so on.
In terms of implementation, this means you can reverse A, follow the solution below, then reverse B and C before printing them.
The problem essentially asks us to write A using the smallest number of powers of two, except we’re allowed to both add and subtract them (addition goes into B, subtraction goes into C).
However, there’s one small catch: B and C have to be of length N each, which means we can’t use larger powers.
Let’s first solve this without the restriction on length N — in the end, we can see how it comes into play.
If we weren’t allowed subtraction, the best we can do is obviously to just use all the bits set in the binary representation of A. So, let’s take this as our starting point and see how to reduce it.
The main power of subtraction is that it allows us to reduce a block of ones into two ones.
That is, we have
so we can replace y-x+1 additive powers of two with just two of them.
Of course, if x = y, this will replace one power of two with two of them, which is bad so we won’t do it.
This gives us a natural greedy solution:
- Let B = A and C be filled with zeros initially.
- Iterate from left to right, i.e from lower bits to higher bits; and find a maximum block of ones in B, say [L, R]. In particular, this means B_{L-1} = B_{R+1} = 0 must hold.
- If L = R, ignore it.
- Otherwise, set B_{R+1} = 1 and C_L = 1, since we’re replacing 2^L + \ldots + 2^R by 2^{R+1} - 2^L.
Note that iterating from lower to higher is important here because it allows us to further replace the bits we add to B.
For example, if A = \texttt{110110}, going from low to high we’d get:
- Step 1: B = \texttt{001110}, C = \texttt{100000}
- Step 2: B = \texttt{000001}, C = \texttt{101000}
whereas if we went high to low we’d get - Step 1: B = \texttt{110001}, C = \texttt{000100}
- Step 2: B = \texttt{001001}, C = \texttt{100100}
which is not optimal.
This almost solves our problem in \mathcal{O}(N): the only thing that needs to be taken care of is the very end.
That is, notice that when replacing a block of ones, we need to use the next higher position.
However, if this block of ones forms a suffix of the string, the next position doesn’t exist, so we can’t perform this replacement.
It’s not hard to see that if a block of ones forms a suffix like this, then we have no choice: this suffix of ones must be set in B and none of them can be set in C.
So, we can simply delete the suffix of ones, solve normally for the remaining string (now without having to worry about edgecases!) and finally add the ones back in.
This way, we’ve solved the problem in \mathcal{O}(N).
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
#include <iostream>
#include <cassert>
#define int long long
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repr(i,n) for(int i = n-1; i >= 0; i--)
#define ff first
#define ss second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sz(x) (x).size()
#define all(x) x.begin(), x.end()
#define mems(x,a) memset((x), a, sizeof(x))
const char nl = '\n';
const int INF = LONG_MAX;
using namespace std;
using namespace __gnu_cxx;
// READ TEMPLATE
void read(){}
void read(unsigned int&a){cin>>a;}
void read(int& a){cin>>a;}
void read(double& a){cin>>a;}
void read(float& a){cin>>a;}
void read(string& a){cin>>a;}
template<typename x,typename y>void read(pair<x,y>& a){ read(a.first),read(a.second);}
template<typename x>void read(x& a){for(auto &i : a) read(i);}
template<typename x,typename... y>void read(x& a,y&... b){read(a);read(b...);}
// DEBUG TEMPLATE
void _print(char i){ cout<<i;}
void _print(string i){ cout<<i;}
void _print(float i){ cout<<i;}
void _print(int i){ cout<<i;}
void _print(double i){ cout<<i;}
void _print(bool i){ cout<<i;}
void _print(long double i){ cout<<i;}
void _print(){cout<<"\n";};
template<typename x,typename y> void _print(pair<x,y>&t){cout<<"{ ";_print(t.first);cout<<" , ";_print(t.second);cout<<" },";}
template<typename x> void _print(x &t){ cout<<"{ "; for(int i = 0;i < (int)t.size();i++){ _print(t[i]); if(i < (int) t.size() - 1) cout<<", "; } cout<<" }"; }
template<typename x,typename... y> void _print(x a,y... b){_print(a);if(sizeof...(b)) cout<<" , ";_print(b...);}
#define dbg(x...) cout<<"DEBUG : "<<#x<<" => ";_print(x);cout<<"\n";
vector<int> prime(int a, int b){
vector<bool> v(b+1, 1);
vector<int> ans;
rep(i,2,b+1){
if(v[i]){
for(int j = 2*i; j <= b; j += i){
v[j] = 0;
}
if(i >= a) {ans.pb(i);};
}
}
return ans;
}
bool subtract(string &a, string &b, string &c) {
int n = a.size();
/* Going from lsb to msb so we can ask for borrow */
for(int i = 0; i < n; i++){
int x = b[i]-'0';
int y = c[i]-'0';
int z = x-y;
if(z < 0){
int j = i;
while(j < n and b[j] == '0') j++;
if(j != n){
z = 1;
b[j--] = '0';
while(j >= i){
b[j--] = '1';
}
}
else return false;
}
if(a[i] != '0'+z) return false;
}
return true;
}
bool test_case = 1;
void solve() {
int n;
cin >> n;
string a;
cin >> a;
reverse(a.begin(), a.end());
string b="",c="";
int cnt=0;
for(int i=0;i<n;i++)
{
if(a[i]=='1')
cnt++;
else
{
if(cnt>=1)
{
c+='1';
for(int j=0;j<cnt;j++)
{
b+='0';
c+='0';
}
b+='1';
}
else
{
b+='0';
c+='0';
}
cnt=0;
}
}
while(b.length()<n)
{
b+='1';
c+='0';
}
for(int i=0;i<n-1;i++)
{
if(b[i]=='1' && c[i+1]=='1')
{
b[i]='0';
c[i]='1';
c[i+1]='0';
}
else if(b[i+1]=='1' && c[i]=='1')
{
b[i]='1';
c[i]='0';
b[i+1]='0';
}
}
reverse(b.begin(), b.end());
reverse(c.begin(), c.end());
cout << b << '\n' << c << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt" , "r" , stdin) ;
freopen("output.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif
int T = 1;
if(test_case) cin>>T;
while( T-- ){
solve();
}
return 0;
}
Editorialist's code (C++)
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
reverse(begin(s), end(s));
int suf = 0;
while (!s.empty()) {
if (s.back() == '1') s.pop_back();
else break;
++suf;
}
string b = s, c(n-suf, '0');
for (int i = 0; i < n-suf;) {
if (b[i] == '0') {++i; continue;}
int j = i;
while (j >= 0 and b[j] == '1') {
++j;
}
if (j-i > 1) {
c[i] = '1';
for (int k = i; k < j; ++k) b[k] = '0';
b[j] = '1';
}
i = j;
}
b += string(suf, '1'); reverse(begin(b), end(b));
c += string(suf, '0'); reverse(begin(c), end(c));
cout << b << '\n' << c << '\n';
}
}
