Submit | All submissions | Best solutions | Back to list |
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
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 |
hide comments
|
|||||||||||||
2015-08-18 17:56:19
good one :) |
|||||||||||||
2015-08-05 14:41:28 [Mayank Pratap]
Took hours to understand the concept of Bitmasks + DP. ..........Coding is easier if u get it... :) |
|||||||||||||
2015-08-02 12:46:06 kejriwal
nice problem..!! :) |
|||||||||||||
2015-07-16 14:31:27 xxbloodysantaxx
Took my 8 hours !! I was able to figure out the solution with complexity O(N^2 * 2^N ) but to achieve O(N*2^N) , I dont know dont waste much time on it just see it :P |
|||||||||||||
2015-05-29 15:57:07 sai krishna
Any one please explain this test case,unable to understand 1 5 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1 |
|||||||||||||
2015-02-28 16:01:13 Siddharth
Same algorithm in JAVA gives TLE... :( Wasted a hell lot of time... |
|||||||||||||
2015-02-27 06:41:01 venu gangireddy
awesome problem.... Last edit: 2015-02-27 06:41:39 |
|||||||||||||
2015-02-05 12:15:56 californiagurl
beautiful optimization! it wasn't obvious to me, although i had a hunch that my original solution will not pass. |
|||||||||||||
2015-01-29 07:45:49 ALISHA
there is nothing wrong with memoization. code indeed gets accepted!! time 2.27 sec :P :P |
|||||||||||||
2015-01-22 08:56:42 CoNtRaDiCtIoN
great problem learnt a lot |