Tuesday, July 1, 2008 Match summaryThe third match of the third TCHS season was an exciting match for the 67 young competitors. After an exciting challenge phase in which the lead changed hands several times, v3ctor was victorious after solving all problems and gaining seven successful challenges. neal_wu took second place with eight challenges, and tourist rounded out the top three. The ProblemsTournamentJudgingUsed as: Division One  Level One:
This problem has a reasonably straightforward solution. In order to round each quotient to the nearest integer, several paths are available. Some competitors used prebuilt libraries, while others simply added 0.5 to the raw score after division and before rounding. As some people worry about double imprecision when doing this, one can instead use only integers by adding conversionFactor/2 to the raw score prior to division; this guarantees that the result will round correctly. public int getPoints(int[] rawScore, int[] cF) { int ret = 0; for(int i=0; i < cF.length; i++) ret += (rawScore[i] + cF[i]/2)/cF[i]; return ret; }RRSchedule Used as: Division One  Level Two:
A simple approach to this problem is to simulate the problem as the statement describes. If we let T be the maximum value in tasks, and N be the number of elements in tasks, this leads to a O(NT) solution. However, T can be up to 20,000,000, which would lead to 1,000,000,000 steps in the worst case. This is too large, so we must optimize the problem further. The run time can be reduced by looping through the array and finding the minimum nonzero value M. If there are P processors still active, then we can simulate the next P*(M1) time steps by subtracting M1 from each active processor. This reduces the runtime to O(N^{2}), which is more than sufficient for this problem. public int[] terminalTimes(int[] tasks) { int N = tasks.length; int[] ret = new int[N]; int curTime = 0; int P = N; while(P > 0) { int M = 1000000000; for(int i=0; i < N; i++) // Get M if(tasks[i] > 0) M = Math.min(tasks[i], M); curTime += (M1)*P; for(int i=0; i < N; i++) if(tasks[i] > 0) tasks[i] = M1; // now simulate the next steps for(int i=0; i < N; i++) { if(tasks[i] == 0) continue; curTime++; tasks[i]; if(tasks[i] == 0) { ret[i] = curTime; P; } } } return ret; }MarblesInABag Used as: Division One  Level Three:
Assume that we currently have b blue marbles and r red marbles, and that it is our turn. You may draw a red marble from the bag; this will happen with probability r/(r+b), and after Sid's turn will leave you at the state (r1, b1). Similarly, if you instead draw a blue marble, you will move to the state (r, b2), with probability b/(b+r). This sets up a nice DP relation that normally would work well, but for the fact that the table will take up too much room in memory. Thus, we need to find a way to conserve memory. In the above recursion, you can see that there will always be b+r2 marbles after Sid's next turn. Thus, we can change the state to (total_marbles, red_marbles). We win if we reach any state (n, 0), and lose if we get to a state of (n, n); this is our base case. Since all calculations of n marbles are based only on the calculations from states involving n2 marbles, we can use O(n) memory by keeping two arrays; one containing the answers from the n2 marble state, and another where we build our answers for the n marble state. After building each row, we can swap the arrays, and compute the following step. Thus, our answer will be (b+r, r). See tourist's solution for a clean implementation of this approach. For those who enjoy code optimization, neal_wu's solution actually uses O(N^{2}) memory. Since the sum of red and blue marbles must be odd on your turn, we can store the table in a 2D array as (red, blue/2); the integer division cuts the size of the table in 2, making it just small enough to fit into memory. 
