You are not logged in. Please login at www.codechef.com to post your questions!

×

THE SORTING HAT ALGORITHM please...

The Sorting Hat Dripping wet after the boat ride across the lake owing to a few minor mishaps, (the Squid was a light sleeper), the little witches and wizards have arrived safe and sound at the castle of Hogwarts. They are ushered into the Great Hall by Professor McGonagall, and they are about to be sorted into houses by the Sorting Hat. Over the years, the Sorting Hat has mastered a technique that it follows while sorting the children into houses. It first considers the child’s own preference, and will not allot any little witch or wizard a house it does not want to be part of. Additionally, the Hat understands that the total maintenance costs of the houses must be reduced as much as possible (the rent being too damn high). The maintenance cost of any house i is equal to ni (ni + 1) / 2, where ni is the number of students in house i. Simply put, the hat seeks to minimize the total cost incurred by all the houses together, while also respecting each individual child’s wishes. What is the minimum possible total maintenance cost that can be achieved if the sorting hat classifies the children optimally? Input Format The first line contains integer t<=5, the number of test cases. It is followed by t test cases. The first line of each test case contains 2 space separated integers n and m - the number of children and the number of houses respectively (n>=m). The second line contains an integer e, denoting the total number of choices given by all students. Then e lines follow, each containing 2 space separated integers i and j, implying that house j is acceptable to the ith child. Note: The children and the houses are numbered 1…n and 1…m respectively. Output Format For each test case, output a single integer, which represents the minimum possible maintenance cost of the houses. Constraints n <= 250 e <= 1000 Sample Input 2 6 3 15 1 2 2 2 3 1 4 2 5 3 6 2 2 1 2 3 1 1 5 2 3 3 4 1 1 3 4 3 6 1 5 5 20 1 4 2 2 3 3 4 1 5 4 2 1 5 3 3 2 1 3 4 5 1 2 3 4 3 5 3 1 5 1 4 3 2 4 5 5 1 5 2 3 Sample Output 95 Explanation for the 1st test case: The choices of a child for certain houses are represented by the edges. Blue coloured edge represents the assignment of a child to a house. Here, child 1 is assigned to House 2; child 2 is assigned to House 1 and so on. Total Cost = Cost (House 1) + Cost (House 2) + Cost (House 3) = (23)/2 + (23)/2 + (2*3)/2 = 9 2nd Test case – every house gets 1 child since every child likes all houses. So the Cost is 1 for each house. Total cost = 1 + 1 + 1 + 1 + 1 = 5

asked 01 Mar '13, 23:12

harsh1_5's gravatar image

0★harsh1_5
1111
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×801

question asked: 01 Mar '13, 23:12

question was seen: 2,438 times

last updated: 01 Mar '13, 23:12