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
dhruvgheewala:
2021-01-30 12:48:33
@brokeboy, my code having similar complexities, but I am getting TLE. Do you have any clue, I am using a 2-d vector and adjacency matrix to store preferences.
|
|
ayushpandia:
2021-01-18 14:36:31
Really nice problem |
|
ant_2001:
2021-01-17 13:11:25
I am using DP+bitmask, long long ......test cases give correct answer but I am still getting WA . Please help! |
|
lamda_cdm_10:
2020-10-28 14:29:05
Nice problem for people who are starting to learn bitmasks... has a tight time limit ... enjoyed solving it. |
|
pranavsindura:
2020-09-05 10:50:20
Both top down and bottom up work. |
|
karankamboj:
2020-06-09 15:14:01
AC when used recursive DP
|
|
regex0754:
2020-05-18 00:08:22
During Bitmasking,I just left shifted all masks so that I can use 1 indexing.But this gives TLE while normal 0
|
|
brokeboy:
2020-05-08 19:55:04
Works with Time = (2^n)*n*n, Space = (2^n)*n, Fast IO |
|
cjchirag7:
2020-05-03 10:20:25
DP with bitmasking with state reduction.
|
|
dmorgans:
2020-02-18 19:14:33
my 51st
|
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 |