Reading all problems first and ordering by difficulty

Why this matters when you build with AI

When you build with AI tools, you constantly decide which task to hand off first, which one to do yourself, and which one to leave for later. A contest asks the same question with a fixed clock. Competitors who start coding the first problem they see often spend the whole contest on one hard problem and solve nothing else. The skill this lesson trains is the same one you need to split a product backlog: look at everything, estimate the cost and the chance of success, and pick an order you can defend.

The idea: a short scan before any coding

A contest set is a list of problems. Each problem has a statement, which is the text that describes the input, the output and the limits. A limit is a bound such as n <= 200000 or time limit 2 seconds. The limits matter as much as the story, because they tell you which kinds of solutions can pass.

The opening scan is a fixed routine:

1. Read every statement once, from the first problem to the last. Do not code and do not think for long on any one of them.
2. For each problem, write three tags on paper: a rough difficulty (easy, medium or hard), a topic guess (for example graph, string, counting or geometry) and one line of what you would try first, even if you are not sure.
3. Mark each problem with a risk note: "I can see the idea", "I have no idea", or "statement is long and I may have misread it".
4. Use the solve count or the scoreboard only as a weak signal, which section 3 explains.
5. Write the attack order and one line of reason next to each problem.

The scan should take 10 to 15 minutes. If it takes 30, you are solving while reading, which is the habit the scan is meant to stop. Keep a timer visible.

A concrete example shows why the tags matter. Suppose problem B looks short and ends with "print the number of ways modulo 998244353", and problem C is three paragraphs long with a picture. A reader who only counts paragraphs picks B last. A reader who reads the limits finds that B needs the same counting idea as a problem they solved last month, and that C needs a graph structure they have not used yet. The scan lets you find that out in two minutes instead of forty.

Tagging each problem

Use a small table and keep it the same in every contest, so you can compare your guesses against results later.

Rules for good tags:

• The difficulty is about your own time, not about the contest as a whole. A problem is "easy" if you believe you can code and test it in about one fifth of the contest.
• The topic is a guess. Write it anyway, because a wrong topic guess is quick to catch when you start.
• The first idea can be a single sentence. If you have none, write "none" and do not invent one.

Using solve counts without trusting them

Many contest platforms show how many competitors have solved each problem. This is a useful signal, but it is easy to misread.

The number is a count of solves so far. Early in a contest, the count mostly reflects the fastest competitors, and they usually solve the easy problems first. A problem with ten solves at minute 20 may simply be the easiest one. The same problem could end with two hundred solves. A problem with zero solves at minute 20 may be hard, or it may be a problem most people have not opened yet.

Use the count as a tie-breaker and a sanity check:

• If your own estimate says "medium" and the count says "almost nobody has solved it after an hour", check whether you misread a constraint.
• If your estimate says "hard" and the count is rising fast, check whether the statement is simpler than it looks.
• Do not move a problem to the top only because its count is high. A high count can also come from a trick that you will not spot.

Some contests hide the scoreboard until the end. Read your contest rules before you use this signal, and follow them.

The standard technique: choose a set and an order under a time budget

After the scan you have, for each problem, three numbers:

• v: the points the problem is worth if you solve it.
• t: the minutes you expect to spend on it, including coding and testing.
• q: your chance of solving it in that time, in percent from 0 to 100.

Given a total budget of T minutes, the question is which problems to attempt. A simple answer is to maximise expected points: the sum of v * q / 100 over the problems you choose, with the total minutes at most T.

This is the 0/1 knapsack problem. "0/1" means each problem is either taken once or not taken at all. The knapsack name comes from a thief filling a bag with items of value and weight.

To keep the arithmetic in whole numbers, the program below uses v * q (the points multiplied by 100) and prints that scaled value. Divide by 100 to get expected points.

The dynamic programme works like this. Keep dp[w], the best scaled value you can get using at most w minutes. For each problem in turn, go through the minute budgets from high to low. If taking the problem gives a better value at budget w, update dp[w]. Going from high to low makes sure a problem is used at most once in each pass.

A keep table take[i][w] records where an update happened, so the chosen set can be rebuilt by walking back from the last problem.

The C++ implementation

This is C++17. Compile and run with g++ -std=c++17 -O2 -Wall -o attack_plan attack_plan.cpp.

// attack_plan.cpp: pick the problems to attempt within the time budget,
// maximising expected points, then print the attack order.
// Input:  n T
//         then n lines: v_i t_i q_i
//           v_i = points if solved, t_i = minutes you will spend, q_i = success chance in percent (0..100)
// Output: "scaled S" where S = sum of v_i * q_i over chosen problems (expected points = S / 100)
//         then the chosen problems in attack order, one per line: index v t q
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, T;
    if (!(cin >> n >> T)) return 0;
    vector<int> v(n), t(n), q(n);
    for (int i = 0; i < n; i++) cin >> v[i] >> t[i] >> q[i];
 
    // 0/1 knapsack over minutes. dp[w] = best scaled value using at most w minutes
    // after the problems processed so far. take[i][w] remembers whether problem i
    // improved dp[w], so the chosen set can be rebuilt.
    vector<long long> dp(T + 1, 0);
    vector<vector<char>> take(n, vector<char>(T + 1, 0));
    for (int i = 0; i < n; i++) {
        long long gain = (long long)v[i] * q[i];
        for (int w = T; w >= t[i]; w--) {
            if (dp[w - t[i]] + gain > dp[w]) {
                dp[w] = dp[w - t[i]] + gain;
                take[i][w] = 1;
            }
        }
    }
 
    vector<int> chosen;
    int w = T;
    for (int i = n - 1; i >= 0; i--) {
        if (take[i][w]) {
            chosen.push_back(i);
            w -= t[i];
        }
    }
 
    // Attack order: higher success chance first, then shorter time, then input order.
    sort(chosen.begin(), chosen.end(), [&](int a, int b) {
        if (q[a] != q[b]) return q[a] > q[b];
        if (t[a] != t[b]) return t[a] < t[b];
        return a < b;
    });
 
    cout << "scaled " << dp[T] << "\n";
    for (int i : chosen) {
        cout << i << " " << v[i] << " " << t[i] << " " << q[i] << "\n";
    }
    return 0;
}

A second program brute forces every subset of problems. It is slow, but it is simple enough to be obviously correct, so it is the check you run against the fast one.

// attack_plan_brute.cpp: try every subset of problems (n <= 20) and print the best scaled value.
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, T;
    if (!(cin >> n >> T)) return 0;
    vector<int> v(n), t(n), q(n);
    for (int i = 0; i < n; i++) cin >> v[i] >> t[i] >> q[i];
 
    long long best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        long long minutes = 0, value = 0;
        for (int i = 0; i < n; i++) {
            if (mask >> i & 1) {
                minutes += t[i];
                value += (long long)v[i] * q[i];
            }
        }
        if (minutes <= T) best = max(best, value);
    }
    cout << "scaled " << best << "\n";
    return 0;
}

I compiled both with g++ -std=c++17 -O2 -Wall and generated 500 random inputs with 1 to 10 problems, budgets from 1 to 60 minutes, points from 1 to 30, minutes from 1 to 25 and chances from 0 to 100. The fast program and the brute force printed the same scaled value on all 500 inputs. This tested the code on small inputs only. It does not prove the code is fast enough for the largest limits in a real contest.

Worked example on a small input

Here is a six-problem sheet with a 30-minute budget. Each line is v t q.

6 30
10 10 90
20 15 50
8 5 80
12 20 40
5 8 100
9 12 60

Running the program gives:

scaled 2540
0 10 10 90
2 8 5 80
1 20 15 50

Read the output this way. The scaled value 2540 means expected points of 25.40. The chosen problems are indices 0, 2 and 1, which take 10 + 5 + 15 = 30 minutes, exactly the budget. They are listed in attack order: problem 0 has the highest chance (90 percent), then problem 2 (80 percent), then problem 1 (50 percent). The brute force program prints scaled 2540 on the same input, so the two agree.

Check the arithmetic by hand once. Problem 0 gives 10 * 90 = 900, problem 2 gives 8 * 80 = 640, and problem 1 gives 20 * 50 = 1000. The sum is 2540. One tempting swap is to replace problem 2 with problem 4 (5 points, 100 percent, 8 minutes), but then the total minutes are 10 + 15 + 8 = 33, which is over budget. The knapsack checks every such combination for you. A greedy rule, which takes problems one at a time by a single score, can miss the best combination, as practice problem 2 shows.

Complexity

Time is O(n * T): for each of the n problems the loop runs up to T times. Memory for the keep table is also O(n * T) bytes, because each entry is one byte. For 20 problems and a 300-minute budget that is 6,000 entries, trivial. For 100 problems and 10,000 minutes it is one million entries, still fine. Very large budgets or many problems need a different plan, and the brute force program is not an option at all beyond about 20 problems.

Worked original problem: the six-problem mock set

Here is a mock set. The six summaries below were written for this lesson. They are not taken from any contest. They describe what the problem asks, without limits, and your own scan would produce the same kind of summary.

Your scan would give, for an attack window of 150 minutes, the following estimates. These are the numbers you would fill in yourself.

Write this as input, with the budget T = 150 on the first line:

6 150
5 10 95
10 30 60
15 45 40
10 25 70
20 60 25
8 20 85

Running ./attack_plan on it gives:

scaled 3055
0 5 10 95
5 8 20 85
3 10 25 70
1 10 30 60
2 15 45 40

The brute force program also prints scaled 3055. The chosen set is A, F, D, B and C, using 10 + 20 + 25 + 30 + 45 = 130 minutes. Problem E is left out: its expected value is 20 * 25 / 100 = 5 points for 60 minutes, and the other problems give more points for the time.

The one-line reasons for the attack order are where your own judgement enters. Here is a set of reasons that matches the program's order, with the points per minute of expected value (v * q / 100 divided by t):

• A, 95 percent chance and 10 minutes: the highest rate, 4.75 expected points per 10 minutes, and the statement is a single pass.
• F, 85 percent chance and 20 minutes: a linear scan with one idea, about 3.4 points per 10 minutes.
• D, 70 percent chance and 25 minutes: a standard prefix structure, about 2.8 points per 10 minutes.
• B, 60 percent chance and 30 minutes: a split with a known cost, about 2.0 points per 10 minutes.
• C, 40 percent chance and 45 minutes: a graph count with a modulus, the risk is a wrong path rule, about 1.3 points per 10 minutes.
• E is not attempted: 5 expected points for 60 minutes, the lowest rate on the sheet.

Notice that the ordering rule in the program is "chance first", not "rate first". For this set the two agree, but they can differ. If you want the order to follow the rate instead, change the sort key to compare v * q / t. Your choice is a judgement, so state it in your notes.

Common mistakes

Solving while scanning. The symptom is a scan that runs past 20 minutes with one problem half-coded. Fix it with a timer and a rule: the scan ends when every problem has a tag and a line of reason.

Trusting the first idea. The first idea you write is a guess. If you start coding it and find a counterexample in ten minutes, the tag was wrong. Update the tag and move on, do not defend it.

Picking by points only. A 20-point problem that needs 60 minutes and has a 25 percent chance is worth less than a 10-point problem you can finish in 20 minutes. Put points, time and chance in the same calculation.

Overrating a long statement. Long statements often describe a simple task with a lot of text. Count the constraints and the sample outputs before you decide a problem is hard.

Misreading a limit. The symptom is a solution that is correct on the sample but times out, because n was 200000 and you planned for 2000. Write the limit in the tag column, next to the difficulty.

Reading the solve count as a verdict. A count is a fact about the past, not a judgement about the problem. Use it as a second opinion.

Mixing the table and the code. If you write the knapsack with v and t swapped, you get a plan that looks reasonable and is wrong. Run a brute force on your own sheet and compare the two numbers before you trust the order.

Prompt to use with an AI model for a second opinion on tags

Use this only as a second opinion on your own tags, and only after you have written your own. Paste the statement, not a link.

Here is a contest problem statement and its limits. Do not write code.
1. Give a difficulty rating (easy, medium or hard) for a competitor with my level: [your level].
2. Name the one or two topics the solution most likely uses.
3. List the constraints that rule out a slow approach, and say which approach they rule out.
4. Say which part of the statement you are least sure about.
Statement:
[paste the statement here]

A good answer names specific constraints and gives a reason for the difficulty rating. It also admits uncertainty on a named part of the statement. Check it against the limits yourself. Models often rate a short statement as easy when the difficulty sits in one hidden condition, and they can state a topic with confidence when the topic is only a guess. If the answer does not mention any constraint, ask again and require it.

Exercise on your own machine

Set up a working folder, write the two programs from this lesson, and run them on your own sheet.

1. Create the folder and save attack_plan.cpp and attack_plan_brute.cpp from this page.
2. Compile both with g++ -std=c++17 -O2 -Wall.
3. Write the mock set above as mock.txt, run ./attack_plan < mock.txt, and check that the first line matches scaled 3055.
4. Change problem E from 25 to 60 percent. Run again. Write one sentence saying whether E is now attempted and why.
5. Write your own six-problem sheet from six real problems you have solved in the past. Estimate v, t and q honestly, run both programs, and confirm they print the same first line.

The output will be the same on any machine, because the program prints only integers. If your compiler warns, fix the warning before you trust the result.

Practice problems

1. Budget change. With the mock set and T = 100, which problems are attempted, and what is the scaled value?

Show the answer

Problems A, F, D and B, in that order, with scaled 2455. The chosen set takes 10 + 20 + 25 + 30 = 85 minutes. Adding C (45 minutes) would make 130, which is over 100. The brute force program also prints scaled 2455.

2. A greedy rule that fails. Sort by expected points per minute (v * q / t), then take problems in that order while they fit. Find a small sheet on which this rule gives a lower value than the knapsack, and state both values.

Hint: use a problem whose rate is the highest but which takes most of the budget, and two smaller problems with rates just below it.

Show the answer

Use T = 10 and three problems: v=6, t=6, q=100 (rate 100 per minute, value 600), and two copies of v=5, t=5, q=99 (rate 99 per minute, value 495 each). The rate rule takes the first problem, has 4 minutes left, and cannot fit either other problem. Its value is 600. The knapsack picks the two smaller problems for 990. Input and output:

3 10
6 6 100
5 5 99
5 5 99

scaled 990
1 5 5 99
2 5 5 99

The brute force program prints scaled 990 too.

3. The loop direction bug. Change the inner loop of attack_plan.cpp to go from low to high minutes, as for (int w = t[i]; w <= T; w++). Run it on one problem with v=10, t=10, q=100 and budget T=20. Explain what is wrong.

Show the answer

The program prints scaled 2000 instead of scaled 1000. Going upward lets the same problem update dp after it has already been used, so it is counted twice. The correct version goes from high to low, so each problem is used at most once per pass.

4. Chance changes the answer. For the mock set with T = 150, change E's chance from 25 to 60 percent. What is the new value, and does E change position?

Show the answer

E is now taken, and the scaled value is 3655. The chosen set is A, F, D, B and E, using 10 + 20 + 25 + 30 + 60 = 145 minutes. E comes last in the order because its chance (60) is tied with B's, and B takes less time, so B comes first.

5. Your own tags. Pick three problems from a past set. For each, write the tag line (difficulty, topic, first idea, risk) without solving them. Then solve one, and compare your tag with what happened.

Show the answer

There is no single correct tag. A good answer states the constraint it used to decide, for example "n up to 200000 so I need about linear time", and records whether the tag was right. If the tag was wrong, write down which sentence or limit you misread.

Checklist

• Set a timer for the scan, and stop it at 15 minutes.
• Read every statement and write the limits next to each problem.
• Tag each problem with difficulty, topic, a first idea, and a risk note.
• Treat the solve count as a second opinion, and check the contest rules on whether you may use it.
• Estimate points, minutes and chance for each problem, and run the knapsack check on the sheet.
• Write one line of reason for each problem in the attack order.
• Keep the order flexible: move a problem down as soon as its tag proves wrong.

Summary

The scan tells you where to start and what to skip. Write the tags on paper, use the solve counts only as a check, and let the budget and the chances decide which problems are worth your time.