Tuesday, March 19, 2024
 
contentN

Jan_Kuipers wins Room 1!


Discuss this match
Wednesday, June 27, 2007
Introduction by Olexiy

TopCoder Open 2007 started with the Algorithm Semifinal 1. Number 1 seed ACRush and TCO 2005 Algorithm Champion Eryx were fighting for their spots with 14 other members, with each of them wanting to upset the favorites. ACRush showed he deserved his status with a lightning submission of the 250-pointer, distantly followed by JongMan, Eryx and Vasyl[alphacom].

The medium appeared to be much more difficult than it seemed, with the first submission coming only 50 minutes after the coding started. Soon after that, Per submitted the 1000 problem quickly followed by Ying submitting the 500. Right before the end of the coding phase, coders rushed to submit whatever they had. Jan_Kuipers managed to stun the crowd by submitting the medium for 400+ points, which was more than 100 points better than the previous highest score on that problem, while ACRush took the lead with a strong 700 of 1000.

The challenge phase didn't change the standings significantly, while system testing caused many solutions to fail. As the result, all 3 submissions for the hard failed and Jan_Kuipers advanced to the finals thanks to his amazing score on the medium. Eryx also advances to the finals thanks to his challenge, while Ying, liympanda and JongMan all go to the WildCard. lovro, with a successful challenge, takes the last Wild Card spot, with a tiny half-point lead over Vasyl[alphacom].

Congratulations to the advancers and good luck to the coders competing in the next rounds!


CostMatrix

by Yarin

An insight that almost immediately solves this problem is realizing that if the cost to go between cities A and B is x, and there exists some city C such that the cost to go from A to B and then to C equals x, then there need not be any direct flight between A and B (because that flight could never be cheaper than removing the other two flights). If we find that the cost by going through C is cheaper than x, then we have an inconsistency, and should return -1. So after the input parsing, the solution is to simply do a triple nested loop, trying all values of A, B and C, and deducing what direct flights are not needed.

DifferentPokerHands

by Yarin

This might not be one of the more algorithmically challenging problems the onsite competitors will face. Instead, some careful coding and case analysis is required. Precision is of essence; if you failed the last example after all the coding, bug tracking might take quite a while.

It should be obvious that the core function in this problem will be a method that evaluates a 5 card poker hand. One could immediately try and deduce the rank of a 7 card hand, but this is much more error prone. So how do you best evaluate such a hand, so that it can be compared with other hands, taking all the tie breaking rules into consideration? The best way is, probably, to calculate an integer score for a 5 card poker hand. Assuming we have such a function, evaluating a 7 card hand would then be the best score among all 7 choose 5 possible hand selections, and the number of different evaluated poker hands could be found be looping through all 47 choose 2 remaining cards, evaluating the 7 card poker hand and storing the best score in a set. The result would then simply be the size of this set.

The integer score for a hand can be represented as a six digit base-13 number, where the most significant digit represents the rank (0 for high card, 1 for pair, and so on). The second most significant digit would be the value of the first tiebreaker card (the overall highest card in many cases, but for full house for instance, it would be a card among the three-of-a-kind etc), the third digit would be the second tiebreaker card, and so on.

The evaluation begins by counting the number of aces, kings, queens and so forth in the hand, and store the result in a valueCount array. We can then count the elements in valueCount to find the number of pairs, three-of-a-kinds and four-of-a-kinds we have. From there on, it's mostly a number of if-statements that check the various conditions.

If one likes obfuscated C++ code, the following function is an example of an implementation of a 5 card poker hand evaluator:
int pokerEval(int c[]) // c[i] = 13 * suit + value
{
  int i,j,s=0,f=1,vc[13],sc[5],sv[5],sw[5];
  for(i=0;i<13;i++) vc[i]=0;
  for(i=0;i<5;i++) { sc[i]=sv[i]=0; f&=c[i]/13==c[0]/13; vc[c[i]%13]++; }
  for(i=12;i>=0;i--) { sc[j=vc[i]]++; sw[j]=sv[j]; sv[j]=i; if (j==1) s=s*13+i; }
  if (sc[4]) return 7000000+sv[4]*30940+sv[1];
  if (sc[2]&&sc[3]) return 6000000+sv[3]*30927+sv[2]*14;
  if (sc[3]) return 3000000+sv[3]*30927+s;
  if (sc[2]) return sc[2]*1000000+(sv[2]>?sw[2])*30758+(sv[2]<?sw[2])*182+s;
  if (s==349674) return 90258+1000000*(f?8:4);
  if (s==368714&&f) return 9000000+s;
  int st=(s-121186)%30941==0;
  return s+(st&&f?8:st?4:f?5:0)*1000000;
}

WorstCaseQuicksort

by Yarin

Optimization problems are of course very common in TopCoder. Usually we only have to return the minimized (or maximized) value, but sometimes the "way" to that value must be returned. Since TopCoder problems must have one single solution for a test case, some tie breaking scheme is needed (often the lexicographically first "way" is to be selected). Usually these tie breakers cause no (or very little) extra head ache; one often only has to make sure the loops are in the right order. This problem, however, is the total opposite. To find a sequence of integers that maximizes the nesting depth is very easy, and only a few lines of code are needed. To find the lexicographically first such sequence, however, is a much harder task.

Let Z[n] be the maximum nesting depth for a sequence of n distinct integers. Obviously Z[1] = 1, and it should also be obvious that Z is a non-decreasing sequence. Let f1, f2, f3 be the indexes in the sequence for a fixed value of n. We can assume that f1 <= f2 <= f3. If f1 = f2 or f2 = f3, the same index is included at least twice, so we know what the position of the pivot element will be no matter how we arrange the integers. If we put the smallest integer in the sequence at this known position, we will get a worst case, since the "less" list will be empty, and the "right" list will have length n - 1. Because Z is non-decreasing, this is the best we can get, so in that case Z[n] = Z[n - 1]. If f1 < f2 < f3, we can't get the smallest (or largest) integer selected as pivot element. We have to settle for the second smallest, so in this case Z[n] = Z[n - 2].

It might be intuitive from this to conclude that the pivot element select at each step should either be the smallest, second smallest, second largest or largest. However, this turns out not to be the case, which the first example showed (five elements, where the pivot element should be the middle element).

So, in order to determine the lexicographically first sequence of n numbers, in true DP style we assume we know the lexicographically first sequence for all sequence lengths less than n. We now try all integers between 1 and n (between 2 and n-1 if f1 < f2 < f3) as the pivot, and call this value p. The length of the two lists less and greater will then be p - 1 and n - p. We must first check that such a split indeed yields an optimal solution, by confirming that Z[n] = 1 + max(Z[p - 1], Z[n - p]). Assuming this is the case, then for both the less and greater list we can use the already computed optimal sequence of those lengths. In the case of the greater list, we need to modify its elements by adding p.

We know have two lists, lt and gt, and a pivot element p, which should merge into a single sequence seq, so that seq[f1] <= seq[f2] <= seq[f3] and seq[f2] = p. One must be a bit careful in implementing this merge in order to get the lexicographically first sequence. It can be done in one loop with several if-statements, but from a practical point of view it might be easier to split it up into several cases, depending on whether f1, f2 and f3 are different or not. It can look like this:
// Input: lt, gt, f1, f2, f3
boolean allDifferent = f1 != f2 && f2 != f3;
int seq[] = new int[n];
int seqPos = 0, ltPos = 0, rtPos = 0;
while (seqPos < n)
{
    if (seqPos == f1 && allDifferent)
        seq[seqPos++] = lt[ltPos++];
    else if (seqPos == f2)
        seq[seqPos++] = p;
    else if (seqPos == f3 && allDifferent)
        seq[seqPos++] = rt[rtPos++];
    else if (ltPos + (seqPos < p1 && allDifferent ? 1 : 0) < lt.length)
        seq[seqPos++] = lt[ltPos++];
    else
        seq[seqPos++] = rt[rtPos++];
}

This sequence can then be compared to the sequences generate by other selected values of p for a particular n, so that the lexicographically first sequence is chosen.

contentS