AND Reachability DP Problem

#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

#21

Bhaiya, go[N][25] 2D DP bana ne ke lea, hum ne bas array elements ka istamal kiya hai. Yah X,Y peh dependent nhi hai, I believe.

#22

ha query ka go table banane mein koi role nahi hai.

first hum go table banate hai and then using that table hum query ka answer dete hain

#23

Bhaiya, iss hisab se go[1][1]=3 hona chahiye? Magr, mera go[1][1]=1 aa rha hai.

#24

yeah its correct… . . .

#25

ha . . . . . … . . ./ . . . .

#26

Thik hai, aur ek baar dry run krke batate hai…
Bhaiya, yah last[25] kya bata rha hai?

#27

last[j] = last index that we encountered whose jth bit was ON (while iterating from n-1 to 0).

bro wo 1 hi hoga its <=.

#28

is answer tumhara 0 aana chaiye,kynki 0th bit already set hai a[0] ki.

#29

Ha bhaiya, go[0][0]=0 hoga. kyun ki, go[i][j]=i hai when i=0,j=0

#30

no not always.
go[i][j]=i only when jth bit of a[i] is set otherwise it will be > i

#31

Ha bhaiya, ek if() condition bhi hai j-loop ke andar so

Bhaiya, yah kese bol diye directly…bataye thoda…

#32

a[0] 1 hai right?
1 -> 00001 (binary)
0th bit 1 which is set.
isiliye
go[0][0]=0

#33

Accha…tab isse yah bol sakte hai ki agar kisi bhi elements ka koi bhi bit set ho then uska
go[i][j]=i hi hoga…

#34

ha. . . . … . . . . .