Connection Status:
Competition Arena > PowerAdapters

PowerAdapters

SRM 393 · 2008-03-11 · by StevieT

SRM 393 · 2008-03-11 · by StevieT · Dynamic Programming, Graph Theory
Class Name: PowerAdapters
Return Type: int
Method Name: needed
Arg Types: (vector<string>, vector<string>, string)
Problem Statement

Problem Statement

Jane is about to go on a round-the-world trip. She is taking her laptop so she can compete in TopCoder competitions while she is away, but she is worred that she may not be able to charge the batteries. The power supply unit for her laptop has a plug suitable for the country that she lives in, but each country that she is visiting on her travels uses a different type of plug for their power outlets. Fortunately she can buy adapters to help her solve the problem. An adapter has a socket of one type, connected to a plug of another type, so she can plug the adapter into the power outlet, then plug her laptop into the adapter. Adapters can also be chained. For example, consider the case where her laptop has a US-style plug, and she has two adapters: one from a US socket to a European plug, and one from a European socket to a UK plug. She can plug her laptop into the first adapter, plug the first adapter into the second one, and then plug that into a UK power outlet to charge her laptop. She has already traveled widely, so might already own some adapters. What is the minimum number of additional adapters she will have to purchase in order to be able to charge her laptop in every country on her itinerary, assuming that she can buy an adapter from any country's socket to any other country's plug.

You are given a String[] adapters containing the details of the adapters that she already owns. Each element details a single adapter and is formatted "<socket> <plug>" (quotes for clarity), where <socket> and <plug> are both strings specifying country names. The adapter accepts a plug of type <socket>, and converts it to a plug of type <plug>. The names of the countries Jane is visiting are given in a String[] itinerary and her home country is given in the String homeCountry. Return the minimum number of additional adapters she needs to buy to be able to charge her computer in every country on her itinerary, given that her laptop plug is of type homeCountry.

Constraints

  • adapters will contain between 0 and 50 elements, inclusive.
  • Each element of adapters will contain between 3 and 50 characters, inclusive.
  • Each element of adapters will be formatted "<socket> <plug>" (quotes for clarity), where <socket> and <plug> are non-empty Strings containing only uppercase letters ('A' - 'Z').
  • In each element of adapters, <socket> and <plug> will be distinct.
  • itinerary will contain between 1 and 16 elements, inclusive.
  • Each element of itinerary will contain between 1 and 50 uppercase letters ('A' - 'Z'), inclusive.
  • Each element of itinerary will be distinct.
  • homeCountry will contain between 1 and 50 uppercase letters ('A' - 'Z'), inclusive.
Examples
0)
{"USA EUROPE","EUROPE UK"}
{"UK","EUROPE"}
"USA"
Returns: 0

The example from the problem statement. Jane is travelling to Europe and the UK and already has enough adapters to charge her laptop everywhere on her journey.

1)
{"A B","C D","E F","G H","I J","K L","M N","O P","Q R","S T","U V","W X","Y Z","AA BB","CC DD","EE FF","GG HH","II JJ","KK LL","MM NN","OO PP","QQ RR","SS TT","UU VV","WW XX","YY ZZ","AAA BBB","CCC DDD","EEE FFF","GGG HHH","III JJJ","KKK LLL","MMM NNN","OOO PPP","QQQ RRR","SSS TTT","UUU VVV","WWW XXX","YYY ZZZ","AAAA BBBB","CCCC DDDD","EEEE FFFF","GGGG HHHH","IIII JJJJ","KKKK LLLL","MMMM NNNN","OOOO PPPP","QQQQ RRRR","SSSS TTTT","UUUU VVVV"}
{"IIIII","AAAB","ABCDEF","GHIJK","FGHL","REWQ","POTYU","SDFKSDF","PVWDF","BNMWE","PHKLJ","CDEFG","RCBMH","PLATE","HITG","PACBN"}
"AAA"
Returns: 16
2)
{"A B","B C","C D","B F","A D","D G","I G","G X","X R","A R","A V","V R","R Z","AA BB","CC DD","EE FF","GG HH","II JJ","KK LL","MM NN","OO PP","QQ RR","SS TT","UU VV","WW XX","YY ZZ","AAA BBB","CCC DDD","EEE FFF","GGG HHH","III JJJ","KKK LLL","MMM NNN","OOO PPP","QQQ RRR","SSS TTT","UUU VVV","WWW XXX","YYY ZZZ","AAAA BBBB","CCCC DDDD","EEEE FFFF","GGGG HHHH","IIII JJJJ","KKKK LLLL","MMMM NNNN","OOOO PPPP","QQQQ RRRR","SSSS TTTT","UUUU VVVV"}
{"A","R","G","B","C","Z","BBB","FFF"}
"AAA"
Returns: 2
3)
{"UK CANADA","BRAZIL EGYPT","EGYPT JAPAN","USA BRAZIL","EGYPT GERMANY","JAPAN EGYPT","USA EGYPT"}
{"GERMANY","USA"}
"UK"
Returns: 1
4)
{"USA CANADA","USA UK","GERMANY AUSTRALIA","GERMANY CANADA","AUSTRALIA USA","UK CANADA","JAPAN USA","JAPAN USA"}
{"AUSTRALIA","CANADA"}
"UK"
Returns: 1
6)
{"INDIA EGYPT","USA GERMANY","CHINA SPAIN","GERMANY NETHERLANDS","NETHERLANDS CHINA"}
{"CHINA","GERMANY","SPAIN"}
"NETHERLANDS"
Returns: 1

Jane already has an adapter for China and she can chain two together (Netherlands-China and China-Spain) to charge her laptop in Spain, so she only needs 1 additional adapter for Germany.

7)
{"AUSTRALIA GERMANY","CANADA INDIA","AUSTRALIA USA","USA INDIA","USA AUSTRALIA","CANADA GERMANY","USA AUSTRALIA","USA CANADA"}
{"AUSTRALIA","CANADA"}
"CANADA"
Returns: 1

Jane's home country can be on her itinerary.

12)
{"SPAIN AUSTRALIA","SPAIN NETHERLANDS","AUSTRALIA EGYPT"}
{"AUSTRALIA","EGYPT","NETHERLANDS"}
"UK"
Returns: 1

Jane needs to buy a UK-Spain adapter.

Submissions are judged against all 90 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PowerAdapters with a public method int needed(vector<string> adapters, vector<string> itinerary, string homeCountry) · 90 test cases · 2 s / 256 MB per case

Submitting as anonymous