Choosing Algorithm Families from Constraints and Input Structure

Hello. In the previous lesson, you learned to turn constraints into a realistic complexity budget, including the crucial distinction between per-test and total work across all test cases. That budget eliminates algorithms that cannot possibly pass.

This lesson takes the next step: using the structure of the input and requested output to generate a short list of plausible algorithm families before coding. The objective is not to guess “the intended trick” immediately. It is to make a disciplined shortlist, where every candidate both fits the constraints and exploits a concrete property of the problem.

---

From a complexity ceiling to an algorithm shortlist

Constraints tell you what is impossible. Structure tells you what may work.

Suppose a problem has $n\le 2\cdot 10^5$. From the previous lesson, you should immediately reject a routine $O(n^2)$ scan of all pairs or all subarrays. But that still leaves many possibilities:

• sorting and scanning;
• prefix sums;
• frequency counting;
• two pointers;
• a Fenwick tree or segment tree;
• graph traversal;
• dynamic programming with a small state;
• binary search with a fast feasibility check;
• greedy construction.

The problem statement must contain enough additional information to distinguish among them. Treat its details as evidence.

A useful mental model is:

Constraints set the budget; input structure selects the operations.

For example, “find the best contiguous segment” may point toward several different families depending on what else is promised:

Additional property	Plausible family
All values are nonnegative	Two pointers or sliding window
Many fixed range-sum queries	Prefix sums
Point updates occur between queries	Fenwick tree or segment tree
Values can be negative and the condition compares prefix sums	Prefix sums plus ordered structure or coordinate compression
$n\le 3000$	Perhaps an $O(n^2)$ dynamic program or enumeration

The word subarray alone does not choose the algorithm. The surrounding mathematical conditions do.

The guide’s keyword lists are useful, but there is an important refinement for harder Codeforces problems: a keyword suggests a family; a precise property justifies it.

“Minimum” does not automatically mean greedy.
“Subarray” does not automatically mean two pointers.
“Graph” does not automatically mean Dijkstra.
“Many queries” does not automatically mean segment tree.

Before coding, be able to finish this sentence:

“I am considering this algorithm family because the problem guarantees ________, which lets me maintain or compute ________ efficiently.”

If you cannot fill both blanks concretely, you have an association, not yet an algorithmic idea.

---

The evidence checklist: what to extract from a statement

During the first read, separate the statement into a few kinds of evidence. This takes little time and prevents “last-topic-learned bias,” where every problem starts looking like a segment tree, DP, or graph.

1. Shape of the objects

Ask what the input fundamentally is:

• Array, string, or sequence: ordering may matter; contiguous segments, prefixes, suffixes, and relative positions become available.
• Set, multiset, or permutation: perhaps only values and frequencies matter; a permutation also gives uniqueness.
• Grid: movement, adjacency, geometry, and row or column structure may matter.
• Graph or dependency relation: reachability, components, shortest paths, or topological order may be relevant.
• Intervals or events: sorting by endpoints, sweeps, and offline processing become candidates.

A permutation, for instance, is not merely “an array whose values happen to be distinct.” It supports an inverse-position array:

$$\mathrm{pos}[x]=\text{the index containing value }x.$$

That enables constant-time conversion between “where is this value?” and “which value is here?” Many permutation problems become about positions rather than values.

2. What changes, and what is queried?

This is one of the strongest filters in contest problems.

Operation pattern	First candidates
Static array, one final answer	Sorting, prefix sums, greedy, DP
Static array, many range queries	Prefix sums, sparse table, offline sorting
Point updates plus range queries	Fenwick tree, segment tree
Range updates plus point queries	Difference array, Fenwick tree
Range updates plus range queries	Lazy segment tree or paired Fenwick trees
Queries can be reordered	Offline sweeps, Mo’s ordering, divide-and-conquer methods

The same requested quantity can demand radically different tools. Range sums on a fixed array are solved with prefix sums; allowing updates invalidates the simple prefix-sum solution because every later prefix could change.

3. Order, monotonicity, and sign restrictions

Look for promises that reduce the number of possibilities you must examine.

Common high-value properties include:

• the array is sorted, or you are allowed to reorder it;
• all values are nonnegative or positive;
• endpoints only move forward;
• a threshold condition becomes easier as a parameter increases;
• values lie in a small bounded range;
• all edge weights are $0$ or $1$, or all are equal;
• choices have an order such as earliest deadline or smallest available value.

These properties often justify an algorithm that would be invalid on unrestricted inputs.

For instance, if every array value is positive, extending a window can only increase its sum. That is exactly the kind of monotonic behavior that can make a sliding-window process viable. If negative values are permitted, extension may decrease the sum, and the same pointer movement can become unsound.

4. The requested form of the answer

The output is also evidence:

• Count all valid objects: contribution counting, prefix-frequency methods, combinatorics, or DP.
• Find one valid construction: greedy or invariant-based constructive methods.
• Minimize a maximum or maximize a minimum: binary search on an answer may be plausible, provided feasibility is monotone.
• Shortest route or minimum number of moves: a graph model, BFS, $0$-$1$ BFS, or Dijkstra may be appropriate depending on edge costs.
• Number of ways, minimum cost, maximum score over repeated choices: dynamic programming becomes a candidate if subproblems overlap.

Do not confuse the answer’s wording with proof of a technique. “Minimum possible maximum” suggests binary search only after you can define a yes-or-no condition that remains true when the candidate answer becomes more permissive.

---

A three-filter method for candidate families

Use the following filters in order. They turn an intimidating statement into a manageable shortlist.

Filter 1: Can the family fit the budget?

Use the relevant bounds from the previous lesson. Eliminate families whose best normal formulation is too expensive.

For an array of size $2\cdot 10^5$:

• enumerate all pairs: reject;
• enumerate all subarrays: reject;
• sort once and scan: plausible;
• process each element with a logarithmic data structure: plausible;
• maintain a constant number of pointers: plausible;
• subset DP over all masks: reject.

For $n\le 20$, the conclusion can reverse: a bitmask DP with

$$O(n{2}^n)$$

states and transitions may be much more plausible than searching for an elaborate greedy proof.

Filter 2: Does the structure enable the family?

A complexity-compatible technique still needs a structural reason.

Candidate family	Structural evidence needed
Two pointers	A monotone condition that makes discarded positions safely irrelevant
Prefix sums	An operation expressible as a difference of prefix states
Sorting plus scan	Order may be changed, or sorting preserves the relevant relationships
Frequency array	Value range is small enough to allocate directly
Hash map	Keys may be large or sparse; expected-time hashing is acceptable
BFS	All graph edges have equal cost
$0$-$1$ BFS	Every edge cost is $0$ or $1$
Dijkstra	Edge weights are nonnegative
Bitmask DP	The essential state is a subset and $n$ is small
Binary search on answer	Feasibility is monotone in the searched value
Greedy	You can identify an exchange, stays-ahead, or invariant argument

This table is not a list of rules to memorize in isolation. It is a list of proof obligations. Each structural promise tells you what must eventually be proved.

Filter 3: Can you name the maintained information?

A candidate becomes much more concrete when you can state what it would maintain.

Examples:

• Two pointers: current interval, its sum, and perhaps frequency counts.
• Prefix-sum counting: how many times each prior prefix state has occurred.
• Fenwick tree: aggregated information over prefixes.
• Dijkstra: best currently known distance to each state.
• Dynamic programming: the answer for each compressed subproblem state.
• Greedy construction: the unresolved positions and the invariant preserved so far.

If you can name neither the state nor the update rule, do not code yet. Continue analyzing the transformation.

---

Example: a subarray condition changes the shortlist

Consider the following family of tasks:

Given an array of length $n\le 2\cdot 10^5$, find the maximum length of a contiguous subarray whose sum is at most $K$.

The word “subarray” tempts you toward a nested loop. Constraints eliminate that:

$$O(n^2)$$

is unacceptable in the worst case.

Now suppose the statement also guarantees:

$$a_i>0$$

for every $i$.

That positivity is decisive. If a current window has sum exceeding $K$, making the window longer cannot repair it. The left endpoint can be advanced until the sum is valid again. Each endpoint only advances through the array a bounded number of times, making a two-pointer family plausible.

Your contest sketch might be:

$n$ requires near-linear work. Since all elements are positive, the window sum increases when the right endpoint moves right. Maintain a valid window by advancing the left endpoint while its sum exceeds $K$. Two pointers are plausible in $O(n)$.

Now change only one feature: values may be negative.

The old argument collapses. A currently invalid window can become valid by adding a negative value later. Therefore “shrink immediately when the sum exceeds $K$” is no longer justified. You should remove ordinary two pointers from the shortlist and investigate prefix sums with an ordered structure, offline processing, or another transformation appropriate to the exact condition.

This is the discipline to develop:

Do not remember “subarray plus sum means sliding window.” Remember the property that makes a window strategy safe.

The formal monotonicity argument behind two pointers is developed in the next module on array techniques. For now, use it as a screening question: does extending or shrinking the structure change the relevant quantity in a predictable one-directional way?

---

Example: operation types choose the data structure

Suppose a statement gives an array of size $n$ and $q$ operations, with

$$n,q\le 2\cdot 10^5.$$

The phrase “answer range-sum queries” is not enough to choose a data structure. The update model decides.

Static range sums

If there are no updates, define

$$P[i]=\sum _{j=1}^i{a}_j.$$

Then the sum over an interval $[l,r]$ is

$$P[r]-P[l-1].$$

The preprocessing cost is $O(n)$, and every query costs $O(1)$. A segment tree would also work, but it would be unnecessary complexity.

Point updates and range sums

If an operation changes one element, earlier prefix sums are no longer fixed. You need a structure that can update an element and aggregate a prefix or interval efficiently. This makes a Fenwick tree or segment tree a plausible family:

$$O((n+q)\log n).$$

Range updates and range sums

If updates affect whole intervals and queries also request interval sums, a simple Fenwick tree is no longer automatically sufficient. You should consider a lazy segment tree or the appropriate paired-Fenwick formulation.

The key observation is not “use a data structure because $q$ is large.” It is:

The operation set determines what information must stay dynamically correct.

When reading a query problem, write down each operation exactly. A one-word difference between “set,” “add,” “point,” and “range” can invalidate an otherwise familiar solution.

---

Example: the same physical process under different bounds

Constraint changes can require a change of model, not merely a faster implementation.

For modest dimensions $n$ and $m$, the ball’s state consists of a cell and one of a constant number of directions. A simulation can use a bound proportional to the number of states, roughly $O(nm)$.

If dimensions reach $10^9$, even visiting one row or column at a time is impossible. No amount of implementation optimization rescues the simulation. The useful structure is the reflection rule: by imagining reflected copies of the board, a bouncing path can be viewed as a straight path through an expanded grid. That change opens a number-theoretic route.

This is an important contest habit:

• First ask whether direct simulation fits the scale.
• If not, ask what regularity the simulation is hiding: periodicity, symmetry, repeated states, conservation, or a mathematical equation.

Many difficult problems are designed around this transition.

---

A practical pre-coding shortlist

Before implementing, take about one minute to produce a compact note like this:

Objects: static array; values form a permutation.
Scale: $\sum n\le 2\cdot 10^5$, so $O(n\log n)$ is safe; $O(n^2)$ is not.
Requested quantity: count pairs satisfying a positional relation.
Useful structure: each value occurs once, so invert values to positions.
Candidates: sorting by one attribute plus Fenwick tree; offline sweep.
Rejected: direct pair enumeration.
Proof target: explain why the sweep has counted exactly the eligible earlier positions.

This has two benefits:

1. It stops you from coding the first familiar technique that comes to mind.
2. It makes debugging more focused. If the implementation fails, you can ask whether the error lies in the model, the data structure, or the unproven assumption that justified the candidate.

Keep the shortlist small. Usually, two or three families are enough:

• one approach that clearly fits but may be more general;
• one approach that exploits the strongest structural promise;
• occasionally, a brute-force version for tiny inputs, useful later for stress testing.

Avoid maintaining ten vague ideas. The aim is disciplined elimination, not maximal brainstorming.

---

Common selection errors

Choosing from a keyword alone

“Shortest path” does not settle whether to use BFS or Dijkstra. Inspect the edge weights:

• equal edge costs suggest BFS;
• costs only $0$ or $1$ suggest $0$-$1$ BFS;
• general nonnegative costs suggest Dijkstra;
• negative edges require a different analysis.

Sorting without checking what must be preserved

Sorting is powerful because it creates order. But it may destroy information about original indices, adjacency, or chronology. If the condition is about original subarrays, sorting the array usually changes the problem.

Ask: Does the answer depend only on the multiset of values, or on their original order?

Treating “many queries” as “segment tree”

For static range sums, prefix sums are simpler and faster. For idempotent static operations such as minimum or gcd, a sparse table may be suitable. The right structure follows from both the query operation and whether updates occur.

Using DP because there are choices

Many problems have choices but no overlapping subproblems. DP is justified when different decision paths reach the same relevant state and caching that state avoids repeated work. If every state is essentially unique, a greedy, graph, or direct combinatorial approach may be better.

Failing to identify the property that makes an optimization legal

A fast method often depends on an assumption:

• positivity for a particular window process;
• sorted order for binary search;
• nonnegative edges for Dijkstra;
• monotonic feasibility for answer search;
• uniqueness for inverse-position techniques.

Write that assumption down. It is often where an incorrect solution silently fails.

---

Takeaways

A strong pre-coding routine has two stages:

1. Use constraints to eliminate algorithm families that cannot fit the full legal input.
2. Use structure to justify the survivors: object shape, update model, ordering, value restrictions, graph edge costs, and answer form.

The most valuable question is not “Which algorithm does this remind me of?” Instead ask:

“What exact property of this problem makes this algorithm family valid and efficient?”

A plausible shortlist is not yet a proof. In the next lesson, you will sharpen that distinction by separating necessary conditions from sufficient conditions when deriving a solution criterion.