You are not logged in. Please login at www.codechef.com to post your questions!

×

ORMATRIX- Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Hasan Jaddouh
Tester- Ivan Safonov
Editorialist- Abhishek Pandey

DIFFICULTY:

SIMPLE

PRE-REQUISITES:

2-D Arrays, Bitwise Operations, Logical Reasoning.

PROBLEM:

Given a $2-D$ 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 case-making, 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-

View Content

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.

View Content

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-

View Content

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 :)

Setter

View Content

Tester

View Content

$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)$ pre-processing before hand while taking input.

CHEF VIJJU'S CORNER :D

1. There is an interesting version of problem. Given a $2-D$ array, with some $1$ and $0's$ as values of array elements, solve the following-

  • Find the row with maximum $1's$ given that all $1's$ lie before all $0's$.
  • Find row with minimum $1's$ if all $0's$ like before all $1's$.
  • Given any general array, find minimum number of moves to make any row OR column all $1$.

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 int arr[n][m]={}; anywhere? Its UNDEFINED BEHAVIOUR and causes your code to print garbage values to judge when submitting. Specify the dimensions of an array as a number only!!

This question is marked "community wiki".

asked 20 Jul '18, 15:29

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 24 Jul '18, 23:13


Video solution with explanation: https://youtu.be/w1cDf-rjjU4?t=2m33s

link

answered 23 Jul '18, 00:32

code_report's gravatar image

3★code_report
3305
accept rate: 0%

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.

link

answered 23 Jul '18, 00:48

tieros's gravatar image

4★tieros
734
accept rate: 12%

All the best :)

(23 Jul '18, 02:11) vijju123 ♦♦5★

https://ideone.com/VqMNok can anyone provide a test case where my code might be wrong? i am really stuck...

link

answered 23 Jul '18, 08:16

jaizzz's gravatar image

4★jaizzz
111
accept rate: 0%

got it....

(23 Jul '18, 09:25) jaizzz4★

https://www.codechef.com/viewsolution/19311830 Can someone tell me the complexity of my code

link

answered 23 Jul '18, 14:36

adityaseth1011's gravatar image

4★adityaseth1011
32
accept rate: 0%

Seems $O({N}^{3})$ to me.

(23 Jul '18, 14:59) vijju123 ♦♦5★

Why i got AC ???? I am confused

(23 Jul '18, 16:33) adityaseth10114★

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) vijju123 ♦♦5★

Ok thanx :)

(23 Jul '18, 17:02) adityaseth10114★

I am not sure why my one solution gets AC while other got WA...any help is appreciated

AC Solution

WA Solution

link

answered 24 Jul '18, 22:52

thesmartguy's gravatar image

4★thesmartguy
786
accept rate: 8%

int ans[n][m] = {};

This is UNDEFINED BEHAVIOUR and causes runtime error. You cannot initialize arrays like this if $n$ and $m$ are variables. You can do this only with constants.

(24 Jul '18, 23:11) vijju123 ♦♦5★

thanks, got it now :))

(26 Jul '18, 12:20) thesmartguy4★

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??

link

answered 29 Dec '18, 11:52

whyamievenhere's gravatar image

4★whyamievenhere
0
accept rate: 0%

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??

link

answered 29 Dec '18, 11:52

whyamievenhere's gravatar image

4★whyamievenhere
0
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,173
×847
×834
×96

question asked: 20 Jul '18, 15:29

question was seen: 1,704 times

last updated: 29 Dec '18, 11:52