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

Правка en4, от ShivanshJ, 2023-10-02 16:25:26

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, div 2 e, div 1 b, cool problem, interesting problem, bfs

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)