Local favorite reid advancesby Yarin,
Long time member reid, the second highest seeded competitor in the event, was
heavily favored to win this round, with a probability of 45%. However, he started
Room 2 off slowly, submitting a rather involved easy problem after 20 minutes.
Instead, antimatter took the early lead, submitting the easy after 14 minutes,
followed by bladerunner and then aneubeck. Two more easy problem submissions
followed in the next few minutes, and 6 of the competitors had submitted after 25
minutes, all of whom moved on to the medium problem. However, despite taking a
while on easy problem, reid was the first to submit the medium problem, and had two
problems in after 40 minutes. In the next 20 minutes, bladerunner, antimatter, and
kalmakka all submitted the medium problem. Despite some furious typing, no one was
able to submit the hard problem, and at the end of the coding phase, everyone had
submitted the easy problem, and six coders submitted the medium.
TextColumnsThis is a fairly straightforward problem although it requires several steps:
Each step is a fairly simple task, and several of them can be done in one sweep. It should be easier and less error prone to split them into several tasks though. TablePartitionsSince all constraints must hold, the constraints for a partition can be specified as intervals for each column. For instance, a partition defined as "a>5 b>=9 a<9 d=3" in a table with 4 columns can be defined with the intervals { (6-8), (9-100), (0-100), (3-3) } where all intervals are inclusive. The first step then becomes to parse the input. For each partition, we split the constraint string at the spaces, and loop through all individual constraints, maintaining the intervals for each column. The min and max for each column is initially set to 0 and 100, respectively, since those are the maximum values. It's important not to just set the min or max for each column to the value in the constraint since that would cause problems on elements such as "a>10 a>3". Care needs also to be taken of the equality operator; it's easiest to treat this as two operators, both <= and >=. Once this is done, it becomes easy to check the EMPTY case: If, for any partition, the interval for a column is such that the min value is greater than the max value, then obviously no element can go into this partition. Otherwise at least one element satisfies all constraints in a partition. Before considering the remaining cases, let's first try to visualize the partitions. If there were only two columns, a partition can be described with two intervals as mentioned above. Now, this is exactly how one could define a 2D rectangle in the Cartesian coordinate system with the sides parallel to the axis. This can easily be extended to the general case: in a table with n columns, each partition can be thought of as a n-dimensional rectangle. Now, the second case is OVERLAP. This corresponds to when two of the n-dimensional rectangles overlap. We thus check, for each pair of partitions, whether there exist elements in each column that could go to both partitions. This can be done with the following C++ code: for(int i=0; i<noPartitions; i++) for(int j=i+1; j<noPartitions; j++) { // Check if partitions i and j overlap bool overlap = true; for(int col=0; col<noColumns; col++) { int newMin = max(intervalMin[i][col], intervalMin[j][col]); int newMax = min(intervalMax[i][col], intervalMax[j][col]); if (newMin>newMax) overlap = false; } if (overlap) return "OVERLAP"; } The last thing to check is completeness. This turns out to be very easy to check with the n-dimensional rectangles metaphor: since we know the rectangles don't overlap, all we have to do is check if the sum of the "volumes" for each rectangle equals the volume of the whole table (which is 101n). Here we have to be a bit careful: this sum won't fit in an int if there are 5 or more columns, so we have to use long (long long in C++). This can be implemented like this: long long sum = 0, totalVol = 1; for(int col=0; col<noColumns; col++) totalVol *= 101; for(int i=0; i<noPartitions; i++) { long long vol = 1; for(int col=0; col<noColumns; col++) vol *= (intervalMax[i][col]-intervalMin[i][col]+1) sum += vol; } if (sum<totalVol) return "INCOMPLETE"; return "OK"; MhingThe first observation to make is that we can assume that all cards we pick up will be a Mhing card, and since we always will need one card, we can just pick up a card right away so we have 14 cards. The task at hand (pun intended) is to determine the least number of these cards that we have to replace with Mhing cards so that we get a Mhing hand. Before considering what algorithm to use, let's find a suitable representation for the cards. The honor cards can simply be thought of as individual suits, each having value 1. That is, if bamboo, character and dots are suits 0, 1 and 2, the west wind can be suit 3, east wind suit 4 etc. Then we don't have to treat these cards differently since they can't occur in sequences when they all have the same value. It's very tempting to loop over all 214 subsets of cards, and replace those cards not in the subset with Mhing card and check whether you can form a Mhing hand of the cards. It turns out it's not so easy to determine whether 14 given cards (which will include Mhing cards) can be partitioned into groups using a simple strategy. It should be possible, but it's a very error prone method. A much safer method is to just try all possible card groupings, using memoization to avoid exceeding the 8 second time limit. This can be done at the same time we're checking which cards to replace with Mhing cards. We define a recursive function with the following head: int replace(int mask, int mhingCards, bool pairUsed) The replace function should return the least number of cards that needs to be replaced to get a Mhing hand. mask is a bitmask (essentially a subset of the original cards) telling which cards must yet be assigned to a group (or replaced), mhingCards is the number of available Mhing cards and pairUsed tells if the pair group has yet been decided (remember that there should be exactly one pair group). Note that in this approach, we have to separate the Mhing cards from the other cards. So, if 3 of the 13 cards in the input are Mhing cards, only 10 bits in the bitmask should be used, and mhingCards should initially be 4 (since we add an extra Mhing card right away to get 14 cards total). The state space is small enough to use memoization. To evaluate the function, start by looping over all cards that still has not be assigned a group (from now on referred to "is in the mask"); let this card have index i in the mask (if all cards have been assigned a group, we are done; the method then returns 0). There are now several options for this card:
2) The card is part of a group with 3 cards where the other two cards are in the mask. 3) The card is part of a group with 3 cards where only one other card is in the mask (1 Mhing card needed). 4) The card is part of a group with 3 cards where none of the other two cards are in the mask (2 Mhing cards needed). 5) The card is part of the pair where the other card is in the mask. 6) The card is part of the pair where the other card is not in the mask (1 Mhing card is needed). All cases must always be considered, if they're legal (i.e. we can't use a card in a pair if pairUsed is set etc). For instance, the result of the first case would simply be replace(mask-(1<<i), mhingCards+1, pairUsed)+1. In case 3, we first check that mhingCards is at least 1. If so, loop over all remaining cards and let j be the index of this card. If i and j can be in the same group of 3 cards (with the help of a Mhing card), the result of this case would be replace(mask-(1<<i)-(1<<j), mhingCards-1, pairUsed). Of all possible options for any card i, we of course select the one with the minimum number of replacements. No extra pruning is needed, the recursive function with memoization is enough to make the problem run within the time limit. The pseudo code for the recursive function can look like this: (without the memoization part). int replace(int mask, int mhingCards, bool pairUsed) begin if mask is empty, return 0 best = infinity for each i in mask begin case1 = replace(mask-(1<<i), mhingCards+1, pairUsed)+1 for each j and k in mask if i,j,k can form a 3-group case2 = replace(mask-(1<<i)-(1<<j)-(1<<k), mhingCards, pairUsed) if mhingCards>0 then for each j in mask if i,j an form a 3-group with the help of a Mhing card case3 = replace(mask-(1<<i)-(1<<j), mhingCards-1, pairUsed) if mhingCards>1 then case4 = replace(mask-(1<<i), mhingCards-2, pairUsed) if not pairUsed then begin for each j in mask begin if i,j can form a pair case5 = replace(mask-(1<<i)-(1<<j), mhingCards, true) if mhingCards>0 case6 = replace(mask-(1<<i), mhingCards-1, true) end best = min of (best, case1, case2, case3, case4, case5, case6) end return best end The for each statements above should of course only loop over unique indexes, i.e. i, j and k are always different cards. The functions to check whether two or three cards can form a group of cards are all fairly straightforward to implement, so I won't discuss them here. |
|