Subtask and partial-marks strategy

Many CCC problems are split into subtasks. Each subtask restates the problem with a smaller, more specific constraint on the input. A simple, slow solution can clear the easiest subtask outright, without going anywhere near a solution to the full problem. This changes your strategy: you do not have to solve the whole problem to make progress on it. You can finish a subtask, submit it, and move on to something else.

This is different from a contest where a wrong answer earns nothing. On CCC, a partial-marks problem lets you climb it one step at a time. Getting the smallest subtask correct and safe is real, independent progress, whether or not you ever reach the hardest one.

Recognising subtasks

A problem statement describes subtasks like this:

"Subtask 1: 1 <= N <= 100 Subtask 2: 1 <= N <= 10,000 Subtask 3: 1 <= N <= 1,000,000"

Each subtask loosens a constraint. Subtask 1 is the easiest, because the bound on N is the tightest. Subtask 3 is hardest, because it allows the full range the problem describes. These bounds are facts about the problem, not a target to aim for: read them the way you would read any other constraint, and let them tell you what kind of algorithm each subtask needs.

You can write a brute-force algorithm that handles every instance of Subtask 1. When N is at most 100, even a quadratic O(N^2) algorithm finishes instantly. Submit it, and move on to a smarter algorithm, perhaps an O(N log N) approach or a greedy observation, that also clears Subtask 2. If time allows, keep optimising for Subtask 3. If not, the earlier subtasks stand on their own.

A worked example: maximum sum of a contiguous subsequence

Imagine a problem: "Given N integers, find the maximum sum of a contiguous subsequence."

Subtask 1: N <= 100. Brute force: try all O(N^2) contiguous subsequences, sum each one, and keep the maximum. This finishes in milliseconds at N = 100, and takes only a few minutes to write and test.

Subtask 2: N <= 10,000. A quadratic algorithm is too slow now: 10,000^2 is 100 million operations against a one-second time limit. Kadane's algorithm (from M2.7) runs in O(N) time and clears both this subtask and the first one, for a modest amount of extra coding time.

Subtask 3: N <= 1,000,000. Kadane's algorithm still works unchanged. It clears every subtask, at the cost of a little more care with fast input and output.

Once Subtask 1 and Subtask 2 are both solved and tested, you face a choice: spend more time chasing Subtask 3, or move to a different problem that might be faster to make progress on. If the remaining optimisation is small and you are confident in it, finishing the problem is often worth the extra minutes. If a different, unstarted problem looks faster to gain ground on, moving there can be the better use of the time left in the contest.

A second worked example: counting inversions

Problem: Count the number of inversions in an array (pairs (i, j) where i < j but arr[i] > arr[j]).

Subtask 1: N <= 200. Brute force: check all pairs with two nested loops. O(N^2) is about 40,000 operations here, comfortably fast, and quick to write.

Subtask 2: N <= 5,000. The brute force now runs about 25 million operations. It may still finish in time, but the margin is thin. A merge-sort based approach counts inversions in O(N log N) and removes that risk, at the cost of a more careful, more error-prone implementation: an off-by-one in the merge step is easy to introduce and easy to miss.

Subtask 3: N <= 200,000. The same merge-sort approach clears this subtask too, but only if the implementation is exactly right. This is the point where the decision matters most: pushing further on one problem's hardest subtask means less time for every other problem, and a subtle bug in a complex routine can cost you the subtask you already had working.

A contestant who has already cleared Subtask 1 and Subtask 2 has made real, banked progress. Whether to spend the next stretch of time hardening the merge sort for Subtask 3, or reviewing the working solution once and moving to a different problem, depends on how confident you are in the harder implementation and on how much of the contest remains. Neither choice is automatically correct: it is a judgment about where your remaining time buys the most progress.

When to bank vs. when to push

Move to the next problem when:

• The next optimisation needs a complex or error-prone technique, such as a data structure you rarely implement.
• You have already spent a long stretch on this problem and further gains are getting smaller and harder to reach.
• A different, unstarted problem looks like it has an easier first subtask.
• Your current solution is clean, tested, and unlikely to hide a bug.

Keep working this problem when:

• The next optimisation is a small, well-practised step, such as swapping a brute force for a technique you know well.
• You are confident in both the algorithm and the implementation.
• A large part of the contest remains.
• You are unsure whether the other problems are actually easier than they look.

The grader keeps your best submission

When you submit to the judge, it runs your code against every test case in the problem, not only the subtask you were aiming for. If a solution written for the easiest subtask happens to also satisfy a harder one's constraints, the judge credits it for that subtask too, without you doing anything extra.

This means a simple algorithm sometimes covers more ground than you expected. Test your brute-force solution on a large input before assuming it only handles the smallest subtask: if it runs fast enough by chance, that changes what you decide to do next.

Recap

Many problems split into subtasks with looser and looser constraints. A solution built for the easiest subtask is real progress on its own, and you do not need to finish the whole problem to have gained something from it.

Decide what to do next based on the constraints you are reading, your confidence in the next step, and how much contest time remains, not on finishing every problem you touch. Solve the safest subtask first, keep track of the time left, and look honestly at what the other problems seem to need before choosing where to spend the next stretch of time.