Doubt in problem implementation

#1

Problem - https://csacademy.com/contest/archive/task/confused-robot/statement/

Solution - https://csacademy.com/submission/3084050/

I do not understand line 45 in the solution. Why are we considering only the set bits in ‘query’ function?

#2

hello @yuvi2701

basically instead iterating linearly …they are iterating in powers of two simple binary thing.
like if length is 5 then instead of going linearly 1+1+1 + 1+1
we can go like 2^2 + 2^0 (quick and reduced steps)

#3

Thanks for your reply.
In the implementation nxt[k][i][j] is storing position of robot after input string is traversed k times if bot starts from (i,j).

How is traversing the string 5 times same as taking 2 binary steps?

#4

to go 5 mutiple of length . we could have done like nxt[0][i][j] 5 times (i.e linear) right?
or we can do nxt[2^2][i][j] and then next[2^0][i][j] i.e first go next[4][i][j] and then nxt[1][i][j]

in both the cases we will reach to same point but becuase second will be fast we are using it

#5

Got it
Thank you so much!

#6

Oh no
It is not going to next[4][i][j] and then nxt[1][i][j] for nxt[5][i][j].
It is going nxt[0][i][j] and nxt[2][i][j], just the set bits in binary(5).

#7

the dp table that they have prepared is this

dp[k][i][j] = final state after 2^k multiple of length when starting from (i,j).

if u have studied binary lifting or sparse table then u will get this . same logic is applied there.

2^k = 2^k-1 + 2^k-1 (something like this)

#8

this was for ur understanding.

here in actual it should be nxt[2]+nxt[0] -> 2^2 + 2^0

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.