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
vaibhavi760:
2016-06-23 06:12:28
took 1 day to solve and finally success nice question to understand bitmasking Last edit: 2016-06-25 18:01:55 |
|
vijay kumar paliwal:
2016-06-02 07:48:19
Here comes my third fifty!! :)
|
|
ajay_5097:
2016-05-25 12:05:12
Question is worth trying !!
|
|
try2catch:
2016-01-22 07:03:39
I'm not getting the question. Can some1 explain test cases?
|
|
:.Mohib.::
2015-11-18 22:06:15
top-down :D ;) |
|
theweblover007:
2015-11-09 08:12:49
After juggling with TLE's for 4 hrs, Attained the enlightenment. Last edit: 2015-11-09 10:22:28 |
|
rahul nagurtha:
2015-10-02 12:34:09
Can someone tell me why am i getting wrong answer instead of TLE ? |
|
Abhilash:
2015-09-24 14:09:33
Topdown gets AC with few optimizations in code. |
|
anando_du:
2015-08-31 16:22:18
Top DOwn ... single submission . AC . DP state is important here .... |
|
Abhinandan Agarwal:
2015-08-30 15:46:20
A good problem indeed! Top down -TLE,
|
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 |