AND Reachability DP Problem

#1

I have doubts,
what is dist1to1[25][25] for? and,
what is mindist[N][25] for in this problem?
If anyone did this problem then know what I seek for here…

#2

please share the question name and the code .
i will tell you .

#3

It’s Codeforces 1169E Problem: AND Reachability https://codeforces.com/problemset/problem/1169/E
And I’m watching the video still, haven’t code this problem so far by myself.

#4

please share the link of the video as well

#5

It’s a coding blocks video, it’s a part of the course lecture. How can I share this video?

#6

this is another video for the same problem that I have seen as well for clarity: https://www.youtube.com/watch?v=MB_n50WNQrw&t=330s&ab_channel=Errichto

#7

dist1to1 is the array that we ahve to maintain by calculating and it will tell us about the distance to reach from one particular bit to another bit .

#8

can you give some example… let’s say, if I have numbers: 1, 3, 5 then how can I calculate dist1to1

#9

this is my code for this problem.

#10

hello @Kinjal

bro ur code is working fine.

#11

Bhaiya, yah code likha hai so dry run krne ke lea.
Yah code bahut jada complicated hai.

#12

bro erricto wale approach se karo uska idea kaafi logical hai and code bhi easy to understand hai

#13

Maine bhi observe kiya hai, even codeforces ka editorial meh bhi same approach hai. Magr bhaiya, errichto kya bolta hai samjh hi nhi ata…

#14

let say from b u can reach to positions {c,d,e,f,g,h} ie they have some bits in common .
and if b is reachable from a then we can say from a we can reach {b,c,d,e,f,g,h} right?
this is the whole idea.
and we are using dp to store this info efficiently.

dp[i][j] -> smallest index in right of i(including i) whose jth bit is set.

#15

this is the main logic->
image

let me know if anything is not clear in this.
i will explain

#16

Thik hai bhaiya.
go[N][25] jo 2D DP array humne liya hai, yah kya denote kar rha hai aur iska contribution kya hai iss problem meh?
where N is no of elements in the array and 25 is the max no of bits possible for a number in the array.

#17

IMG_20201111_125415-min
IMG_20201111_125415-min3024×3024 869 KB

Dry run kara hai jo codeforces wale diya hai.

#18

go[i][j] jo hoga wo hame next smallest index >= i batayega jiska j th bit set hai.

#19

go[0][0]=1, after dry run. Iska matlb kya hoga tab?

#20

first of all its test case dependent.
go[0][0]=1 ka matlab hua ki from index 0 , u can go to index 1(smallest) , using 0th bit