Clean Explanation of CF Round 901 Div 2 E/1 B

Revision en3, by ShivanshJ, 2023-10-01 19:49:16

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$ 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!

#### History

Revisions

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