Connection Status:
Competition Arena > EllysWordCoins

EllysWordCoins

TCO17 Round 1C · 2017-03-31 · by espr1t

TCO17 Round 1C · 2017-03-31 · by espr1t · Graph Theory, Simple Math
Class Name: EllysWordCoins
Return Type: int
Method Name: getCost
Arg Types: (vector<string>, string, string)
Problem Statement

Problem Statement

Elly has already traded BitCoins, LiteCoins, DogeCoins, and many other cryptocurrencies. However, now she has invested in a promising new currency: WordCoins. In contrast to the other currencies, each WordCoin is actually a nonempty word that consists of uppercase English letters.

Each character has a value in dollars: 'A' is worth 1 dollar, 'B' is worth 2 dollars, and so on until 'Z' which is worth 26 dollars. There is also a special character '_' (underscore). This character does not appear in WordCoins and it is worth 0 dollars.

If the owner of a word L wants to trade it for another word R, the following happens:
  1. If one of the words is shorter than the other, the owner of the shorter word temporarily appends underscores to the end of their word until both words have the same length.
  2. For each valid index i, they calculate the difference between the value of R[i] and L[i].
  3. The sum of those differences is the difference between the values of those words. The person with a less valuable word pays the difference (in real dollars) to the other person.
  4. If any underscores were added in step 1, they are now removed.
  5. The two people trade their words.
For example, suppose Elly has the WordCoin "ESPRIT" and she wants to trade it for the WordCoin "CGFRVR". The difference between the cost of "CGFRVR" and the cost of "ESPRIT" is (3-5) + (7-19) + (6-16) + (18-18) + (22-9) + (18-20) = -13 dollars. This means that "ESPRIT" is more expensive. In the trade Elly will give "ESPRIT" to the other person, and the other person will give her "CGFRVR" and 13 dollars.
If you have "DEADBEEF" and you want to trade it for "TOPCODER", you will have to pay 64 dollars for the trade.
As another example, suppose we have the WordCoin "CODEFORCES" but we want "TOPCODER" instead. In this case, we will first pad the second string to get "TOPCODER__". Then we will calculate the price difference between "TOPCODER__" and "CODEFORCES": (20-3) + ... + (18-3) + (0-5) + (0-19) = 3. Note that this means that "TOPCODER" is actually more valuable than "CODEFORCES": you will have to pay 3 dollars to make the trade.

You are given a String[] market. Each element of market describes one trade offer on the WordCoin market. Each offer has the form "L R", meaning that if you have the word L, you can trade it to get the word R. (Each trade includes the payment of the price difference.)
You are also given two Strings: S and G. Elly has the string S and she wants to have the string G. In order to get the string G she can make any sequence of zero or more consecutive trades. Determine the cheapest way of obtaining the WordCoin G and return the total (possibly negative) amount the transactions will cost. It is guaranteed that one can obtain G from S with the given transactions.

Notes

  • Each trade offer in market can be executed at most once.

Constraints

  • market will contain between 1 and 1000 elements.
  • Each element of market will contain between 3 and 41 characters, inclusive.
  • Each element of market will be formatted as "W1 W2", where W1 and W2 are two wordcoins.
  • Each wordcoin (including S and G) will contain between 1 and 20 characters, inclusive.
  • Each wordcoin (including S and G) will consist entirely of capital letters of the English alphabet ('A'-'Z').
  • It is guaranteed that the transactions available in market allow converting S to G.
Examples
0)
{"TOPCODER OPEN", "SOURCE CODE", "CHALLENGE POINTS", "POINTS OPEN", "QUAL ROUND",
 "ROUND CHALLENGE", "QUAL FUN", "FUN TOPCODER", "OPEN FINAL", "OPEN SOURCE", "CODE FINAL"}
"QUAL"
"FINAL"
Returns: -9

An optimal solution: Elly should trade QUAL for FUN (receiving $10), then FUN for TOPCODER (paying $55), next she should trade TOPCODER for OPEN (receiving $46), and finally she can exchange "OPEN" for "FINAL" (receiving another $8). The total cost of these trades is (-10) + 55 + (-46) + (-8) = (-9).

1)
{"ESPRIT CGFRVR"}
"ESPRIT"
"CGFRVR"
Returns: -13

One of the examples from the problem statement.

2)
{"I CODE", "CODE THEREFORE", "THEREFORE AM"}
"I"
"AM"
Returns: 5

Not much of a choice here.

3)
{"MONEY PEARS", "MONEY APPLES", "MONEY PLUMS", "MONEY CHERRIES", "MONEY STRAWBERRIES",
 "MONEY BLUEBERRIES", "MONEY GRAPES", "PEARS RAKIQ", "BRANDY NOMNOMNOM", "APPLES JUICE",
 "JUICE NOMNOMNOM", "PLUMS RAKIQ", "JAM NOMNOMNOM", "CHERRIES JAM", "STRAWBERRIES JAM",
 "BLUEBERRIES JAM", "GRAPES WINE", "WINE NOMNOMNOM"}
"MONEY"
"NOMNOMNOM"
Returns: 54

With MONEY we can buy BLUEBERRIES, which we can convert to JAM and finally achieve NOMNOMNOM.

4)
{"ONE ONE", "ONE TWO", "ONE THREE", "ONE FOUR", "ONE FIVE", "ONE SIX",
 "ONE SEVEN", "ONE EIGHT", "ONE NINE", "ONE TEN", "ONE ELEVEN", "ONE TWELVE",
 "TWO TWO", "TWO FOUR", "TWO SIX", "TWO EIGHT", "TWO TEN", "TWO TWELVE",
 "THREE THREE", "THREE SIX", "THREE NINE", "THREE TWELVE", "FOUR FOUR",
 "FOUR EIGHT", "FOUR TWELVE", "FIVE FIVE", "FIVE TEN", "SIX SIX", "SIX TWELVE"}
"ONE"
"TWELVE"
Returns: 53

There are multiple optimal paths here. One of them is ONE->TWO->FOUR->TWELVE.

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

Coding Area

Language: C++17 · define a public class EllysWordCoins with a public method int getCost(vector<string> market, string S, string G) · 105 test cases · 2 s / 256 MB per case

Submitting as anonymous