Match Editorials

Match summary

The 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 Problems

Value	250
Submission Rate	51 / 53 (96.23%)
Success Rate	49 / 51 (96.08%)
High Score	xiaowuc1 for 249.24 points (1 mins 34 secs)
Average Score	231.36 (for 49 correct submissions)

This problem has a reasonably straightforward solution. In order to round each quotient to the nearest integer, several paths are available. Some competitors used pre-built 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;
}

Value	500
Submission Rate	43 / 53 (81.13%)
Success Rate	21 / 43 (48.84%)
High Score	Token for 471.36 points (7 mins 5 secs)
Average Score	348.74 (for 21 correct submissions)

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*(M-1) time steps by subtracting M-1 from each active processor. This reduces the runtime to O(N²), 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 += (M-1)*P;
    for(int i=0; i < N; i++) 
        if(tasks[i] > 0) tasks[i] -= M-1;
        
            // 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;

}

Value	1000
Submission Rate	21 / 53 (39.62%)
Success Rate	11 / 21 (52.38%)
High Score	tourist for 880.54 points (10 mins 46 secs)
Average Score	641.75 (for 11 correct submissions)

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 (r-1, b-1). Similarly, if you instead draw a blue marble, you will move to the state (r, b-2), 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+r-2 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 n-2 marbles, we can use O(n) memory by keeping two arrays; one containing the answers from the n-2 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²) 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.