Monitoring Madness

Problem code: MMADNESS

All submissions for this problem are available.

At Directi, we have many machines connected to each other since we host many web-sites. However, administering these machines is a great hassle. That is because a machine can be administered only by a machine connected directly to it (a machine that is an administrator can administrator itself). So, the system administrators have decided to convert some of the machines in the network to "administrative machines". However, the cost of converting a machine to an administrative machine is $100, which is pretty high. So, the system administrators approach you to help them out.

You will be given a list of machines which have a direct connection between them. You need to compute the least cost that the company needs to incur so that every machine in the final network is administrable by at least one of the machines converted to administrative machines.

Input

The first line of input will contain an integer 't', the number of test cases (1 t 100). Each test case starts with a blank line followed by an integer 'n' which specifies the number of connections between machines (0 n 100). Each of the 'n' lines that follows contains a pair of upper-case characters between A and Z that are separated by a space. Each distinct character represents a machine.

Output

For each test case, your output should contain the least amount of money in dollars that you need to spend so that every machine in the network is administered by at least one administrator machine.

Example

Input:
1

4
A B
A C
B E
B D

Output:
200

Explanation: In this case, the least cost you have to incur is $200 and it can be achieved by converting machines A and B to administrative machines.

The diagrammatic representation for the example test case above:

Date: 2009-05-29
Time limit: 40s
Source limit: 50000
Languages: C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp HASK CAML CLPS PRLG WSPC BF ICK


Comments

supercharger @ 22 Jun 2009 05:22 AM

Admin, can you list one or two more test cases?

sagar_jhobalia @ 22 Jun 2009 04:58 PM

m gettin an error wid d name of the class....wats d problem...

supercharger @ 23 Jun 2009 02:25 AM

make class as Main

i0exception @ 24 Jun 2009 01:42 AM

1
7
A C
C D
X E
E G
G A
B D
H I

should give the answer as 400

skp @ 24 Jun 2009 02:25 AM

I got some three test cases (including one by Aniruddha above) and it seems fine with them, but seems to get wrong answer when submitted. ! any chance of a closure .. multiple test cases are output-ed one per line.

sush @ 26 Jun 2009 05:21 AM

srsly can anyone suggest a tricky test case??

sush @ 26 Jun 2009 06:42 AM

for n=0 output is 0
still wrong answer !!!

i0exception @ 26 Jun 2009 05:23 PM

You need to think of corner cases. Have you thought of what would happen if you have distinct clusters of machines? Are you taking care of that?

ankur_vjy @ 27 Jun 2009 11:43 PM

Cumon, there has to be some way to find out where i am going wrong ?? i cant keep on searching for corner test cases ?

vids @ 7 Jul 2009 09:16 PM

A very trivial doubt but it will bug my code bad..
will all the sample test cases have first n alphabets as in A,B,C...
as nodes or they may also have
A,B,X as nodes

admin 2 @ 7 Jul 2009 09:27 PM

The nodes can be any arbitrary alphabets between A and Z.

arbitlinks @ 21 Jul 2009 03:12 AM

If i have multiple test cases ,then how should be the output as in.
1 test case followed by its output , or i take in all the test cases and then give all outputs together.
I have the right answer(as do many) but cannot seem to impress online judge.

admin 2 @ 21 Jul 2009 03:33 AM

@arbitlinks Read the FAQ at http://blog.codechef.com/2009/06/29/frequently-asked-questions/ Your question has already been answered there.

arbitlinks @ 22 Jul 2009 03:40 AM

@DirectiAdmin..
thanks fr the quick response...
but the online judge is not accepting the solution i have presented..
anyhw will move to a new problem...

varun2004singh @ 23 Jul 2009 06:42 PM

I think i am getting the right result but don't know why ,codechef is saying your result is wrong.
Can anybody provide me some more test cases?
Test cases:-1 7 A C C D X E E G G A B D H I the answer is 400
Test Cases:-1 4 A B A C B C A D the answer is 100
Test Case :-1 5 A B A C B E B D C D the answer is 200
Can anybody check and tell me if i am wrong.

arbitlinks @ 23 Jul 2009 09:24 PM

@Varun Singh .. same here bro...
have given up though...

atulbansal128 @ 24 Jul 2009 06:25 AM

This problem seems to be NP-hard

atulbansal128 @ 24 Jul 2009 06:27 AM

What should be the answer when n=0. I think 0 is correct?

varun2004singh @ 24 Jul 2009 07:48 AM

@Atul
The answer should be zero for n=0.

admin 2 @ 24 Jul 2009 05:51 PM

@atul No, it is not NP-hard. It is similar to another problem which is NP hard, but it is not the same as that one.

manish_bansal @ 12 Aug 2009 07:14 AM

Hey wat compiler u guys are using...
For the same solution first i got compiler error then wrong answer...
Looks like sumthing wrong??? Even when it says compiler error the error log that i got had nuthing..

blablub @ 17 Aug 2009 08:40 AM

I used the following algorithm: Sort all nodes of the graph(which represents the network) by their degree in descending order. Then, adding one node after an other until all machines can be administrated. However, I get an error - is my algorithm in itself incorrect or should I look after details? thx in advance.

triplem @ 17 Aug 2009 12:37 PM

Can you prove that algorithm will always give the optimal answer? If not, perhaps you should try something else.

blablub @ 17 Aug 2009 06:15 PM

I've found out, that the algorithm is wrong. The key is not to sort all nodes by their degree, but rather by the number of machines that become accessible, when one declares a node as administrator.

admin 2 @ 17 Aug 2009 06:26 PM

See the sample solutions in the help section. You need an int main() and a return 0; at the end of it. Also, read the previous comment. Don't print something like "enter a number"

@blablub -greedy approach

pegasus @ 20 Aug 2009 11:11 PM
@blablub -greedy approach won't work in this case. I took an example (>10 nodes) and tried on paper with greedy approach .Wont work.

@admin:: can you provide few

akmnitt @ 21 Aug 2009 04:27 PM
@admin:: can you provide few more inputs .

There already a lot of test

admin @ 21 Aug 2009 04:59 PM

There already a lot of test cases posted here. You can try creating random test cases of small size and verify your answer by using a bruteforce approach on these.

@admin >>Can input have same

akmnitt @ 21 Aug 2009 05:52 PM
@admin >>Can input have same node in connection A A B B like ..

Can someone provide any

akmnitt @ 21 Aug 2009 05:56 PM
Can someone provide any tricky input... In my coding I took care of disconnected node and individual nodes but online compiler is saying wrong answer every time.

From the problem statement

admin @ 21 Aug 2009 06:26 PM

From the problem statement -> (a machine that is an administrator can administrator itself).

Is the judge known to face

lonewolf @ 4 Sep 2009 02:45 PM

Is the judge known to face problems if I use sys.stdin in python code?

No.

admin @ 4 Sep 2009 04:55 PM

No.

Hi,   Please tell the

vaibhavgupta_iitd @ 4 Sep 2009 06:12 PM

Hi,

 

Please tell the mechanism for taking inputs in java. I have submitted three quizzes so far. And all of them ended up in error. I have tested for many conditions and they work fine in my system. It would be helpful if codeChef could tell that the input shown in the example executed correctly but it failed in other cases. This will give a reference that it's not I/O issues or JVM issues. 

Take a look at

admin @ 4 Sep 2009 06:56 PM

Take a look at www.codechef.com/help for a sample solution in java .

 Guys i have given

manish_bansal @ 5 Sep 2009 11:05 AM

 Guys i have given up..

Programe works awesome for all the cases mentioned above and few more i used.

Not sure why i am always getting wrong answere here...

You get wrong answer here

triplem @ 5 Sep 2009 01:49 PM

You get wrong answer here because your program is printing out the wrong answer :P You'll just have to keep looking for mistakes in your code. I guarantee you there will be one.


Admin, the result for my prog

Krish_ @ 8 Sep 2009 08:54 PM

Admin, the result for my prog is shown as Runtime error SIGSEG in this screen and shows  Runtime error OTHER in the my submissons screen and shows NZEC in the mail i received... so wat exactly is it??

It is the first one, SIGSEGV.

admin @ 9 Sep 2009 02:13 PM

It is the first one, SIGSEGV.

i am getting compilation

kevindra @ 8 Oct 2009 05:07 PM

i am getting compilation error.. does the compiler support STL "pair"?

Yes it does.

admin @ 8 Oct 2009 05:11 PM

Yes it does.

my code is running correctly

kevindra @ 8 Oct 2009 05:38 PM

my code is running correctly in MS visual studio 2005 correctly. Here it shows compilation prob. What can be the problem?

if you have something like

admin @ 8 Oct 2009 05:47 PM

if you have something like vector<vector<int>> change it to vector<vector<int> >. Notice the extra space between '>>'. Codechef uses the GNU compiler collection. You might want to download gcc or a port of it to run on your machine.

can i see here where is it

kevindra @ 8 Oct 2009 05:50 PM

can i see here where is it getting compilation error?

thnx... that was the only

kevindra @ 8 Oct 2009 06:28 PM

thnx... that was the only prob. got AC. :)

where can I see the compile

paloflat @ 21 Oct 2009 10:48 PM

where can I see the compile error? The yellow triangle is not clickable..

 

Thank you!

Does the problem has got

sppraveen @ 20 Mar 2010 02:19 PM

Does the problem has got something to do with DP

is this a graph colouring

Myth17 @ 15 Feb 2011 06:12 PM

is this a graph colouring variant?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions