All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Sir scolded Rishu

Bitmask, Dynamic programming, Medium


Umesh Sir was busy in assigning tasks to the students in the class, but he gets irritated because of the murmuring sound being caused by some students. And meanwhile, he caught Rishu talking to some other guy. Now, Umesh Sir scolded Rishu and told him that he will make sure that Rishu will get detained by the end of the semester if he will not complete the given task. Although Rishu is too good at algorithms, he was not able to complete the task because he got nervous. Help Rishu otherwise he will get detained.

The task will be: There are n students in the class and Sir chose n topics to give tasks. You have to calculate the number of different ways to assign n different topics to n students such that everybody gets exactly one topic he likes.

Input Format:

The first line of input contains the number of test cases T (1<=T<=80). Each test case begins with the number of students n (1<=n<=20). Each of the next n lines contains n integers describing preferences of one student. 1 at the ith position means that this student likes ith topic, 0 means that he definitely doesn't want to take it.

Output Format:

For each test case output number of different assignments.

1 1 1
1 1 1
1 1 1
Time Limit: 0,5 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:


View All Notifications