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!

Tags #901, div 2 e, div 1 b, cool problem, interesting problem, bfs


  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)