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
rapiram31:
2022-11-28 05:02:24
Iterate through the bits like we do in fenwick tree with dp it works:)
|
|
nayemislamzr:
2022-10-04 04:10:13
dp[20][(1<<20)-1] works Last edit: 2022-10-04 04:10:36 |
|
hv22:
2022-06-05 02:13:37
Cool problem!
|
|
thanos_tapras:
2022-01-18 15:58:58
Nice problem.
|
|
arun_code21:
2021-12-15 13:39:45
how (2^n * n) complexity is accepted, time complexity according to this coming in range 10^9?
|
|
adam____:
2021-08-27 16:51:29
AC in one, the bitmasks are a really big hint
|
|
tropo_sphere:
2021-06-26 16:53:19
Can explain O(2^n*n) complexity approach plz! Mine was O(n*n*2^n) with optimization. |
|
null12_21:
2021-06-08 08:11:50
use row...keep a mask to check which index you have been taken i mean which assignment...mask can use with bit operation. use a for loop between the recursive solution. if you on a position on mask dont forget to off it after the iteration |
|
anupam_akib:
2021-05-22 20:14:11
Finally got AC after 1 TLE and 2 WA. Nice problem for beginners who started solving DP with bitmasks. |
|
saurabh_38:
2021-02-18 10:20:22
use-> unsigned long long
|
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 |