Match summary

Three questions with a few hidden tricks resulted in 83 failed solutions out of a total of 207 submissions for TCHS SRM 8, the second in the Delta Quadrant. Weiqi capitalised on this, with 325 points from challenges resulting in an impressive 1893.29 before the system tests had begun. However, the testing phase claimed as many solutions as the challenge phase, leaving only 6 members with all 3 submissions still standing. Of those, newcomer MenShoiKin had the best possible debut, placing 1st, with hmao coming in second by a very narrow 0.62 points, and Rostislav rounding out the top 3 less than a challenge behind.

The Problems

FussySleeper

Used as: Division One - Level One:

Value 250

Submission Rate 113 / 125 (90.40%)

Success Rate 69 / 113 (61.06%)

High Score RuslanSM for 247.77 points (2 mins 42 secs)

Average Score 217.67 (for 69 correct submissions)

As the time "00:00" is divisible by every number, you are guaranteed to have at least one solution. With only 24 * 60 = 1440 minutes to check, it is sufficient to simulate the time, until we get one where we can fall asleep. This can be done minute by minute, being careful to not simulate illegal times, such as 9:61 or 24:00.

To test for divisibility, you can first get the 4-digit number 'HH:MM' by calculating 100*HH + MM. Next, to check if this is a multiple of the number of elephants, you may find the mod operator '%' useful, as divisibility is the same as checking whether (100*HH + MM) % elephants == 0.

This strategy was in the solution by the fastest submitter, RuslanSM, and can be seen below:

    do{
    currentTime[1] ++; // increment minute
    if(currentTime[1] == 60)
    currentTime[0] ++; // increment hour

    currentTime[0] %= 24; // fix times
    currentTime[1] %= 60;
    } while((currentTime[0] * 100 + currentTime[1]) % elephants != 0);

    return currentTime;

WordMath

Used as: Division One - Level Two:

Value 500

Submission Rate 61 / 125 (48.80%)

Success Rate 49 / 61 (80.33%)

High Score Weiqi for 480.08 points (5 mins 50 secs)

Average Score 341.40 (for 49 correct submissions)

One way to approach this problem, as coded by Weiqi, was to try every single letter-to-digit mapping, calculate the sum for each, and return the best of these. To get all the possible mappings you can put the digits {0, 1, ...} into an array, and use a next_permutation method to iterate through every combination. At worst case, this uses around 10! combinations * 8 letters * 10 words = 290 million.

This will only just run in time, providing you use efficient storage, but some optimisations can be implemented to help speed things up. The key is to realise that you can do a bit of precalculation, by treating the digits as variables, similar to an algebra question. For example:

"CAB" = 100 * C + 10 * A + 1 * B, and
    "AB + BAC" = 20 * A + 101 * B + 1 * C

By calculating these multipliers at the start, it changes the operations to closer to 8 * 10 + 10!, which will easily run in time.

However, using the representation above, looking at the second example you can see that if A were greater than B, you could swap their digit values and the total would increase by (101 - 20) * (A - B). This is enough to show that once we calculate how much each letter contributes to the overall total, we can greedily assign the digits, giving 9 to the letter with the greatest contribution, 8 to the next, and so on.

See hmao's solution for a neat implementation of this.

PendingTasks

Used as: Division One - Level Three:

Value 1000

Submission Rate 33 / 125 (26.40%)

Success Rate 6 / 33 (18.18%)

High Score reiten for 514.30 points (35 mins 42 secs)

Average Score 470.40 (for 6 correct submissions)

On first inspection, the input of this problem may seem a bit unusual. If you consider the tasks as nodes, and dependencies as edges, then the input describes a graph. This is also a special type of graph, as the constraints make it a directed graph, with no cycles, and exactly one edge out of all but the last node. In other words, a tree rooted at the last task, such as:

An important realisation is that every node (task) can only be in one of three states:

Not executed. If a node is not used, then at most one of its children will used, the rest must be unused.
Forced execution. This occurs when the execution of this node will eventually force the root node to be executed. In this case, exactly one if its children is used voluntarily, and one other can be a forced execution.
Voluntary execution. A node is in this state is executed, but its execution doesn't cause the root task to be executed. As its execution does not force termination, all of its children can then also be executed voluntarily after it.

Using this observation, we can define three values for each node, being the maximum number of tasks that can be executed in the subtree rooted at node #ref if that node is:

not executed = cache[ref][0], a forced execution = cache[ref][1] or a voluntary execution = cache[ref][2]

The solution is the number of tasks that can be executed before the final task must be, so the required answer is cache[#tasks - 1][1] - 1;
The question then is how to calculate these cache values. Using the descriptions above, in pseudocode:

    // task is not executed
    cache[ref][0] = 0 +
    sum( cache[child][0] ) +
    // voluntarily execute the single child that has the best benefit
    max( cache[child][2] - cache[child][0] );

    // task is executed
    cache[ref][1] = 1 +
    sum( cache[child][0] ) +
    // execute two children(c1, c2), one forced.
    max( cache[c1][2] - cache[c1][0] + cache[c2][1] - cache[c1][0] );

    // task is executed
    cache[ref][2] = 1 +
    // all subtasks voluntarily executed too
    sum( cache[child][2] );

The ordering of tasks in the input meant you could loop through all tasks and calculate the cache values in order, taking care to handle the special cases when a task has 0 or 1 children. For a solution which implements the memoized version of this, see the solution by FarV. In this, Time1(ref) calculates cache[ref][0], TimeMin(ref) calculates cache[ref][1], and TimeAll(ref) calculates cache[ref][2].

Also, for those who enjoyed this problem, here are two variations to ponder:

The above algorithm is O(N³), as the calculation of cache[ref][1] is quadratic at worst. Is this the best you can do?
What is the best algorithm if the tasks must be executed at priority 3, rather than 2? How about k?

By sql_lall
TopCoder Member