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.
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!
Can u add your code following this explanation?
Sure! I've added my code and explanation.
Auto comment: topic has been updated by ShivanshJ (previous revision, new revision, compare).
Thank you for the detailed explanation of the problem solution!
Thanks for providing the detailed solution. I am a little bit confused about what "state" means here. Can you please clarify? For example, what does the node/state 01001200 mean?