PROBLEM LINK:
Contest - Division 4
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
SIMPLE
PROBLEM:
Given a binary string S. You may perform the following operation any number of times - choose a previously unselected number X, and flip some substring of S with length X.
Determine a sequence of moves that sorts S in non-decreasing order.
EXPLANATION:
Hint 1
The binary string comprising of all 0's (or all 1's) is in non-decreasing order.
Can you apply the operations to convert the string into either of the above?
Hint 2
Try iteratively converting an increasing prefix of S into all 0's or all 1's.
Solution
We solve with the help of an example.
Consider S=1110110010. A valid sequence of moves is given below:
1110110010 // Original string
0000110010 // Invert prefix of len 3
1111110010 // Invert prefix of len 4
0000000010 // Invert prefix of len 6
1111111110 // Invert prefix of len 8
0000000000 // Invert prefix of len 9
More formally, we repeatedly invert the longest prefix of S consisting of the same value, until the string is all 0's or all 1's. It is easy to see that the lengths of the inverted substrings are increasing, and hence distinct.
This can be implemented efficiently by iterating over S (from left to right) and appending range [1..i] to the set of inverted substrings when S[i]\ne S[i+1].
TIME COMPLEXITY:
Since we iterate over the string only once, the total time complexity is
O(N)
per test case.
SOLUTIONS:
Editorialist’s solution can be found here.
Author's solution
#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;
int t, n;
string s;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> t;
for(int cases = 0; cases < t; cases++)
{
cin >> n >> s;
int parity = 0;
vector<pii> ops;
for(int i = n - 1; i >= 0; i--)
if((s[i] - '0') ^ parity)
{
ops.push_back({1, i});
parity ^= 1;
}
cout << ops.size() << "\n";
for(auto x : ops)
cout << x.first << " " << x.second << "\n";
}
return 0;
}
Tester's solution
// Super Idol的笑容
// 都没你的甜
// 八月正午的阳光
// 都没你耀眼
// 热爱105°C的你
// 滴滴清纯的蒸馏水
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n;
string s;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
int TC;
cin>>TC;
while (TC--){
cin>>n;
cin>>s;
vector<ii> ans;
rep(x,0,n-1) if (s[x]!=s[x+1]) ans.pub({1,x+1});
cout<<sz(ans)<<endl;
for (auto [a,b]:ans) cout<<a<<" "<<b<<endl;
}
}
3 Likes
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define endl "\n"
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
//----------------------------------------------
// if 000000 or 1111111 then print directly "0"
int zero=0;
rep(i,0,n)
{
if(s[i]=='0')
zero++;
}
if(zero==n || zero==0)
{
cout<<"0"<<endl;
return ;
}
//----------------------------------------------
// this part is to set starting postion for test cases like 000010101 number of steps are 2
//coz first prefix "0" shd not be counted
int start=0;
rep(i,0,n)
{
if(s[i]=='1')
{
start=i;
break;
}
}
//--------------------------------------------------
vector<int> v; // this vector store postion of all zeros (excpet prefixing zeros)
rep(i,start,n)
{
if(s[i]=='0')
v.push_back(i+1);
}
//------------------------------------------------------
// number of zero's excluding prefixing zeros is number of steps
int n1=v.size();
cout<<n1<<endl;
if(n1>0)
{
cout<<"1 "<<v[0]-1<<endl; // 1 to (first 0 postion-1)
rep(i,0,n1-1)
cout<<v[i]+1<<" "<<v[i+1]-v[i]<<endl;
}
cout<<endl;
}
signed main()
{
int t; cin>>t;
while(t--)
solve();
return 0;
}
This is my solution !!.. this passed sample TC and also TC shown in Editorial
but it gives WA
can anyone tell me which TC is it failing
I have tried to explain my logic through comments in the code
please tell me where iam going wrong !!!
Hey @codeus1234 
,
Your code is failing for the case
1
9
110110101
your output is giving 2 2’s as X which is wrong ,I would suggest you to traverse from right to left and every time you see different parity you need to do the operation (here is a trick always do the operation from the 1 to i(where s[I] changes)
you can go through my code for the same logic
#include <iostream>
#include<bits/stdc++.h>
#include<deque>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<stdio.h>
#include<bitset>
#include<string>
#include<vector>
#include<unordered_map>
#include<queue>
#include<set>
#include<fstream>
#include<map>
#define int long long int
#define ld long double
#define pi 3.1415926535897932384626433832795028841971
#define MOD 1000000007
#define MOD1 998244353
#define print(vec) for (int i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << "\n";
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int inf = 1e18;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
#ifdef __SIZEOF_INT128__
ostream& operator << (ostream &os, __int128 const& value) {
static char buffer[64];
int index = 0;
__uint128_t T = (value < 0) ? (-(value + 1)) + __uint128_t(1) : value;
if (value < 0)
os << '-';
else if (T == 0)
return os << '0';
for (; T > 0; ++index) {
buffer[index] = static_cast<char>('0' + (T % 10));
T /= 10;
}
while (index > 0)
os << buffer[--index];
return os;
}
istream& operator >> (istream& is, __int128& T) {
static char buffer[64];
is >> buffer;
size_t len = strlen(buffer), index = 0;
T = 0; int mul = 1;
if (buffer[index] == '-')
++index, mul *= -1;
for (; index < len; ++index)
T = T * 10 + static_cast<int>(buffer[index] - '0');
T *= mul;
return is;
}
#endif
int add(long long a, long long b) {return ((a % MOD) + (b % MOD)) % MOD;}
int subtract(long long a, long long b) {return ((a % MOD) - (b % MOD)) % MOD;}
int mult(long long a, long long b) {return ((a % MOD) * (b % MOD)) % MOD;}
int add1(long long a, long long b) {return ((a % MOD1) + (b % MOD1)) % MOD1;}
int subtract1(long long a, long long b) {return ((a % MOD1) - (b % MOD1)) % MOD1;}
int mult1(long long a, long long b) {return ((a % MOD1) * (b % MOD1)) % MOD1;}
int expo(int a, int b, int mod) {
int res = 1;
while (b > 0)
{ if (b & 1)
res = (res * a) % mod;
a = (a * a) % mod;
b = b >> 1;
} return res;
}
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int mminvprime(int a, int b) {
return expo(a, b, b + 2);
}
int32_t main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
string s;
cin >> s;
int c0 = 0, c1 = 0;
for (auto x : s) c1 += (x == '1');
c0 = n - c1;
int i = n - 1;
while (i >= 0 && s[i] == '1')
{
c1--;
i--;
}
if (i <= 0)
{
cout << 0 << "\n";
continue;
}
std::vector<pair<int, int>> v;
int st = 0;
while (i >= 0)
{
if (0 != i + 1)
v.push_back({0, i});
while (i >= 0 && s[i] - '0' == st)
{
i--;
}
st = 1 - st;
}
cout << v.size() << "\n";
for (auto x : v) cout << x.first + 1 << " " << x.second + 1 << "\n";
}
return 0;
}