Greedy -> Prefix Constraints

Greedy selection under prefix or feasibility quotas, usually proved with exchange arguments and heap maintenance.

• Topic slug: greedy/prefix-constraints
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 3
• Repo companion pages: 3
• Curated external problems: 8

Microtopics

• prefix-quota
• feasible-prefix
• heap-greedy
• exchange-proof
• offline-selection
• representative-reconstruction

Learning Sources

Source	Type
OI Wiki greedy	Reference
Principles of Algorithmic Problem Solving	Reference
Competitive Programmer's Handbook	Reference

Practice Sources

Source	Type
CSES Problem Set	Practice
USACO contest archive	Practice
IOI tasks archive	Practice

Repo Companion Material

Material	Type
Greedy overview	area guide
Lemonade Line note	anchor note
Prefix Sum Addicts note	anchor note

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Lemonade Line	USACO 2018 US Open Silver	Easy-Medium	-	-	-	Sort+Greedy; Threshold	keep a valid prefix by descending willingness

Binary Construction

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Two Binary Strings	Codeforces	Easy	Construction	Greedy-Construction	String Scanning; Invariants	Binary-Strings; Prefix-Conditions	A constructive greedy where valid prefixes constrain how the final string can be assembled.

Extremal Constraints

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Prefix Min and Suffix Max	Codeforces	Easy	Prefix-Extrema	Greedy-Check	Suffix Extrema	Prefix-Min; Suffix-Max	A nice prefix/suffix constraint problem that rewards tracking the right extrema at the right time.

Prefix Extrema

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Prefix Max	Codeforces	Easy	Prefix-Extrema	Greedy-Check	Prefix Maxima; Comparisons	Prefix-Max; Arrays	A crisp prefix-max problem where the greedy invariant is both simple and central.

Prefix Feasibility

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Prefix Sum Addicts	Codeforces	Easy	Prefix-Feasibility	Greedy-Check	Prefix Sums; Parity Reasoning	Prefix-Sum; Construction	The prefix-sum structure is the whole problem, so it is a nice fit for prefix-constrained greedy reasoning.

Prefix Monotonicity

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Keep it Beautiful	Codeforces	Easy	Stateful-Greedy	Greedy-Check	Sequence Invariants; Two-State Logic	Binary-Array	A good example of maintaining a global prefix condition while processing the sequence online.

Prefix Trimming

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Remove Prefix	Codeforces	Easy	Prefix-Invariant	Greedy-Check	Arrays; Set Membership	Construction	A very direct prefix-invariant greedy where the answer is determined by the first repeated prefix pattern.

Structured Prefix Cleanup

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Binary Removals	Codeforces	Easy	Prefix-Structure	Greedy-Check	String Scanning; Prefix/Suffix Reasoning	Binary-String	A compact prefix-constraint problem where the feasibility check is driven by a simple greedy invariant.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
LEMONADELINE	Lemonade Line	primary	easy	descending tolerance order; prefix feasibility count; minimize accepted arrivals	Note	Code
PREFIXSUMADDICTS	Prefix Sum Addicts	primary	medium	suffix prefix differences; sorted sequence feasibility; first block capacity bound	Note	Code
VODIVIDE	Chia phần	primary	hard	prefix quota greedy; heap maintenance; pair reconstruction	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py