Saturday, July 12, 2014

CodeChef: Dish Owner

Problem Statement:
CodeChef: Dish Owner
Overview:

Keep track of winners in a cooking competition.

Java Source:
    01: /*
    02: CodeChef
    03: July Challenge 2014
    04: Description: http://www.codechef.com/JULY14/problems/DISHOWN
    05:  */
    06:
    07: import java.io.File;
    08: import java.util.Scanner;
    09:
    10: public class DishOwner {
    11:
    12:     public static void main(String[] args) throws Exception {
    13:
    14:         Scanner sc;
    15:
    16:         // If an arg is given, read from that file. Otherwise use stdin.
    17:         if (args.length > 0) {
    18:             File f = new File(args[0]);
    19:             sc = new Scanner(f);
    20:         } else {
    21:             sc = new Scanner(System.in);
    22:         }
    23:
    24:         // Get number of Test Cases
    25:         int numTestCases = Integer.parseInt(sc.nextLine());
    26:
    27:         for (int i = 0; i < numTestCases; i++) {
    28:
    29:             // Get number of Chefs
    30:             int numOfChefs = Integer.parseInt(sc.nextLine());
    31:
    32:             // Set dish owners
    33:             int[] owners = new int[numOfChefs];
    34:             for (int owner = 0; owner < numOfChefs; owner++) {
    35:                 owners[owner] = owner;
    36:             }
    37:
    38:             // Set scores for each Dish
    39:             int[] scores = new int[numOfChefs];
    40:
    41:             int dish = 0;
    42:             for (String s : sc.nextLine().split(" ")) {
    43:                 scores[dish++] = Integer.parseInt(s);
    44:             }
    45:
    46:             // Get number of Queries
    47:             int numOfQueries = Integer.parseInt(sc.nextLine());
    48:
    49:             // Process each query
    50:             for (int q = 0; q < numOfQueries; q++) {
    51:                 String[] query = sc.nextLine().split(" ");
    52:
    53:                 if (query.length == 3) {
    54:                     doCompetition(Integer.parseInt(query[1]) - 1,
    55:                             Integer.parseInt(query[2]) - 1, scores, owners);
    56:                 } else {
    57:                     System.out.println(getDishOwner(Integer.parseInt
    58:                             (query[1]) - 1, owners) + 1);
    59:                 }
    60:             }
    61:         }
    62:     }
    63:
    64:     private static void doCompetition(int dish1, int dish2, int[] scores,
    65:                                       int[] owners) {
    66:
    67:         int chef1 = getDishOwner(dish1, owners);
    68:         int chef2 = getDishOwner(dish2, owners);
    69:
    70:         if (chef1 == chef2) {
    71:             System.out.println("Invalid query!");
    72:             return;
    73:         }
    74:
    75:         if (scores[dish1] > scores[dish2]) {
    76:             owners[dish2] = chef1;
    77:         } else if (scores[dish2] > scores[dish1]) {
    78:             owners[dish1] = chef2;
    79:         } else {
    80:             // Tie. do nothing
    81:         }
    82:     }
    83:
    84:     private static int getDishOwner(int dish, int[] owners) {
    85:
    86:         int chef = dish;
    87:         while (owners[dish] != chef) {
    88:             chef = owners[dish];
    89:         }
    90:         return chef;
    91:     }
    92: }
Notes:

This is the first problem that I've attempted on the CodeChef.com site. I haven't registered for an account there, so I did not submit this code, and therefore I cannot guarantee that it passes their tests. It does however pass their example and my own unit tests.

The algorithm works by maintaining two integer arrays - scores, and owners. There are at most 10^4 chefs, and scores may be as large as 10^6 which easily fit into an int. Scores simply holds the scores for each dish. Once set, their values never change. owners initially holds the chef that brought the dish to the competion, but as challenges are won and lost, these values change.

The problem states that each chef chooses their dish optimally, and there is no constraint prohibiting them from using the same dish multiple times. I took this to mean that they always put up their highest scoring dish which will be the dish they started with since it's impossible to obtain one with a higher score. This also means that if the value in the owners array matches it's index, then that chef has never lost.

When a competition starts, I first determine the owner of the two dishes, more on this next. It checks to see if the owners are the same. Then determines a winner (or a tie). Here, the loser's owner is set to the winning chef. That is, in the owners array, the value at index loser is set to the winner: owners[loser] = winner

Now, to determine a dish's owner, we look into the owners array, and follow the chain up until the owner of the dish is the same value as the chef. The following table shows the state of the owners array after a series of competitions.

owners
Initial Setup:
index 0 1 2
value 0 1 2
Dish 2 beats Dish 0:
index 0 1 2
value 2 1 2
Dish 1 beats Dish 2:
index 0 1 2
value 2 1 1

To determine the owner of dish 0 after this series of competitions, we look at owners[0] and see the value is 2. Since 0 != 2, we then look at owners[2] and see the vaue of 1. Again, 2 != 1, so we continue following the chain by looking at owners[1]. Here, the index matches the value, so we conclude that 1 is the owner of dish 0.

Be careful about subtracting 1 from the index (Lines 54, 55, and 58) since the chefs and scores are numbered starting at 1 while our array starts at 0. We then need to add 1 back on when printing out the owner.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

For this, and other TopCoder solutions, please visit www.topcodingsolutions.net.

No comments:

Post a Comment