AND Reachability DP Problem

#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. . . . … . . . . .

#35

Aur I believe, yhi main logic hai go[N][25] table ko fill up karne ka aur iske wajah se hum ne last[25] ka help liya hai.

#36

ha reachablity ka yahi main logic hai.

#37

Bhaiya, b se {c,d,e,f,g,h} reach agar kar bhi rhe hai, tab bhi jo dp[i][j] ka array hai usse pata nahi chalega… kyun ki, index b meh agar koi bhi bit set hai, toh woh b hi fill karega har ek set bit ke ghar meh in dp[i][j] array ya go[i][j]…

#38

bro , this was idea behind the solution .

#39

tell me about its answer

dp[i][j] = ?
if jth bit is not set in a[i]. (this is crucial point of the solution)

#40

INT_MAX ya n…dono same hai

Iss code meh, humne n-1 se suru kiya hai and at first, all the table filled up by n so answer will be n