Contest Strategy & Time Management

Contest Strategy & Time Management | Algoryva

Intuition

A contest is a clock and a list

Two hours, six problems, and each problem has a different value and a different expected solving time. Most competitors spend the first minutes on the problem that looks easiest, which is not always the same as the one that earns the most points for the time it takes.

The structure is familiar. You have a fixed budget (the minutes), and each item (a problem) costs time and returns points. Choosing which items to take is exactly the 0/1 knapsack problem: each problem is taken whole or skipped.

The concept

Points per minute, and why it can mislead

The tempting rule is greedy: rank problems by points per minute, then take them in that order while time remains. It is quick, easy to explain, and often close to right.

Greedy by ratio is an approximation. It works when the problems divide the time finely, so no single large problem blocks the rest.
It can fail when the big, high-value problem takes a large share of the clock. A small problem with a good ratio can then leave too little time for a combination that is worth more.
The exact answer comes from the knapsack table: the best total for every time t, built one problem at a time. It considers every combination without listing them.
The table is exact but costs time proportional to the number of problems times the number of minutes, so it suits contests, where both numbers are small.

Worked by hand

Three problems and fifty minutes

Take three problems: (10 minutes, 60 points), (20 minutes, 100 points) and (30 minutes, 120 points). Their ratios are 6, 5 and 4 points per minute.

Greedy by ratio takes the 10-minute problem (60 points) and the 20-minute one (100 points). That uses 30 minutes and earns 160 points. The 30-minute problem then no longer fits in the 20 remaining minutes.

The best plan is the 20-minute and 30-minute problems together: 50 minutes exactly, for 220 points. Greedy left 20 minutes unused and lost 60 points. The table below shows the best total for each set of problems and each time budget.

Plan	Minutes	Points
10 + 20 (greedy)	30	160
20 + 30 (best)	50	220
10 + 30	40	180
all three	60	too long

See it move

Filling the table for fifty minutes

Each row adds one problem; each column is a time budget from 0 to 50 minutes. A cell holds the best points you can get in that many minutes. Follow the bottom-right cell back: the cells where the value changed from the row above tell you which problems were taken.

Implementation

Greedy, then the exact table

The plan: a greedy function that sorts by ratio, and a table function that is exact. Both run on the same three problems so the difference is visible.

Plan in plain steps

pseudocode

greedy: sort by points/minutes descending; take each problem that still fits
exact: best[t] = points achievable in t minutes; for each problem, go through t downwards and take the better of skip and take

python

def greedy_by_ratio(problems, minutes):
    total_points, used = 0, 0
    for m, p in sorted(problems, key=lambda x: x[1] / x[0], reverse=True):
         used + m <= minutes:
            used += m
            total_points += p
     total_points

 (problems, minutes):
    best = [] * (minutes + )
     m, p  problems:
         t  (minutes, m - , -):
            best[t] = (best[t], best[t - m] + p)
     best[minutes]

problems = [(, ), (, ), (, )]
((problems, ))   
((problems, ))   
(([(, ), (, )], ))   
(([(, ), (, )], ))   
(([(, )], ))

Complexity

The cost of each plan

With n = 6 problems and T = 180 minutes, the table takes about 1,000 updates, which is trivial. The greedy rule is cheaper, but for a contest the exact plan is affordable, and it is the safer choice when you are unsure.

greedy by ratio

time O(n log n)space O(n)

sorting dominates; a single pass then takes or skips each problem.

exact knapsack table

time O(n · T)space O(T)

for each of n problems, update every time budget up to T. The space is one row, reused.

Edge cases

Cases that change the plan

A problem longer than the whole contestIt can never be taken. The table handles this naturally, because the loop never reaches it.
Two problems with equal ratioEither order gives the same greedy total, but the exact table may prefer the one that fits better with the rest.
Time left over at the endA plan that leaves slack is not wrong, but compare it with the table: unused minutes are often a sign that a larger problem was skipped.
Problems that depend on each otherThe knapsack model assumes independent problems. If you must solve A before B, the choice is a chain, not a set, and the model needs changing.

Common mistakes

Common mistakes in contest planning

Starting to code the first problem before reading all of them.
Spend the first few minutes reading every statement. The best plan depends on what you see, and reading is cheap compared with a wasted hour.
Treating points per minute as the whole rule.
It is a heuristic. Check the table for the final decision when the numbers are close.
Spending the whole budget on one problem you are stuck on.
Set a time limit per problem. Leave a stuck problem and return if time allows; a partial solution earns nothing, but the next problem may earn full points.
Ignoring wrong-submission penalties.
Add the expected penalty to the time cost. A problem with many attempts is more expensive than its statement suggests.

Recognize it in a contest

Recognising a contest-planning problem

Whenever a budget and a list of costed options appear together, the knapsack table is the reliable tool, and greedy is a fast first guess.

Reach for it when the problem says or implies

A fixed budget (time, money or capacity) is shared by several tasks, each with a cost and a value.
Each task can be done or skipped, and doing it once is enough.
The question asks for the best total value that fits the budget.

Look elsewhere when

If the tasks depend on each other in a fixed order, the set model is wrong; plan a sequence instead.
If tasks can be split into parts that earn partial value, the problem is fractional knapsack, where taking by ratio is exactly optimal.

Worked problem

Worked problem: a practice session

The problem

A coach has 30 minutes for a practice session and three drills: (15 minutes, 50 points), (10 minutes, 30 points), (20 minutes, 55 points). Choose the drills that maximise the points within 30 minutes.

Ratios are 3.33, 3 and 2.75 points per minute. Greedy takes the first two drills: 25 minutes, 80 points.
The table checks the alternatives. The 20-minute drill with the 10-minute drill uses 30 minutes for 85 points, which is better.
The exact answer is 85 points. Greedy missed it because the first choice used half the session and blocked a better pair.

python

def best(drills, minutes):
    dp = [0] * (minutes + 1)
    for m, p in drills:
        for t in range(minutes, m - 1, -1):
            dp[t] = max(dp[t], dp[t - m] + p)
    return dp[minutes]

print(best([(15, 50), (10, 30), (20, 55)], 30))   # 85

Wrap-up

Remember this

A contest is a knapsack problem: a fixed time budget and problems that are taken whole or skipped.
Ranking by points per minute is a fast heuristic, but it can leave time unused and lose points.
The exact knapsack table finds the best set for a given budget, in time proportional to problems times minutes.
Good planning reads all problems first, time-boxes each one, and accounts for penalties.

Cheat sheet

Model: 0/1 knapsack: each problem is taken whole or skipped, with a time budget
Greedy: sort by points per minute; fast, but not always optimal
Exact: dp[t] = best points in t minutes; go t downwards; O(n · T)
Practice: read everything first; time-box each problem; add expected penalties to the costs

Top traps to avoid

Starting to code the first problem before reading all of them.
Treating points per minute as the whole rule.
Spending the whole budget on one problem you are stuck on.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What does a points-per-minute greedy rule do well, and where can it fail?
2.With the problems (10,60), (20,100), (30,120) and 50 minutes, what is the best total?
3.Greedy by ratio on the same problems and 50 minutes earns how many points?
4.What is the time cost of the exact knapsack table for n problems and T minutes?
5.Which situation does NOT fit the knapsack model of a contest?
6.In a 3-hour contest, why is it wise to read every problem statement early?
7.Why set a time limit before you give up on a problem you are stuck on?
8.When is a brute-force solution a good first submission?
9.Why check your solution on the sample input before submitting?
10.Two solutions disagree on a random test. What is the best next step?
11.Why are edge cases like n = 1 or all values equal worth checking?
12.What does checking complexity against the limit tell you?
13.Why keep a record of your mistakes after a contest?
14.A greedy rule looks right during a contest. What should you check before trusting it?
15.Why write a short plan on paper before you code?