All Tracks Problem

Ways of Seeing



Ways of Seeing

"The relation between what we see and what we know is never settled. Each evening we see the sun set. We know that the earth is turning away from it. Yet the knowledge, the explanation, never quite fits the sight"
~ John Berger, Ways of Seeing.

At the Smithsonian Museum, the ledger storing information of all the paintings has been stolen.
Larry Daley, the night guard, has to do damage control, or else he'll be fired the next morning!

There are M boxes and N paintings in the museum, each box comprising some non-negative number of paintings. A painting can have more than one copy, so it can be present in more than one box. Each box contains paintings of either the Renaissance Era, or the Neoclassical Era.

There are some 'interesting' paintings in the museum. A painting is 'interesting' if it belongs to both the Renaissance and the Neoclassical Era, indicating that it was probably made during the transition period between the two eras.

For some boxes, you already know which era it belongs to. The museum administration wants to minimize the number of interesting paintings. Larry has to assign an era to the remaining unassigned boxes, such that the number of interesting paintings at the Smithsonian is minimized.

Note that assigning an era to box would assign the era to all the paintings in that box. As a painting can be present in multiple boxes, it can be assigned multiple eras. It is interesting if it is assigned both eras at least once.

Can you help Larry out by minimizing the number of interesting paintings after assigning an era to each unassigned box?

Input Format :

First line contains T, the number of test cases.
First line of each test contains N (number of paintings) and M (number of boxes).
Next line contains M integers, where each integer \( \in \) {\(0, -1, +1\)}\( \)
1 shows that box belongs to Renaissance Era.
1 shows that box belongs to Neoclassical Era.
0 shows that box is unassigned any Era.
Next M lines contain N integers each, where each integer is either 0 or 1.
If \(j'th\) integer in \(i'th\) line \( i.e. contains[i][j] = 1\), it means that \(i'th\) box has a copy of \(j'th\) painting present in it.

Output Format:

Output the minimum number of interesting paintings after assigning eras to all unassigned boxes in a single line for each test case.

Constraints :

\(1 \le T \le 100\)
\(1 \le N \le 100\)
\(1 \le M \le 100\)
\(contains[i][j] \in\) {\(0, 1\)}

Subtasks :

For 5 points, \(M \le 15\)
For \(10\) points, count of unassigned boxes \(\le 1\)
For \(20%\) points, \(N \le 10\)

2 2
-1 0
0 1
1 1
3 4
0 1 0 -1
1 0 1
0 0 1
0 1 1
1 1 0

For first sample, only box 2 is unassigned any era.

If we assign box 2 '1' era, then for each painting, set of assigned eras are:
Painting 1 : Eras {1}
Painting 2 : Eras {1}
Interesting Paintings = {}

If we assign box 2 '1' era, then for each painting, set of assigned eras are:
Painting 1 : Eras {1}
Painting 2 : Eras {\(-1, +1\)}
Interesting Paintings = {Painting 2}

Thus, assigning box 2 as '1' era results in minimum number of interesting paintings.

For second sample, optimal answers is assigning box 1 a '1' era and box 3 a '1' era.
After this, the set of interesting paintings : {Painting 3}.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

May Circuits

View All Notifications