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
saurav_paul:
2019-05-27 14:23:27
First time got TLE after using recursive 2d memorization DP, next I used 1d DP and got accepted, really a very nice problem for learning bitmasking with DP. |
|
ankityadav:
2019-03-28 12:49:02
NOBODY LOVES THE ASSIGNMENTS
|
|
tarungupta:
2019-03-16 19:26:42
Top-down DP works. Finally got AC after many TLEs. Hint: 1D memoization works. |
|
debsourav33:
2018-10-11 13:41:50
Learn Bitmask DP first.. Use mask to keep track which books have been taken so far. |
|
elliot1:
2018-09-11 01:31:04
for those who solve the problem and come to show off in comments.. "fuck you" |
|
souvikd_pro:
2018-08-19 03:56:20
After this, try: https://www.codechef.com/AUG14/problems/TSHIRTS Last edit: 2018-08-19 03:59:23 |
|
be1035016:
2018-06-29 09:50:51
bitset tle:bitmask ac |
|
s_a_k_s_h_a_m:
2018-06-14 22:22:48
question is quite easy
|
|
ankit1cool:
2018-06-11 13:12:12
My first dp+bitmasking learnt a lot |
|
horizon121:
2018-05-16 17:12:44
My first dp+bitmasking !! Very nice. Learnt alot |
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 |