Match Editorial

Match summary

After nearly a month since the previous SRM, SRM 364 kicked off in high gear with 1164 competitors ready for action. The long break did not seem to affect these brave souls, and many were shouting "Woohoo!" as their code passed the system tests. At the end of the challenge phase, ltdtl, bozzball, and Eryx were standing on top of the leaderboard. However, all three cried out "D'oh!" as system tests took them out of contention. With two challenges and strong times on all three problems, OpenGL took home the top spot for his first SRM win, followed closely by liympanda and windbells (regaining his red color). domino and SnapDragon rounded out the top 5.

In Division 2, narri took home the gold with solid times on all three problems, including the fastest medium and hard problems. ranc's two successful challenges vaulted him into second, with Eeyore, WtbH, and izquierdo coming in close behind.

The Problems

Value	250
Submission Rate	496 / 564 (87.94%)
Success Rate	467 / 496 (94.15%)
High Score	rajesh105.04 for 249.42 points (1 mins 22 secs)
Average Score	196.65 (for 467 correct submissions)

To solve this problem, we split the message into its individual letters, and then search through the library for the letter associated with them. If we find the coded letter in the library, we append that to the returned string. If the coded letter is not in the library, we instead append a '?'. With at most 25 encoded letters in the message, and only 50 possible encodings, this can easily be done without further optimization. Java code for this follows:

public String decrypt(String[] library, String message)
{
 String words[] = message.split(" ");
 String ret = "";
 for(int i=0; i < words.length; i++)
 {
  char next = '?';
  for(int j=0; j < library.length; j++)
   if(words[i].equals(library[j].substring(2)))
   { next = library[j].charAt(0);
    break;
   }
  ret += next;
 }
 return ret;
}

Value	600
Submission Rate	184 / 564 (32.62%)
Success Rate	148 / 184 (80.43%)
High Score	narri for 468.44 points (16 mins 1 secs)
Average Score	293.12 (for 148 correct submissions)

Value	300
Submission Rate	469 / 509 (92.14%)
Success Rate	454 / 469 (96.80%)
High Score	kp7 for 269.17 points (9 mins 50 secs)
Average Score	186.06 (for 454 correct submissions)

To help Bart out with his game's leaderboard, we need to first determine the scores of each individual player. If a player splattered a teammate, then he receives -1 point; otherwise, the player gains 1 point, and the splattered player loses 1 point. Once this part is done, we obtain the team scores by summing the scores of their individual players. We then sort the teams (paying attention to alphabetical order), and process the teams one by one. For each team, we sort the team's players in order, and output those. kp7's fastest solution is a very good illustration of this method.

An alternate way to do this is to create a data structure containing a player's name, score, team, and team score. By providing a way to compare two of these data structures, we can put all of the data in and do one sort. Then we process the entries one by one and output the answer easily. gozman's solution is a nice example of this.

Value	1000
Submission Rate	42 / 564 (7.45%)
Success Rate	18 / 42 (42.86%)
High Score	narri for 905.50 points (9 mins 22 secs)
Average Score	592.93 (for 18 correct submissions)

Value	500
Submission Rate	340 / 509 (66.80%)
Success Rate	277 / 340 (81.47%)
High Score	ACRush for 493.65 points (3 mins 13 secs)
Average Score	365.94 (for 277 correct submissions)

With N=16 in the worst case, the constraints allow for an O(2^N * N²) algorithm. We can represent the state using a bitmask, where the i-th bit is 1 if the plant is operational, and 0 if the plant is not. We can then use dynamic programming to solve the problem. From any given state, we can quickly calculate the costs of powering each unpowered plant by looping through all powered plants, and taking the cheapest cost. If at any time we have at least numPlants plants powered, we compare that cost to the minimum found so far. Iterating over all possible moves, we will eventually obtain the minimum cost path. A Java solution in this light follows:

public int minCost(String[] connection, String curPowered, int numPlants)
{
 int N = connection.length;
 int costs[][] = new int[N][N];
 
 for(int i=0; i < N; i++)
 for(int j=0; j < N; j++)
  costs[i][j] = connection[i].charAt(j)<='9'?connection[i].charAt(j)-'0'
            :connection[i].charAt(j)-'A'+10;
 int dpTable[] = new int[1 << N];
 
 Arrays.fill(dpTable, 10000);
 
 int curMask = 0;
 for(int i=0; i < N; i++)
    if(curPowered.charAt(i)=='Y')
        curMask |= 1 << i;
 
 dpTable[curMask] = 0;
 int ret = 10000;
 for(int i=1; i < (1 << N); i++)
 {
  int g=0, h=i;
  while(h > 0)  // g counts the number of powered plants
  {
   h = h & (h-1);
   g++;
  }
  if(g >=numPlants)
  {
   ret = Math.min(ret, dpTable[i]);
   continue;
  }
 
  for(int j=0; j < N; j++)
   if((i & (1 << j))==0)
   { 
    int lowCost = 10000; // lowCost is the lowest cost to power j
    for(int k=0; k < N; k++)
        if((i & (1 << k))!=0)
             lowCost = Math.min(lowCost, costs[k][j]);
    dpTable[i | (1 << j)] = Math.min(dpTable[i | (1 << j)],
                         lowCost+dpTable[i]);
   }
 }
 return ret;
}

Although this code runs in time under these constraints, a larger value of N (N=21, for instance) would not be feasible. However, there is an O(N * 2^N + N²) solution for this problem, which runs in time for N=21 in Java (as well as for N=22 in about 1.3 seconds for C++). This solution is omitted here, so that the reader may discover it for himself, but my code with this complexity is available in the practice room.

Value	1000
Submission Rate	40 / 509 (7.86%)
Success Rate	37 / 40 (92.50%)
High Score	domino for 761.62 points (17 mins 3 secs)
Average Score	572.52 (for 37 correct submissions)

First, let us consider the simpler problem of determining what gifts each guest would end up with, regardless of how the gifts are swapped. Starting with the last person, we see that they can choose a gift with no unhappiness, simply by swapping to get it (or not swapping if they already have it). Thus, we can remove that gift from the other guests' preferences, leaving the same problem (but with one fewer guest). Following the same algorithm, we can quickly determine the gift that each guest will have at the end of an optimal YankeeSwap:

boolean used[] = new boolean[256];

String finalString = "";

for(int i=N-1; i>-1; i--)
{
     int j=0;
     while(used[preferences[i].charAt(j)]) j++;
     finalString = preferences[i].charAt(j) + finalString;
     used[preferences[i].charAt(j)] = true;
}

Once we have this optimal ending arrangement, the question is how to get there, fitting the swapping constraints. The most common approach involved a greedy brute force (similar to what is seen in domino's fastest solution). Assume that we have found an optimal move for the first i-1 guests. Since each following guest will act greedily (as seen in the code above), we try each possible move for guest i, and follow it with a greedy solution for the remaining guests. If this yields the same finalString as seen above, then we accept this move and move on to the next guest; otherwise, we try the next move. Since the following guests must act to minimize their own unhappiness, this guarantees that we will arrive at the finalString, and that the string we return conforms to the rules.

Alternatively, we start with Guest i, and find the guest who is holding the gift he wants. We then take that person's final gift, and find the person who is holding it. Continuing this pattern, we will eventually either return to Guest i, or find some Guest j with j<i. In the first case, Guest i can do nothing, and his gift will eventually come to him. In the latter case, then Guest i must swap with Guest j in order to receive his gift, and his move is uniquely determined. See Sumudu's post for a nice proof that this works, and liympanda's solution for an example of this approach.

Finally, we can essentially start with finalString, and work our way back to the initial configuration. This is based on the fact that a previous guest who wants the gift you are holding will make a move to hold the optimal gift for you to hold (either the gift that you directly want, or a gift that will eventually lead to your gift). The moves made during this backwards conversion are the same moves that would be done during the Swap. See windbells's solution for a clear implementation of this strategy, or see SnapDragon's solution for a very interesting recursive implementation of this approach.