### ShivanshJ's blog

By ShivanshJ, history, 5 months ago,

I feel that the problem is not explained in tutorial in sufficient detail. Let $a_i$ denote $i^{th}$ bit in $a$, and so on for various variables. First, lets handle the bits independently, for $i^{th}$ bit, we have a tuple $(m_i, a_i, b_i)$ and we want to get $(c_i, d_i)$. Let's map this $i^{th}$ bit tuple $(m_i, a_i, b_i)$ into integer (binary) as $S[i] = 4m_i + 2a_i + b_i$ and tuple $(c_i, d_i)$ into $D[i] = 2*c_i + d_i$

The first observation is that (as highlighted in editorial, that if for some $i$ and $j$, if $S[i] = S[j]$ then, $D[i]$ must be equal to $D[j]$, otherwise no solution exists.

The second crucial observation is we can reduce the problem involving "lesser numbers" (instead of dealing with numbers of size $2^{30}$), since there are only $8$ possibilities of $S[i]$ and $4$ for $D[i]$. How do we do that exactly?

Consider a $8$ bit number is base $4$, the $i^{th}$ bit $(i < 8)$ in binary represents $S[i]$ (since there are $8$ possibilities we have bits from $0$ to $7$) and the destination $D[i]$ is put into $i^{th}$ position in that number. Since there are $4$ possible values of $D[i]$ $(0 \le D[i] < 4)$, we are working in base $4$. This is our state.

However, notice that, every value of $S[i]$ cannot be mapped to $D[i]$ since, some tuples $(m, a, b)$ may not even occur! So, for those tuples we can map them into a fake value of $D[i]$ (take it as $4$), so instead of base $4$ we have to work with base $5$. There are only $5^8$ possibilities. If we construct a directed graph, then it has $5^8$ nodes and $4*5^8$ edges. (Since every node has $4$ edges coming out of it).

Now, let $dist[i]$ denote the minimum distance from node $i$ from some node $j$ whose $dist[j]$ is $0$. Obviously for $j = (32103210)_5$, $dist[j] = 0$, because it takes $0$ moves to reach that state. However for any $i$ ($i=(32103210)_5$ initially) in you select any number of positions such that for every selected position $k$ $(0 \le k < 8)$, put $4$ into that position $(S[i][k] = 4)$ then also $dist[i] = 0$.

Just run a multisource BFS from all those nodes $i$ whose $dist[i] = 0$, then every testcase can be answered easily!

That's it!

Edit

Attached my submission here (apologies for unclear and long code), $nxt[i][j]$ denotes the next $mask$ (the $8$ bit number in base $5$) we get when we perform $j^{th}$ operation (for example $j=0$ means AND operation) on mask $i$. $prepow[i]$ denotes the value of $5^{i}$. $dist[i]$ denotes the min of distance from node $i$ from all those nodes $j$ such that $dist[j] = 0$. Function $mask(a,b,c,d,m)$ calculates the value of mask given these parameters.

• +119

By ShivanshJ, history, 5 months ago,

Many of my friends asked this interesting OA problem to me:

Given an array of strings $A$ of size $N$ and two integers $B$ and $C$.

Let $D$ be the number of strings of length $C$ that contains exactly $B$ of the strings in $A$ as substring.

Return $D$ mod $10^9+9$.

Constraints

$1 \le N \le 6$

$1 \le |A[i]| \le 50$

All the $N$ strings are distinct

$0 \le B \le N$

$1 \le C \le 50.$

Note that if a substring belonging to set $A$ occurs multiple times in my resulting string, it is counted only once.

My approach:

Let $Z$ be the size of the alphabet $(26)$.

Let $dp[i][j][k][m]$ denote the number of strings satisfying the constraints:

1) It is of length $i$.

2) The longest suffix present in it which is a proper prefix of some string belonging to set $A$ is the substring $[k...i]$ and the string whose proper prefix is the $j^{th}$ string in set $A$, in case of multiple such strings in $A$ choose the one with longest length. In case no such suffix exists, we can put a fake "empty string" at index $0$ in set $A$ (rest of the strings are numbered from $1$ to $N$) and assume that substring is $[i+1 , i]$.

3) The substrings (belonging to set $A$) which has already been occurred is denoted by mask $m$, more formally, if the $w^{th}$ string in $A$ has already occurred, then $w^{th}$ bit of $m$ is set, otherwise its not.

I'll write transitions via forward style dp, if I'm adding the $(i+1)^{th}$ character, then, it might "complete" some substrings, by this I mean, some suffix which was a proper prefix of some string in $A$ before adding character will now be a complete string belonging to set $A$. Note that all such strings will be the suffix of that longest suffix.

So, some new bits in mask $m$ will be set, All this can be calculated, since we already know the longest suffix, in fact lets precalculate, $info[i][j][k]$ which gives a tuple $(bitmask, L, idx)$. If we consider the prefix of length $j$ of $i^{th}$ string in set $A$ and add character $k$ at the end, $w^{th}$ bit in bitmask is set iff, entire $w^{th}$ string in $A$ occurs as a substring in that prefix after adding character $k$, $L$ denotes the length of the longest suffix in resulting string (after adding character $k$) that is a proper prefix of $idx^{th}$ string in set $A$, this precomputation can be done naively in $O(N*C*Z*N)$.

So, after adding $(i+1)^{th}$ character (denote it by $c$), new mask is $(m | info[j][i-k+1][c][0])$, new length of longest suffix is $info[j][i-k+1][c][1]$ so, add its contribution towards state $dp[i+1][info[j][i-k+1][c][2]][i+2-info[j][i-k+1][c][1]][(m | info[j][i-k+1][c][0])]$.

I think the complexity would be $O(C*N*C*2^{N}*Z)$, which might pass. However, I think I'm overkilling it and there has to be simpler solution. I'm not even sure whether my solution is correct or not.

• +14

By ShivanshJ, history, 12 months ago,

I see various solutions involving segment tree, dp etc. I have a simple solution without using these stuffs, also which works for $0\le k \le n$.

If your subarray of size $m$ has $z$ elements to which $x$ is added and thus $m-z$ elements in which $x$ is subtracted then, the sum of subarray will be $s + 2zx - mx$. (Here $s$ is the sum of subarray before doing the operation). Now there are several cases to consider.

If $x \geq 0$. Then we want $2zx$ to be as large as possible, so, there are two further subcases

If $x \geq 0$ and $m \leq k$. Then, we should choose $z = m$. Sum $= s + mx$. To find this over all subarrays, just do the transformation, $a[i] = a[i] + x$ over all $i$, then find the maximum subarray sum in $a$.

If $x \geq 0$ and $m > k$. Then, we should choose $z = k$. Sum $= s + 2kx - mx$. To find this over all subarrays, just do the transformation, $a[i] = a[i] - x$ over all $i$, then find the maximum subarray sum in $a$ plus $2kx$.

If $x < 0$. Then we want $z$ to be as small as possible, so, there are two further subcases

If $x < 0$ and $n-m \leq k$. Then, $z$ has to be $k-n+m$. Sum $= s + 2x(k-n) + mx$. To find this over all subarrays, just do the transformation, $a[i] = a[i] + x$ over all $i$, then find the maximum subarray sum in $a$ plus $2x(k-n)$.

If $x < 0$ and $n-m > k$. Then, we should choose $z = 0$. Sum $= s- mx$. To find this over all subarrays, just do the transformation, $a[i] = a[i] - x$ over all $i$, then find the maximum subarray sum in $a$.

That's it! Its a simple solution. You can use deque for $O(n)$ solution or a multiset for $O(nlogn)$ solution. I hope you guys find it helpful :)

O(n) solution using deque

• +66

By ShivanshJ, history, 13 months ago,

We hope you enjoyed the contest!. Thank you for your participation! Do vote under the Feedback section, and feel free to give your review of the problems in the comments.

Idea: ShivanshJ
Preparation: ShivanshJ
Editorialist: ShivanshJ

Hints
Solution
Implementation (C++)
Implementation (Python)
Feedback

Idea: TimeWarp101 quantau
Preparation: TimeWarp101
Editorialist: TimeWarp101

Hints
Solution
Implementation (C++)
Implementation (Python)
Feedback

Idea: quantau
Preparation: TimeWarp101 quantau
Editorialist: TimeWarp101

Hints
Solution
Implementation (C++)
Feedback

Idea: AwakeAnay
Preparation: mayankfrost ShivanshJ
Editorialist: AwakeAnay

Hints
Solution
Implementation (C++)
Feedback

Idea: Crocuta
Preparation: mayankfrost
Editorialist: mayankfrost

Hints
Solution
Implementation (C++)
Feedback

Idea: Crocuta
Preparation: TimeWarp101
Editorialist: Crocuta

Hints
Solution
Implementation (C++)
Feedback
• +98

By ShivanshJ, history, 14 months ago,

So, I was doing this this problem and noticed the drastic difference between std::pair and std::vector in C++. I preferred to use std::vector over pairs as I don't have to write .first and .second every time.

Submission using std::vector (GETS TLE) View

Submission using std::pair (GETS AC easily) View

What could be the reason behind it?

• +9