# OFFBYONE - Editorial

**URL:** <https://discuss.codechef.com/t/offbyone-editorial/126137>\
**Category:** editorial\
**Tags:** dynamic-programming, easy, editorial, inclusion-exclusion, start263\
**Created:** [November 4, 2026, 4:30pm UTC](https://discuss.codechef.com/t/offbyone-editorial/126137 "2026-11-04T16:30:17Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![iceknight1093](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@iceknight1093](https://discuss.codechef.com/u/iceknight1093)\
**Post date:** [November 4, 2026, 4:30pm UTC](https://discuss.codechef.com/t/offbyone-editorial/126137/1 "2026-11-04T16:30:17Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/OFFBYONE)  
[Contest: Division 1](https://www.codechef.com/START263A/problems/OFFBYONE)  
[Contest: Division 2](https://www.codechef.com/START263B/problems/OFFBYONE)  
[Contest: Division 3](https://www.codechef.com/START263C/problems/OFFBYONE)  
[Contest: Division 4](https://www.codechef.com/START263D/problems/OFFBYONE)

_ **Author:** _ [iceknight1093](https://www.codechef.com/users/iceknight1093)  
_ **Tester:** _ [raysh07](https://www.codechef.com/users/raysh07)  
_ **Editorialist:** _ [iceknight1093](https://www.codechef.com/users/iceknight1093)

# DIFFICULTY:

Easy

# PREREQUISITES:

Dynamic programming, inclusion-exclusion

# PROBLEM:

Given a binary string S of length N-1, count permutations P of length N such that:

- S\_i = 1 if and only if |P\_i - P\_{i+1}| = 1.

# EXPLANATION:

Consider a block of ones in S, say S\_i = S\_{i+1} = \ldots = S\_j = 1.  
This means, in P, the indices i, i+1, \ldots, j+1 can contain either the values [x, x+1, x+2, \ldots, x+j-i+1], or [x, x-1, x-2, \ldots, x-(j-i+1)].  
There is no other way for all these adjacent values to differ by 1.

So, the permutation will contain several ‘blocks’ of contiguous values.  
This doesn’t cover every index though, so each remaining element can be treated as a block of size 1 instead.  
Note that size 1 blocks have only one orientation possible (as opposed to larger blocks having two.)

This breaks up the permutation entirely into blocks - our task now is to:

1. Pick the values that go into each block,
2. Pick the orientation of the values inside each length \gt 1 block, and
3. Ensure that two adjacent blocks don’t differ by 1 at their borders.

* * *

Let’s ignore the third condition for now, and see what could be done if we had only the first two conditions.

Suppose we have k blocks (including singletons), of which m are not singletons.  
Let their sizes be x\_1, \ldots, x\_k from left to right.

One way of building a permutation is then as follows:

- Fix an order of the blocks, say q\_1, q\_2, \ldots, q\_k.
- Give the values 1, 2, \ldots, x\_{q\_1} to the first block, x\_{q\_1}+1, \ldots, x\_{q\_1} + x\_{q\_2} to the second block, and so on.
- For each block of size \gt 1, choose which orientation the values in the block takes.

There are k! \cdot 2^m ways to do this, because after the first step (fixing block order), the second step is forced; and the third (deciding orientation) is independent of the order chosen and happens once for each valid block.

However, this clearly overcounts, because we did not account for adjacent blocks not differing by one.

How do we deal with that?  
Using inclusion-exclusion!

For each pair of adjacent blocks, consider the event that these blocks hold consecutive values at their endpoints.  
Functionally, this is like merging these two blocks into a single, larger block.

So, if the final permutation has (at most) x block components in reality, we must have performed k - x merges.  
This term hence has the inclusion-exclusion sign (-1)^{k-x}.

* * *

One issue with doing inclusion-exclusion directly is that not all ways of merging into x blocks are equivalent: recall that the contribution was k! \cdot 2^c, and while k! easily becomes x!, the 2^c term is not so easy to deal with since it depends on whether some size-1 blocks merged (and if they did, which ones and how many; since two size-ones merging is different from a size-1 and a larger block merging).

To deal with this, we use dynamic programming.

Define dp(i, j) to be the total weighted sum of all ways of merging the first i blocks into j blocks; where the weight of a configuration is 2^c, with c being the number of \ge 2 length blocks.

To calculate this, we do the following:

- Fix s \le i, and suppose that blocks s, s+1, \ldots, i all merge into one block.
  - Then we need j-1 blocks from everything before s, and there are two configurations for the last block itself.
  - So, s contributes dp(s-1, j-1)\cdot 2 to dp(i, j).

- The one exception to this is when s = i and the i-th block has size 1, in which case it has a multiplier of only 1, and so s contributes dp(s-1, j-1) only.

This gives us a way to compute dp(i, j) in linear time, by iterating over all s \le i and computing the transition appropriately.  
This can be sped up to constant time using prefix sums since only the j-1 column matters for computing dp(i, j).

This allows us to compute all dp(i, j) in quadratic time.

Once that is done, by virtue of the inclusion-exclusion outlined above, the answer is simply

\sum\_{i=1}^k (-1)^{k-i} dp(k, i) \cdot i!

# TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

# CODE:

> **Tester's code (C++)**
>
> ```cpp
> #include <bits/stdc++.h>
> using namespace std;
> #define int long long
> #define INF (int)1e18
> 
> mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
> 
> const int mod = 998244353;
> 
> struct mint{
> int x;
> 
> mint (){ x = 0;}
> mint (int32_t xx){ x = xx % mod; if (x < 0) x += mod;}
> mint (long long xx){ x = xx % mod; if (x < 0) x += mod;}
> 
> int val(){
> return x;
> }
> mint &operator++(){
> x++;
> if (x == mod) x = 0;
> return *this;
> }
> mint &operator--(){
> if (x == 0) x = mod;
> x--;
> return *this;
> }
> mint operator++(int32_t){
> mint result = *this;
> ++*this;
> return result;
> }
>     
> mint operator--(int32_t){
> mint result = *this;
> --*this;
> return result;
> }
> mint& operator+=(const mint &b){
> x += b.x;
> if (x >= mod) x -= mod;
> return *this;
> }
> mint& operator-=(const mint &b){
> x -= b.x;
> if (x < 0) x += mod;
> return *this;
> }
> mint& operator*=(const mint &b){
> long long z = x;
> z *= b.x;
> z %= mod;
> x = (int)z;
> return *this;
> }
> mint operator+() const {
> return *this;
> }
> mint operator-() const {
> return mint() - *this;
> }
> mint operator/=(const mint &b){
> return *this = *this * b.inv();
> }
> mint power(long long n) const {
> mint ok = *this, r = 1;
> while (n){
> if (n & 1){
> r *= ok;
> }
> ok *= ok;
> n >>= 1;
> }
> return r;
> }
> mint inv() const {
> return power(mod - 2);
> }
> friend mint operator+(const mint& a, const mint& b){ return mint(a) += b;}
> friend mint operator-(const mint& a, const mint& b){ return mint(a) -= b;}
> friend mint operator*(const mint& a, const mint& b){ return mint(a) *= b;}
> friend mint operator/(const mint& a, const mint& b){ return mint(a) /= b;}
> friend bool operator==(const mint& a, const mint& b){ return a.x == b.x;}
> friend bool operator!=(const mint& a, const mint& b){ return a.x != b.x;}
> mint power(mint a, long long n){
> return a.power(n);
> }
> friend ostream &operator<<(ostream &os, const mint &m) {
> os << m.x;
> return os;
> }
> explicit operator bool() const {
> return x != 0;
> }
> };
> 
> // Remember to check MOD
> 
> struct factorials{
> int n;
> vector <mint> ff, iff;
>     
> factorials(int nn){
> n = nn;
> ff.resize(n + 1);
> iff.resize(n + 1);
>         
> ff[0] = 1;
> for (int i = 1; i <= n; i++){
> ff[i] = ff[i - 1] * i;
> }
>         
> iff[n] = ff[n].inv();
> for (int i = n - 1; i >= 0; i--){
> iff[i] = iff[i + 1] * (i + 1);
> }
> }
>     
> mint C(int n, int r){
> if (n == r) return mint(1);
> if (n < 0 || r < 0 || r > n) return mint(0);
> return ff[n] * iff[r] * iff[n - r];
> }
>     
> mint P(int n, int r){
> if (n < 0 || r < 0 || r > n) return mint(0);
> return ff[n] * iff[n - r];
> }
>     
> mint solutions(int n, int r){
> // Solutions to x1 + x2 + ... + xn = r, xi >= 0 
> return C(n + r - 1, n - 1);
> }
>     
> mint catalan(int n){
> return ff[2 * n] * iff[n] * iff[n + 1];
> }
> };
> 
> const int PRECOMP = 3e6 + 69;
> factorials F(PRECOMP);
> 
> // REMEMBER To check MOD and PRECOMP
> 
> void Solve() 
> {
> int n; cin >> n;
> string s; cin >> s;
>     
> // consider only constraints of type s[i] = 1 
> // let k be number of components, answer = k! * 2^(non-single components)
>     
> vector <int> a;
> for (int i = 0; i < n; i++){
> int c = 1;
> int p = i;
> while (p < n - 1 && s[p] == '1') p++, c++;
> a.push_back(c);
> i = p;
> }
>     
> vector<vector<mint>> dp(n + 1, vector<mint>(n + 1, 0));
> vector<mint> sum(n + 1);
> sum[0] = 1;
> dp[0][0] = 1;
>     
> for (int i = 0; i < a.size(); i++){
> for (int j = 1; j <= i + 1; j++){
> dp[i + 1][j] = sum[j - 1] * 2;
> if (a[i] == 1){
> dp[i + 1][j] -= dp[i][j - 1];
> }
> }
> for (int j = 1; j <= i + 1; j++){
> sum[j] += dp[i + 1][j];
> }
> }
>     
> mint ans = 0;
> int sz = a.size();
> for (int k = sz; k >= 1; k--){
> mint here = dp[sz][k] * F.ff[k];
> if (k % 2 == sz % 2) ans += here;
> else ans -= here;
> }
> cout << ans << "\n";
> }
> 
> int32_t main() 
> {
> auto begin = std::chrono::high_resolution_clock::now();
> ios_base::sync_with_stdio(0);
> cin.tie(0);
> int t = 1;
> // freopen("in", "r", stdin);
> // freopen("out", "w", stdout);
>     
> cin >> t;
> for(int i = 1; i <= t; i++) 
> {
> //cout << "Case #" << i << ": ";
> Solve();
> }
> auto end = std::chrono::high_resolution_clock::now();
> auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
> cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
> return 0;
> }
> 
> ```

!