BINARYSUB - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Tejas Pandey
Tester: Harris Leung
Editorialist: Nishank Suresh

DIFFICULTY:

TBD

PREREQUISITES:

Dynamic programming

PROBLEM:

Given a binary string S, you can replace 01 with a, 10 with b, 010 with ab, and 101 with ba.

Given a string of a's and b's, how many initial strings could possibly have created this string?

EXPLANATION:

We will use dynamic programming to find the answer.
Let A denote the input string.

Let dp_i denote the number of binary strings such that after replacement, they can form the first i characters of A. The answer we want is, of course, dp_N.

As a base case, we have dp_0 = 1, since we can only form the empty string from the empty string. Now, for i \geq 1:

  • Suppose A_i = a. Then, we have two choices for a binary string that forms A_1A_2\ldots A_i
    • If its last two characters were 01, we could replace them with a, then form the other i-1 characters from the remaining part of the string. There are dp_{i-1} ways to form the rest of the string.
    • If its last three characters were 101 and A_{i-1} = b, we could replace 101 with ba and then form the remaining i-2 characters in dp_{i-2} ways. Note that this is only applicable when i \geq 2.
    • There is no other way to obtain a string ending with a.
  • The analysis for A_i = b will give you the exact same transitions.

So, our dp is as follows:

  • dp_0 = 1
  • For i \geq 1, dp_i = dp_{i-1}
  • Further, if i \geq 2 and A_i \neq A_{i-1}, add dp_{i-2} to dp_i.

Finally, print dp_N.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python) 
mod = 998244353
for _ in range(int(input())):
    s = input()
    n = len(s)
    dp = [1]*(n+1)
    for i in range(1, n):
        dp[i+1] = dp[i]
        if s[i] != s[i-1]:
            dp[i+1] += dp[i-1]
        dp[i+1] %= mod
    print(dp[n])
1 Like
2

I solved it using Fibonacci sequence.

https://www.codechef.com/viewsolution/76392104

2 Likes
3

hey, I also applied the same logic but it didn’t go well my code works great for small test cases but for large test cases my code output comes out to be 0 can you suggest something that I missed

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define mii map<ll,ll>
#define pii pair<ll,ll>
#define vi vector<ll>
#define endl '\n'
#define REP(i,a,b) for(int i=a;i<b;i++)
#define input vi arr;REP(i,0,n){ll ele;cin>>ele;arr.pb(ele);}
void  solve(vi dp)
{
    string arr;
    cin>>arr;
    ll result=1;
    ll curr=1;
    ll n=arr.size();
    REP(i,0,n-1)
    {
        if(arr[i]!=arr[i+1])
        {
            curr++;
            continue;
        }
        else
        {
            result*=dp[curr];
            curr=1;
        }
    }
    result*=dp[curr]%998244353;
    cout<<result%998244353;
    return ;
}
int main()
{
    ll t;
    cin>>t;
    vi dp;
    dp.pb(0);
    dp.pb(1);
    dp.pb(2);
    REP(i,3,100001)
    {
        dp.pb((dp[i-1]+dp[i-2])%998244353);
    }
    while(t--)
    {
        solve(dp);
        cout<<"\n";
    }
    return 0;
}
4

Fascinating approach, I almost understand it but am having some difficulty perhaps because I am not familiar with the language, could you please explain how the fibonacci sequence works for this problem.
Thank you.

5

It’s obvious that consecutive same lettes doesn’t make new cases:
aaaaaaaaaa \to 1 possible construction of binary string.
ab\to 2 possible cases, and aaaaaabbbbbb \to 2 possible cases as well.

So it’s optimal to consider these parts of string in blocks:
abababababababa\dots

Let’s find how many different strings we can make up.
Let’s consider a simple case - aba
Let’s say if we replace ab with 010 we denote it like this \left\{ ab\right\}. And if we separetly replace a and b we denote it like this \left\{ a,b\right\}

So in case of aba , these cases are possible: \left\{ a,b,a\right\},\left\{ ab,a\right\}, \left\{ a,ba\right\} - 3 cases.
This way all the binary strings are distict.

To find solution for larger string (ababa\dots ) we have to make a simple observation.
Suppose we have abab\dots ab of length n.

Now let’s consider all first positions where we pick ab or ba

\left\{a, b, a, b, \dots, a, b, a, b \right\}

Then the answer will be the sum of possible cases here:
\left\{ab, "abab..." (len = n-2)\right\}
\left\{a, ba, "baba..." (len = n-3)\right\}
\left\{a, b, ab, "abab..." (len = n-4)\right\}
and so on
\dots
\left\{a, b, a, b, \dots, a, b, "ab" \right\}
\left\{a, b, a, b, \dots, a, b, a, "b" \right\}

Here \left\{ a,b,a,\dots\right\} means that we already picked it and we don’t consider them.
ababa... means that we consider possible cases this string can give.
If we denote the number of distinct binary strings ababa... with length k can give as f(k), the answer for ababa will be:

f(k-2)+f(k-3)+\dots +f(1)+f(0)+f(0)

The basic cases: f(0)=1, f(1)=1.
(Obviously, if we have "" or a there is only 1 way we can make up a binary string.

Then:

f(k)-f(k-1)=(f(k-2)+f(k-3)+\dots + f(1)+f(0)+f(0)) - (f(k-1)+f(k-3)+\dots+f(1)+f(0)+f(0))

f(k)-f(k-1)=f(k-2)

f(k)=f(k-1)+f(k-2)

Here we go!

But! We only considered some ababa substring of S.
The final answer to the problem is the product of all these f(k). Where k - length of some substring ababa\dots

We can simply precompute Fib array in O(10^5) and answer the queries in O(n)

2 Likes