PROBLEM LINK:Setter Hasan Jaddouh DIFFICULTY:SIMPLE PREREQUISITES:2D Arrays, Bitwise Operations, Logical Reasoning. PROBLEM:Given a $2D$ array of size $N\times M$, where elements are either $0$ or $1$. We can apply operation of OR'ING an entire row/column with another. We need to find minimum number of moves to make a particular cell $A_{ij}=1$. This must be done for all cells independently. QUICK EXPLANATION:Key Strategy Deducing that its simple casemaking, along with apt application of data structures is the key to get quick AC here. We know that ans is $1$ only if all elements are $0$. If even $1$ element is $1$, it is possible to make the all other array elements $1$ as well. Obviously, if $A_{ij}=0$ for some $(i,j)$ and there is any cell in same row or column which is $1$, then we can make $A_{ij}=1$ in a single move. Else, it will always take $2$ moves. EXPLANATION:The editorial will have $4$ sections. The first one will discuss when answer is $0$, second when ans is $1$, the next will discuss when answer is $2$ and last one will discuss if answer is $1$. 1. When answer is $0$ $0$ moves signify that no moves are needed to make $A_{ij}=1$. This is possible if and only if $A_{ij}=1$ initially in the input array. This is because, if $A_{ij}=0$, we will need at least $1$ move to make it $1$. 2. When answer is $1$ This is the case if $A_{ij}$ lies in either same row, or same column with another cell $A_{kl}$ such that $A_{kl}=1$. In this case, we can directly apply the given operation to make $A_{ij}=1$. An example illustration is given below 3. When answer is $2$ This section has $2$ parts. The first part is to prove that "If any single element of array is $1$, then its possible to make the entire array $1$." Have an attempt and then look at the hidden box to see the proof details. Look at the proof above in case you didnt. Notice that, we made the target cell $1$ in $2$ operations, and we used no special assumptions  i.e. we talked for any general cells. Hence, $2$ is a upper bound on number of operations. If no special assumptions like above hold, then answer is always $2$. An illustration of above is given in tab below for reference 4. When answer is $1$  Refer to proof in above section. We proved that if at least one cell $A_{ij}=1$, then we can make entire array as $1$. Hence, the answer is $1$. if and only if, there is no element $A_{ij}=1$, i.e. all elements are $0$. Then, we cannot make any cell $1$. SOLUTION:As a convenience to fellow readers, I have also copy pasted the codes in tabs below. Please refer to them while @admin links the solutions to the editorial Thank you :) $Time$ $Complexity=$ $O(N*M)$ (for input). Checking if there is a $1$ in given row or column is checked in $O(1)$ by doing a $O(N*M)$ preprocessing before hand while taking input. CHEF VIJJU'S CORNER :D1. There is an interesting version of problem. Given a $2D$ array, with some $1$ and $0's$ as values of array elements, solve the following
For each of the three questions, either prove that they arent solvable in polynomial time, or give an algorithm which solves them in polynomial time. 2. One major part of this question is checking if there is a $1$ in same row or column. How will you do that? Lets have a look at this idea  "For every cell $(i,j)$ such that $A_{ij}=1$, store $i$ in a vector $rows$ and store $j$ in another vector column. Now, for each cell $(x,y)$ such that $A_{xy}=0$, just binary search if $x$ exists in $rows$ or $y$ exists in $columns$." Is this correct? Is this the best time complexity we can use? Answer these w.r.t. the above idea. (Hint: Refer to setter's solution) 3. Getting a WA? Does your code use
This question is marked "community wiki".
asked 20 Jul '18, 15:29

Video solution with explanation: https://youtu.be/w1cDfrjjU4?t=2m33s answered 23 Jul '18, 00:32

Just changed my solution's 1 output and codechef accepted it as practice. I was sure my solution for Sticks was correct too but couldn't pass it, now let me check what kind simple mistake I made there. answered 23 Jul '18, 00:48

https://ideone.com/VqMNok can anyone provide a test case where my code might be wrong? i am really stuck... answered 23 Jul '18, 08:16

https://www.codechef.com/viewsolution/19311830 Can someone tell me the complexity of my code answered 23 Jul '18, 14:36
Seems $O({N}^{3})$ to me.
(23 Jul '18, 14:59)
Why i got AC ???? I am confused
(23 Jul '18, 16:33)
No big surprise ${10}^{9}$ instructions are possible if all you do is very,very basic operations. Though that doesnt rule out that your code cannot get TLE.
(23 Jul '18, 16:56)
Ok thanx :)
(23 Jul '18, 17:02)

What if I define an array say of dimension 1000X1000 and only arr[0][0]=1 and rest all zero?? how will arr[999][999] be transformed to 1 within 2 steps?? answered 29 Dec '18, 11:52

What if I define an array say of dimension 1000X1000 and only arr[0][0]=1 and rest all zero?? how will arr[999][999] be transformed to 1 within 2 steps?? answered 29 Dec '18, 11:52
