### ShivanshJ's blog

By ShivanshJ, history, 2 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. #901, Comments (13)
 » 2 months ago, # | ← Rev. 2 →   Div1C isn't explained, either. I wrote my soln here I can write for Div1D, but it isn't much. I came up with the formulas by writing them down on paper, and then it's just idk divide and conquer DP should be able to optimize this.
 » No need to run a multisource BFS, because we have 256 different initial states a0,a1...a255, and for each node x can be reached by at most one initial state. So BFS 256 times is also correct in complexity.
•  » » There is no need, but implementation-wise it doesn't add any complexity.
 » " If we construct a directed graph, then it has 5^8 nodes and 4∗5^8 edges "Should not number of edges be 8*4*5^8? For each bit of each node we have 4 outgoing edges and it has 8 bits. So edges = 8*4*5^8.
•  » » He is considering an edge from a whole number to some other number. He is not making graphs bitwise, bits are used just to find out the next number possible.
•  » » » Ok. Thank you
 » Very nice explanation. Thank you so much. May got bless you with beautiful gf.
•  » » Welcome! I am hoping that I get a beautiful GF very very soon!