Prove
LiveProof-of-Work · Oct–Nov: every verified proof counts. 14 days leftAll outcomes
Learning

IOI: Algorithms and Complexity

10 weeks · 4 milestones

The heart of the IOI: choosing an algorithm and data structure that is fast enough, from greedy and dynamic programming to graph algorithms and segment trees, and judging its running time. Diagnostic, topic practice, timed problems and a review, with free material only.

Part of: IOI prep · Proves for: College Applications

Milestone map

Milestone map

4 milestones

Try a first set of Algorithms and Complexity problems

about 3 weeks

Pick problems from the latest IOI tasks (one competition day of three tasks) and try them before you study, so you know where you stand. Give yourself the contest's own time for each problem: 5 hours for three tasks, so about 100 minutes a task. Write every solution yourself. Never copy an official solution.

Proof required

Upload your own written attempts (scans or typed), marked by you as solved, partly solved or stuck, and a short note on where you got stuck.

What gets checked

  • Each attempt shows your own working, including the dead ends.
  • Each problem is marked solved, partly solved or stuck.
  • Nothing is copied from an official or published solution.

Common mistakes

  • Reading the solution before a real attempt.
  • Trying only one problem.

Powstik Guide

Your first written attempts at Algorithms and Complexity problems.

Steps

  1. Choose three to five past problems.
  2. Time yourself as the contest does.
  3. Write everything down, even ideas that fail.
  4. Only then compare with the official answer.
  5. Mark each one solved, partly solved or stuck.

Template

Problem (contest, year, number):
My attempt:
Result (solved / partly / stuck):
Where I got stuck:

What gets sent back

  • A copied solution.
  • No working shown.

Resources

Foundationstart here

What a verifier looks for

  • Did the learner write these solutions themselves (their own wording and working)? Send it back if it is a copy of an official or published solution.
  • Is each problem named by contest, year and number (not copied out)?
  • Does the note say where the learner got stuck?
  • Send it back if it shows a registration, roll, application or ID number.

You'll sign in first, then come straight back here.

Study Algorithms and Complexity topic by topic

about 3 weeks

Work through the Algorithms and Complexity topics, weakest first: Basic algorithmic analysis, Algorithmic strategies (greedy, divide and conquer, dynamic programming), Algorithms on integers, arrays, strings and graphs, Data structures (heaps, union-find, segment and Fenwick trees, balanced trees), Geometric algorithms. Study each idea, then solve practice problems that use it. Self-check: past IOI tasks on oj.uz.

Proof required

Upload a topic tracker (topic, problems tried, problems solved) and your own written solutions to at least two problems per topic.

What gets checked

  • Every topic in the list has problems tried.
  • At least two full written solutions per topic, in your own words.
  • Each solution says which idea made it work.

Common mistakes

  • Collecting techniques without solving problems.
  • Skipping the topics you find hard.

Powstik Guide

A topic tracker and your own solutions for Algorithms and Complexity.

Steps

  1. Rank the topics by your first attempts.
  2. Study the weakest topic from the linked material.
  3. Solve problems that use it.
  4. Write up two solutions in full.
  5. Move to the next topic.

Template

Topic tracker
Topic | Problems tried | Solved | Date

Solution
Problem (contest, year, number):
Key idea:
Full solution:

What gets sent back

  • Solutions copied from a book or a forum.
  • A tracker that skips topics.

Resources

Foundationstart here

Depthgo deeper

What a verifier looks for

  • Did the learner write these solutions themselves (their own wording and working)? Send it back if it is a copy of an official or published solution.
  • Does the tracker cover every topic named?
  • Does each solution reach a full, checked answer?
  • Send it back if it shows a registration, roll, application or ID number.

You'll sign in first, then come straight back here.

Solve timed Algorithms and Complexity problems

about 3 weeks

Solve Algorithms and Complexity problems against the clock, from past IOI tasks from the official archive. Keep to the contest's own time: 5 hours for three tasks, so about 100 minutes a task. Do at least three timed sessions on different days.

Proof required

Upload your own written work from each timed session (at least three), with the date, the problems (contest, year, number) and the time taken.

What gets checked

  • At least three timed sessions, on different days.
  • The work is what you wrote in the session, not a tidied copy.
  • Each session notes what you would try next for the unsolved ones.

Common mistakes

  • Stopping the clock to look something up.
  • Only choosing problems you have seen before.

Powstik Guide

Three or more timed Algorithms and Complexity sessions, in your own writing.

Steps

  1. Pick unseen problems.
  2. Set a timer: 5 hours for three tasks, so about 100 minutes a task.
  3. Work with only what the contest allows.
  4. Stop when the time is up.
  5. Compare with the official answer and note the gap.

Template

Timed session
Date:
Problems (contest, year, number):
Time taken:
Solved / partly / stuck:
What I would try next:

What gets sent back

  • Fewer than three sessions.
  • A copied solution.

Resources

Foundationstart here

What a verifier looks for

  • Did the learner write these solutions themselves (their own wording and working)? Send it back if it is a copy of an official or published solution.
  • Are there three sessions with dates and times?
  • Is the work the raw session work?
  • Send it back if it shows a registration, roll, application or ID number.

You'll sign in first, then come straight back here.

Review Algorithms and Complexity and rewrite your best solutions

about 3 weeks

Go through every Algorithms and Complexity problem you missed. Sort the misses by topic and by reason. Then rewrite three solutions cleanly, as you would hand them in, and ask someone who knows the subject to check them.

Proof required

Upload your review (misses by topic and by reason) and three clean solutions written by you. A confirmer who knows the subject checks that they are right and that they are yours.

What gets checked

  • The review counts misses by topic and by reason.
  • Three clean solutions, each complete and correct.
  • Every solution is in your own words and working.

Common mistakes

  • Rewriting the official solution instead of your own.
  • A review with no counts.

Powstik Guide

A Algorithms and Complexity review and three clean solutions of your own.

Steps

  1. List every problem you missed.
  2. Count the misses by topic and by reason.
  3. Pick three problems you now understand.
  4. Write each solution cleanly from memory.
  5. Ask someone who knows the subject to check them.

Template

Review
Misses by topic:
Misses by reason:

Clean solution
Problem (contest, year, number):
Solution:

What gets sent back

  • A copy of an official or published solution.
  • A solution with a gap in the argument.

Resources

Foundationstart here

What a verifier looks for

  • Did the learner write these solutions themselves (their own wording and working)? Send it back if it is a copy of an official or published solution.
  • Are the three solutions complete and correct?
  • Does the review count misses by topic and by reason?
  • Send it back if it shows a registration, roll, application or ID number.

You'll sign in first, then come straight back here.