PROBLEM LINK:
Setter: Kasra Mazaheri
Tester: Arshia Soltani
Editorialist: Kasra Mazaheri
DIFFICULTY:
Simple
PREREQUISITES:
Bruteforce, Dynamic Programming
PROBLEM:
Given a binary string S of length N, we want to delete minimum number of characters from it so that it wouldn’t contain subsequence 0101 or 1010 (so that it becomes pure). Find this minimum value.
QUICK EXPLANATION
- A string is pure if and only if there are at most 3 maximal blocks of consecutive equal characters in the string.
- We can calculate the number of 0's and 1's of an interval using partial sum (or dynamic programming).
- We can fix the endpoints of the 3 maximal blocks along with their character (0 or 1) and calculate the minimum number of indices which should be deleted in this configuration of blocks using partial sums.
EXPLANATION
We define a block to be a maximal consecutive block of equal characters in a string. For example, the string 000110100111 consists of 6 blocks : 000, 11, 0, 1, 00 and 111.
It’s clear that two consecutive blocks have different characters, or else they wouldn’t have been maximal. As a result, any string with more than 3 blocks will not be pure, since we can pick the first character of each of the first 4 blocks and it would either be 0101 or 1010. So the resulting string should consist of at most 3 blocks.
We can fix the interval of the middle block (say [L, R]) and it’s character (say 0, the case of 1 is exactly the same). Now all we have to do is to count the number of indices i such that S_i is different than the character of it’s corresponding block. So we should count the number of 0's in the intervals [1, L-1] and [R + 1, N] and the number of 1's in the interval [L, R]. We can calculate this value with partial sums. Namely, define P_i to be the number of 0's in the interval [1, i]. Then the number of 0's in an interval [A, B] will be P_B - P_{A - 1}. The number of 1's can also be calculated as (B - A + 1) - (P_B - P_{A - 1}). Thus we can calculate the number of indices that have to be deleted in O(1). Fixing the interval is O(N ^ 2) so we arrive at a final O(N ^ 2) solution.
TIME COMPLEXITY
The time complexity is O(N ^ 2) per test case.
SOLUTIONS:
Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int q, n, P[2][N];
char S[N];
int main()
{
scanf("%d", &q);
for (; q; q --)
{
scanf("%s", &S[1]);
n = strlen(S + 1);
for (int i = 1; i <= n; i ++)
for (int w = 0; w <= 1; w ++)
P[w][i] = P[w][i - 1] + (S[i] == w + '0');
int Mn = n;
for (int w = 0; w <= 1; w ++)
for (int i = 1; i <= n; i ++)
for (int j = i; j <= n; j ++)
Mn = min(Mn, P[w][i - 1] + (j - i + 1) - (P[w][j] - P[w][i - 1]) + (P[w][n] - P[w][j]));
printf("%d\n", Mn);
memset(S, 0, sizeof(S));
memset(P, 0, sizeof(P));
}
return 0;
}
Tester's Solution
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
long long gcd(long long a, long long b) {return b == 0 ? a : gcd(b, a % b);}
#define ll int
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=1e4+500;
ll p[maxn];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll q;
cin>>q;
while(q--){
string s;
cin>>s;
ll n=(ll)s.size();
for(ll i=0;i<n;i++){
p[i+1]=p[i];
if(s[i]=='1'){
p[i+1]++;
}
}
ll mx=0;
for(ll i=0;i<n;i++){
for(ll j=i+1;j<=n;j++){
mx=max(mx,p[j]-p[i]+i-p[i]+n-j-p[n]+p[j]);
mx=max(mx,j-i-p[j]+p[i]+p[i]+p[n]-p[j]);
}
}
cout<<n-mx<<endl;
for(ll i=0;i<=n;i++)
p[i]=0;
}
}
Feel free to share your approach. As usual, suggestions are warmly welcomed. 