Statistics

Problem Statement for "Antidote"

Problem Statement

One of your best friends is a master chemist and pharmacist, and one day he presents you with an interesting dare. He has concocted a series of interesting drinks, with fake names to confuse their true identity. Some of the drinks are slightly poisonous: they will make you sick if you drink them. Some of the drinks will make you sick if you drink them in immediate succession with another drink. He presents you with a line of drinks with their fake names, and a cheat sheet that tells you the properties of each drink that might make you sick (in other words, any drink or drink combination will not make you sick unless it is on the cheat sheet). He then starts a clock, giving you one minute for each drink he has lined up. Every minute you'll be given the choice to drink the drink you are at, or pass it up, and then move on to the next drink. Your goal is to drink as many drinks as you can in this fashion without getting sick. If there is more than one way to drink the same number of drinks, you would prefer the plan where you drink earlier. In other words if two plans involve drinking the same number of drinks, and the plans are identical up to the ith drink, but differ at the ith drink, you should choose the plan that involves drinking the ith drink. See example 0.

The list can contain one of two types of rules:

  • "BAD:<drinkA>" means that <drinkA> is poisonous.
  • "BAD:<drinkA>+<drinkB>" means that <drinkA> becomes poisonous if followed immediately by <drinkB>.
This is how to use the cheat-sheet to determine if a drink is safe:

First, assume that you have a canditate plan of which drinks you plan on drinking and which drinks you plan on passing. To determine if the plan is safe, check each drink that you plan on drinking. If a drink that you are planning on drinking, <drinkA> is on the cheat sheet as "BAD:<drinkA>", then the canditate plan is not safe, and will make you sick. Next, if you plan on drinking some drink, <drinkA>, and plan to immediately following it with <drinkB>, and "BAD:<drinkA>+<drinkB>" is on the cheat sheet, then that plan is not safe, and will make you sick. Note that if your cheat sheet contains a rule "BAD:<drinkA>+<drinkB>", you may still drink <drinkA>, then pass your next drink, and then drink <drinkB>.

Your program will take in a String[] of every rule on the cheat sheet(rules) and and a String[] of the list and order of the drinks that your friend has set up for you(drinks). Your program will return a String[] all of whose elements are "DRINK" and "PASS" that indicate what you should do with each drink in order to succeed in your friend's dare.

Definition

Class:
Antidote
Method:
safeDrinks
Parameters:
String[], String[]
Returns:
String[]
Method signature:
String[] safeDrinks(String[] rules, String[] drinks)
(be sure your method is public)

Notes

  • All elements of rules and drinks are case-sensitive.
  • Anything not expressly said to make you sick by rules, is safe.
  • Rules may be repeated.

Constraints

  • rules will contain between 0 and 20 elements, inclusive.
  • Each element of rules will be between 1 and 50 characters long inclusive, and all will consist of lowercase/uppercase letters('a'-'z','A'-'Z'), colons(':') and plusses('+').
  • Every element of rules will be in one of the two forms above:"BAD:" or "BAD:+".
  • Both and will consist of lowercase/uppercase letters and will be between 1 and 20 characters long, inclusive.
  • drinks will contain between 1 and 10 elements, inclusive.
  • Each element in drinks will consist of lowercase/uppercase letters and will be between 1 and 20 characters long, inclusive.

Examples

  1. {}

    {"A"}

    Returns: { "DRINK" }

    Base case example. A is good, you should drink it.

  2. {"BAD:RelakShok+Antimurpas"}

    {"RelakShok","Antimurpas"}

    Returns: { "DRINK", "PASS" }

    If we try to drink both of them, we get sick based on the only rule. However, we can drink either one of them. Since "RelakShok" comes first in the list, we drink it.

  3. {"BAD:RelakShok+Antimurpas","BAD:RelakShok"}

    {"Antimurpas","RelakShok"}

    Returns: { "DRINK", "PASS" }

    Nothing is stopping you from drinking the Antimurpas by itself, but RelakShok is always bad, so we can't drink it.

  4. {"BAD:RelakShok","BAD:Minas"}

    {"RelakShok","Minas"}

    Returns: { "PASS", "PASS" }

    Both drinks will make you sick.

  5. {"BAD:Minas+Antimurpas"}

    {"Minas","Antimurpas","Antimurpas"}

    Returns: { "DRINK", "PASS", "DRINK" }

    Note that since drinking the third Antimurpas is not immediately after the Minas, it is safe.

  6. {}

    {"Bitas","Antimurpas"}

    Returns: { "DRINK", "DRINK" }

  7. {"BAD:Bitas"}

    {"Antimurpas","RelakShok"}

    Returns: { "DRINK", "DRINK" }

    Nothing wrong with either of those drinks.

  8. {"BAD:A+A"}

    {"A","A","A","A","A","A","A","A","A","A"}

    Returns: { "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS" }

  9. {"BAD:beer+liquor"}

    {"beer","beer","liquor","beer","beer"}

    Returns: { "DRINK", "DRINK", "PASS", "DRINK", "DRINK" }

  10. {"BAD:A+B","BAD:B+C","BAD:C+A","BAD:B+A","BAD:C+B"}

    {"A","C","B","C","A","B","D","C","B","A"}

    Returns: { "DRINK", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "DRINK", "DRINK", "PASS", "DRINK" }

  11. {"BAD:A+B","BAD:A+B","BAD:A+B","BAD:A+B","BAD:A+B","BAD:A+B" ,"BAD:A+B","BAD:A+B","BAD:A+B","BAD:A+B","BAD:A+B","BAD:A+B" ,"BAD:A+B","BAD:A+B","BAD:A+B","BAD:A+B","BAD:A+B","BAD:A+B" ,"BAD:A+B","BAD:B+A"}

    {"A","B","A","B","A","B","A","B","A","B"}

    Returns: { "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS" }

  12. {"BAD:A+B","BAD:B+C","BAD:C"}

    {"A","B","C"}

    Returns: { "DRINK", "PASS", "PASS" }

  13. {"BAD:A+B","BAD:B+A"}

    {"A","B","A"}

    Returns: { "DRINK", "PASS", "DRINK" }

  14. {"BAD:A+B","BAD:B+A","BAD:A"}

    {"A","B","A","B"}

    Returns: { "PASS", "DRINK", "PASS", "DRINK" }

  15. {"BAD:A+B","BAD:B+A","BAD:A+C"}

    {"A","B","C","A","C","A","B"}

    Returns: { "DRINK", "PASS", "DRINK", "DRINK", "PASS", "DRINK", "PASS" }

  16. {"BAD:A+B"}

    {"B","A"}

    Returns: { "DRINK", "DRINK" }

    Order is important

  17. {"BAD:A+B","BAD:B+A","BAD:A+C"}

    {"A","A","B","A","C","A"}

    Returns: { "DRINK", "DRINK", "PASS", "DRINK", "PASS", "DRINK" }

  18. {"BAD:A+B","BAD:B+A","BAD:A+C"}

    {"D","A","C","A","B","A","C","A","D"}

    Returns: { "DRINK", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "DRINK" }

  19. {"BAD:A+B","BAD:B+A","BAD:A+C","BAD:D","BAD:C"}

    {"D","A","C","A","B","A","C","A","D"}

    Returns: { "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS" }

  20. {"BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A","BAD:A"}

    {"A","A","A","A","A","A","A","A","A","A"}

    Returns: { "PASS", "PASS", "PASS", "PASS", "PASS", "PASS", "PASS", "PASS", "PASS", "PASS" }

  21. { "BAD:RelakShok+Antimurpas" }

    { "RelakShok", "Antimurpas" }

    Returns: { "DRINK", "PASS" }

  22. { "BAD:a+c", "BAD:a", "BAD:c", "BAD:c+d", "BAD:b" }

    { "a", "b", "c", "d" }

    Returns: { "PASS", "PASS", "PASS", "DRINK" }

  23. { }

    { "D", "D", "R" }

    Returns: { "DRINK", "DRINK", "DRINK" }

  24. { "BAD:Bob+Bob", "BAD:Fred+Fred", "BAD:Fred+Bob", "BAD:Bob+Fred" }

    { "Fred", "Bob", "Bob", "Fred", "Bob", "Bob", "Fred", "Fred", "Fred", "Bob" }

    Returns: { "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS" }

  25. { "BAD:a+b" }

    { "a", "b" }

    Returns: { "DRINK", "PASS" }

  26. { "BAD:A", "BAD:A+B" }

    { "A", "B" }

    Returns: { "PASS", "DRINK" }

  27. { "BAD:Fred+Fred", "BAD:Fred+Bob", "BAD:Bob+Bob", "BAD:Bob+Fred" }

    { "Bob", "Fred", "Fred", "Bob", "Bob", "Fred", "Fred", "Fred", "Bob", "Bob" }

    Returns: { "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS" }

  28. { "BAD:Bob+Bob", "BAD:Fred+Fred", "BAD:Fred+Bob", "BAD:Bob+Fred" }

    { "Fred", "Bob", "Fred", "Fred", "Bob", "Fred", "Fred", "Fred", "Bob", "Bob" }

    Returns: { "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS" }

  29. { "BAD:Fred+Fred", "BAD:Bob+Bob", "BAD:Fred+Bob", "BAD:Bob+Fred" }

    { "Bob", "Fred", "Fred", "Bob", "Bob", "Fred", "Bob", "Bob", "Bobl", "Fred" }

    Returns: { "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "PASS", "DRINK", "DRINK" }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: