Tuesday, September 18, 2007 Match summaryThis match was defined by a tough problemset for the competitors, with no solutions to the hard problem and only 12 coders solving the other two. However, there were few wrong submissions, thanks perhaps to the examples in the problems. The winner of the match was exod40 with two problems and a fast submit in the medium, followed by yifan.oi and szsz with two problems solved each. Congratulations to them for their great performance. The ProblemsWebBrowserUsed as: Division One  Level One:
To make the browser simulation three structures are needed: a stack for the back pages, a stack for the forward pages and a vector to store the sequence of pages loaded. Then, we have to iterate each element in actions and execute it following what is descibed in the statement. Finally, just return the vector of pages loaded. For a straightforward solution, look at exod40's code. LinearCityUsed as: Division One  Level Two:
To solve this problem, some knowledge about graph theory might be very useful. To solve the problem, we have to recognize some properties about the references:
Using the first property, we can change every reference that goes from A to B walking to the left to a reference that goes from B to A walking to the right, so all our references will go in a single direction  in this case, to the right. Then, for each query asking for the direction from C to D, we will make two queries, one to check if to go from C to D you have to walk to the right and another to check if to go from D to C you have to walk to the right. If the first query returns true, you have to return "RIGHT". If the second query returns true, you have to return "LEFT". Finally, if both queries return false, you have to return "UNKNOWN". The only part left in the solution is to implement the queries. There are two basic algorithms to implement this:
Used as: Division One  Level Three:
The easiest way to solve this problem is to try each integer in the interval [low, high] and return the one with the lowest bit difference for each values[k]. However, this approach is too slow to pass system tests, because the interval can have up to 2^{30} elements. One way to solve this problem in time involves two recursive searchs. The first step is to split the binary representation of low, high and values[k] in two parts, one where the bits of low and high are the same, and the other where the low and high numbers start to differ (from the most significant bit to the lowest significant bit). For example: high = (181)_{10} = (10110101)_{2} = (101 10101)_{2} low = (173)_{10} = (10101101)_{2} = (101 01101)_{2} values[k] = (38)_{10} = (00101010)_{2} = (001 00110)_{2} To solve the first part we just have to change the first part of values[k] to the first part of low, because if we put a different value in the first part then the final result will be lower than low or higher than high. Now, we can ignore the first part and work only with the second part: high = (10101)_{2} = (21)_{10} low = (01101)_{2} = (13)_{10} values[k] = (00110)_{2} = (6)_{10} Then, the interval can be split in two parts, those where the most significant bit is 0 and and the most significant bit is 1: interval = [01101, 10101] = [01101, 01111] U [10000, 10101] Then, we could search the lowest different number in the both intervals separately and return the one with the lowest difference (or the lowest lexicografically if the difference is equal). To search the best number in the lower interval, we can search recursively from the most significant bit to the least significant bit, comparing the bits in low and value. Then, we have four cases (lowBit is the actual bit of low and valueBit is the actual bit of values[k]):
Something similar can be done with the higher interval. The algorithm runs in O(N), where N is the number of different bits between low and high. The following commented code in Java implements this algorithms using bit manipulation: import java.math.*; import java.util.*; public class RangeFixer { // strucutre to store the algorithm results public class FixResult { public int value, cost; public FixResult(int value, int cost) { this.value = value; this.cost = cost; } } public int getEqualMask(int low, int high) { // return a mask with the longest mostsignificant consecutive block of ones // at the left int eqBits = ~(low ^ high), shift = 0; while ((eqBits & (eqBits + 1)) != 0) { eqBits >>= 1; ++shift; } return eqBits << shift; } FixResult closestToLow(int low, int value, int bit) { // base case, all bits were processed if (bit == 0) return new FixResult(0, 0); // the actual bit in value is higher than the actual bit in low, so no // change to value is needed if ((low & bit) == 0 && (value & bit) != 0) return new FixResult(value, 0); // the actual bit in low is one, so the bit in value must be changed to one // if needed, and then the lowest bits must be adjusted if ((low & bit) != 0) { FixResult next = closestToLow(low & ~bit, value & ~bit, bit >> 1); next.value = bit; if ((value & bit) == 0) ++next.cost; return next; } // both bits are zero, so we have two options, the first is to change the // actual bit in value to one and left the remaining bits equal, and the // second is to keep the bit in zero and adjust the remaining bits FixResult change = new FixResult(value  bit, 1); FixResult noChange = closestToLow(low & ~bit, value & ~bit, bit >> 1); return noChange.cost <= change.cost ? noChange : change; } FixResult closestToHigh(int high, int value, int bit) { // base case, all bits were processed if (bit == 0) return new FixResult(0, 0); // the actual bit in value is lower than the actual bit in high, so no // change to value is needed if ((high & bit) != 0 && (value & bit) == 0) return new FixResult(value, 0); // the actual bit in high is zero, so the bit in value must be changed to // zero if needed, and then the lowest bits must be adjusted if ((high & bit) == 0) { FixResult next = closestToHigh(high & ~bit, value & ~bit, bit >> 1); if ((value & bit) != 0) ++next.cost; return next; } // both bits are one, so we have two options, the first is to change the // actual bit in value to zero and left the remaining bits equal, and the // second is to keep the bit in one and adjust the remaining bits FixResult change = new FixResult(value & ~bit, 1); FixResult noChange = closestToHigh(high & ~bit, value & ~bit, bit >> 1); noChange.value = bit; return change.cost <= noChange.cost ? change : noChange; } public int closestValue(int low, int high, int value) { // get the mostsignificant consecutive equal bits between low and high, // then truncate all the numbers to the nonequal part int eqMask = getEqualMask(low, high), eqPart = eqMask & low; low &= ~eqMask; high &= ~eqMask; value &= ~eqMask; // find the closest value the closest value higher than low with bit in 0 int bit = (~eqMask + 1) >> 1; FixResult lowRes = closestToLow(low & ~bit, value & ~bit, bit >> 1); if (((low ^ value) & bit) != 0) ++lowRes.cost; // find the closest value lower than high with bit in 1 FixResult highRes = closestToHigh(high & ~bit, value & ~bit, bit >> 1); highRes.value = bit; if (((high ^ value) & bit) != 0) ++highRes.cost; // attach the result with the lowest cost to the equal part and return return eqPart  (lowRes.cost <= highRes.cost ? lowRes.value : highRes.value); } public int[] closestValue(int low, int high, int[] values) { // calculate the solution for each value and return int[] result = new int[values.length]; for (int k = 0; k < values.length; ++k) result[k] = closestValue(low, high, values[k]); return result; } }

