1
$\begingroup$

I am trying to solve this problem: https://www.codechef.com/problems/TSHIRTS

Little Elephant and his friends are going to a party. Each person has his own collection of T-Shirts. There are 100 different kind of T-Shirts. Each T-Shirt has a unique id between 1 and 100. No person has two T-Shirts of the same ID.

They want to know how many arrangements are there in which no two persons wear same T-Shirt. One arrangement is considered different from another arrangement if there is at least one person wearing a different kind of T-Shirt in another arrangement.

Input First line of the input contains a single integer T denoting number of test cases. Then T test cases follow.

For each test case, first line contains an integer N, denoting the total number of persons. Each of the next N lines contains at least 1 and at most 100 space separated distinct integers, denoting the ID's of the T-Shirts ith person has.

If there are no duplicates, then we can multiply out the number of t-shirts every person has.

I'm struggling to arrive at a solution for when there are duplicates.

A quick peek at the problem tag indicates that a dynamic programming solution is also possible.

I'd love some pointers on how to approach this problem.

Thanks!

$\endgroup$
2
  • $\begingroup$ This will depend on the number of people available and the collection of shirts that each individual has available to wear. There will be at most $100!$ arrangements and at least $0$ arrangements. As for how to efficiently check this... perhaps try looping over the people one at a time, picking one of the available shirts for each which haven't yet appeared, and if no valid choice is available then continue. It seems brute-forcish, and some improvements can surely be made, but it would work. $\endgroup$
    – JMoravitz
    Commented Dec 18, 2019 at 0:05
  • $\begingroup$ @JMoravitz This is quite brute-forcish. The OP is asking for a DP solution so as to prevent the recalculation. $\endgroup$
    – asn
    Commented Apr 8, 2020 at 7:28

0

You must log in to answer this question.

Browse other questions tagged .