ASSIGN - Assignments


Problem

Your task will be to calculate number of different assignments of n different topics to n students such that everybody gets exactly one topic he likes.

Input

First line of input contains number of test cases c (1<=c<=80). Each test case begins with 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

For each test case output number of different assignments (it will fit in a signed 64-bit integer).

Example

Input:
3
3
1 1 1
1 1 1
1 1 1
11
1 0 0 1 0 0 0 0 0 1 1 
1 1 1 1 1 0 1 0 1 0 0 
1 0 0 1 0 0 1 1 0 1 0 
1 0 1 1 1 0 1 1 0 1 1 
0 1 1 1 0 1 0 0 1 1 1 
1 1 1 0 0 1 0 0 0 0 0 
0 0 0 0 1 0 1 0 0 0 1 
1 0 1 1 0 0 0 0 0 0 1 
0 0 1 0 1 1 0 0 0 1 1 
1 1 1 0 0 0 1 0 1 0 1 
1 0 0 0 1 1 1 1 0 0 0 
11
0 1 1 1 0 1 0 0 0 1 0 
0 0 1 1 1 1 1 1 1 1 1 
1 1 0 1 0 0 0 0 0 1 0 
0 1 0 1 0 1 0 1 0 1 1 
1 0 0 1 0 0 0 0 1 0 1 
0 0 1 0 1 1 0 0 0 0 1 
1 0 1 0 1 1 1 0 1 1 0 
1 0 1 1 0 1 1 0 0 1 0 
0 0 1 1 0 1 1 1 1 1 1 
0 1 0 0 0 0 0 0 0 1 1 
0 1 1 0 0 0 0 0 1 0 1 

Output:
6
7588
7426


hide comments
vishesh197: 2017-09-23 08:41:59

first google what is bitmask and then solve the question.Logic is same involving recursion and dp but it has to be implemented with bitsmask to reduce time to O(n*2^n).

nessaa_05: 2017-07-23 12:16:27

can anyone please explain the question

namitp: 2017-07-07 22:23:55

Nice Question.....
Learnt a lot....

sharif ullah: 2017-06-15 20:22:52

Need Hints???
follow these step->
step-1: First try to solve this problem using all possible option ,recursion;
step-2: draw the tree in paper,for 1st test case,
step-3:Observe there will happen overlapping,so DP!!!
step-4:Now!! what is state?? at frist there may be 2 sate dp(student no,bitmask/track which topics u choose till now);
step-5: Now!! again see at tree diagram #student =no of 1 in bitmask;
step-6:So state will only bitmask;
step-7:WA answer??
step-8:Use long long .

Last edit: 2017-06-15 20:25:08
da_201501181: 2017-06-09 07:16:07

Worth solving to learn something new in world of DP..!!

leafbebop: 2017-06-07 09:00:33

I made a heavy test with 80*20*all-one on my laptop, it was 2.921 seconds but I got AC with 0.92 seconds.

akash619j: 2017-05-30 11:30:37

Declared int instead of long long int costed me 1 WA!

akshayvenkat: 2017-05-09 02:58:21

Explanation of first test case :

Sx denotes Student X , Tx denotes topic Y

Way 1 : S1 T1 , S2 T2 , S3 T3
Way 2 : S1 T1 , S2 T3 , S3 T2
Way 3 : S1 T2 , S2 T1 , S3 T3
Way 4 : S1 T2 , S2 T3 , S3 T1
Way 5 : S1 T3 , S2 T1 , S3 T2
Way 6 : S1 T3 , S2 T2 , S3 T1

(i.e., in Way 5 , Student 1 is assigned topic 3 , Student 2 is assigned topic 1 , and Student 3 is assigned topic 2)

Note that for the following input :

3
1 0 0
1 0 0
1 0 0

The output is 0. Since student 1 can only take topic 1 , he takes that, and no other student can choose any topic, since they either dont like it (or) their preferred topic(s) has been already chosen by some other student.

A great DP+Bitmask problem for beginners.

Khairo21: 2017-04-03 23:06:45

using printf("%I6d") get WA -_-
but AC in cout :D

deadpool_18: 2017-03-29 10:10:34

explain the test case please!

Last edit: 2017-03-29 13:24:03

Added by:gawry
Date:2005-10-08
Time limit:2.997s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET