Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Clean Explanation of CF Round 901 Div 2 E/1 B
Difference between en3 and en4, changed 561 character(s)
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](https://mirror.codeforces.com/contest/1875/submission/226181502) (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. ↵
   

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English ShivanshJ 2023-10-02 16:25:26 561 Tiny change: 'That's it! ' -> 'That's it!\n\n*Edit* '
en3 English ShivanshJ 2023-10-01 19:49:16 2 Tiny change: 'f size $2^30$), since ' -> 'f size $2^{30}$), since '
en2 English ShivanshJ 2023-10-01 18:56:32 1
en1 English ShivanshJ 2023-10-01 18:55:41 2190 Initial revision (published)