ShivanshJ's blog

By ShivanshJ, history, 5 months ago, In English

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.

  • Vote: I like it
  • +119
  • Vote: I do not like it

»
5 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    There is no need, but implementation-wise it doesn't add any complexity.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

" 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very nice explanation. Thank you so much. May got bless you with beautiful gf.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Welcome! I am hoping that I get a beautiful GF very very soon!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can u add your code following this explanation?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ShivanshJ (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Thank you for the detailed explanation of the problem solution!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?