Change the Problem, Not the Algorithm: Transform and Conquer

Quick Revisit

• USE WHEN: direct approach is intractable but a reformulation (compression, complement, duality) reveals a known problem
• INVARIANT: transformed problem is equivalent to original — solution maps back bijectively
• TIME: varies by transformation | SPACE: varies
• CLASSIC BUG: complement counting off-by-one — "total minus bad" fails if "total" is miscounted
• PRACTICE: 08-ladder-mixed

The problem looks impossible. But what if you looked at it differently? Coordinate compression, complement counting, duality -- these are ways to transform a hard problem into one you already know how to solve.

Difficulty: [Intermediate-Advanced]CF Rating Range: 1500-2200 Prerequisites: Problem Pattern Recognition

Contents

• Why Transform?
• Seven Transformations
• How to Spot a Transformable Problem
• Practice Problems

---

Why Transform?

Most competitive programming problems are not original. They are known problems wearing a disguise. The skill isn't inventing a new algorithm — it's stripping away the disguise to reveal a problem you've already solved.

Each transformation below is a lens. Look at your problem through each lens in turn. One of them will make the solution obvious.

Every transformation must prove equivalence. The transformed problem is useful only if its solution maps back bijectively to the original. For each of the seven transformations below, two questions to answer before you trust it:

1. What does it preserve? Order, total count, parity, sum — whatever the algorithm at the next step depends on must survive the transformation.
2. What does it lose? Compression discards distances, modulo discards magnitude, complement requires a clean total. Knowing what is gone tells you which subsequent operations are still legal.

Seven Transformations

1. Coordinate Compression

The situation: values range up to ${10}^9$, but there are only $n\le 2\times {10}^5$ distinct values. You need a segment tree or BIT indexed by value.

The transformation: replace each value with its rank among all values. Sort the distinct values, assign ranks $0,1,\dots ,m-1$. Now you can index a structure of size $m\le n$ instead of ${10}^9$.

vector<int> vals(a.begin(), a.end());
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
for (int &x : a)
    x = lower_bound(vals.begin(), vals.end(), x) - vals.begin();

When it helps: anytime you need an array or tree indexed by value, but the value range is huge and sparse. Inversion counting, range queries by value, BIT-based order statistics.

Example: "Count inversions in an array with values up to ${10}^9$." Compress to $[0,n)$, then use a BIT to count elements already inserted with rank greater than the current element. $O(n\log n)$.

Preserves: strict and non-strict order, equality, count of distinct values. Loses: absolute distances and arithmetic. After compression, you cannot ask "are values $a$ and $b$ within $K$ of each other?" — that requires the original numbers (or compressing to a richer structure that retains gaps).

2. Complement Counting

The situation: "Count the number of subsets / pairs / subarrays satisfying complex condition $C$."

The transformation: count total minus those not satisfying $C$.

$$|\{x:C(x)\}|=|\text{total}|-|\{x:\mathrm{\neg }C(x)\}|$$

When it helps: when the invalid set has a simpler structure. "Count pairs with $gcd>1$" is hard directly, but "total pairs minus pairs with $gcd=1$" uses Euler's totient / Möbius inversion cleanly.

Example: "How many subarrays have at least one element $>K$?" Hard to count directly. Complement: count subarrays where all elements $\le K$. These are contiguous runs of small elements -- count them in $O(n)$ with a simple scan. Subtract from $n(n+1)/2$.

Preserves: the cardinality of the universe and the validity of the partition (good $\bigsqcup$ bad = total). Requires: an exact total count and a precise definition of "bad". The classic bug is miscounting "total" — e.g., $n(n+1)/2$ vs. $n(n-1)/2$ for ordered vs. unordered pairs — and silently producing an answer off by $n$.

3. Difference Array Transform

The situation: perform $q$ operations, each adding a value $v$ to all elements in range $[l,r]$. Then read the final array.

The transformation: maintain a difference array $d$ where $d[i]=a[i]-a[i-1]$. A range-add of $v$ to $[l,r]$ becomes two point updates: $d[l]+=v$, $d[r+1]-=v$. After all operations, recover $a$ via prefix sum.

vector<long long> d(n + 1, 0);
for (auto& [l, r, v] : queries) {
    d[l] += v;
    d[r + 1] -= v;
}
for (int i = 1; i < n; i++) d[i] += d[i - 1];
// d[0..n-1] is now the final array

Complexity: $O(n+q)$ instead of $O(nq)$.

Extension: for range-add followed by range-sum queries, use a BIT on the difference array. For 2D range-add, use a 2D difference array.

Preserves: all per-element values after the prefix-sum recovery; the bijection between difference and value sequences is exact. Loses (during the operation phase): point reads. While the difference array is "open", the per-element values are not directly available — only after the final prefix sum. If the problem interleaves range-add with point-reads, plain difference arrays don't apply; use a BIT on differences instead.

4. Contribution Reframe

The situation: "Compute the sum of $f(\text{subset})$ over all subsets / pairs / subarrays."

The transformation: instead of iterating over subsets and computing $f$, iterate over each element and count its contribution across all subsets that contain it.

$$\sum _{\text{subsets }S}f(S)=\sum _{\text{elements }e}\text{contribution}(e)$$

When it helps: when each element's contribution can be computed independently in $O(1)$ or $O(\log n)$.

Example: "Sum of maximums over all subarrays." For each element $a[i]$, find the nearest greater element to the left (at position $L$) and right (at position $R$) using a monotone stack. Then $a[i]$ is the maximum of exactly $(i-L)\times (R-i)$ subarrays, and its contribution is $a[i]\times (i-L)\times (R-i)$. Total: $O(n)$.

Preserves: the total sum (linearity of summation is exact). Requires: each structure–element incidence is counted exactly once. Equal-valued elements are the danger zone — see the double-counting checklist in 06-contribution-counting-advanced.

5. Graph Dual: Vertex Cover <-> Independent Set

The situation: you need the maximum independent set. That's NP-hard in general. But the graph is bipartite.

The transformation: in bipartite graphs, König's theorem says:

$$\text{max matching}=\text{min vertex cover}$$

And for any graph:

$$\text{max independent set}=n-\text{min vertex cover}$$

So on bipartite graphs: max independent set $=n-$ max matching, which is solvable in polynomial time via Hopcroft-Karp or network flow.

Dual transformations in general:

• Minimum cut $=$ maximum flow (max-flow min-cut theorem)
• Shortest path in primal $\leftrightarrow$ potential function in dual (LP duality)
• Minimum path cover in DAG $=n-$ max matching

These dualities turn "hard" problems into "known" problems. Recognizing the duality is the hard part.

Preserves: the optimal value (by the duality theorem). Loses: the witness — knowing the size of a max matching does not immediately give you the matching itself. Reconstruction often needs a second pass (e.g., alternating-path arguments to recover the independent set).

6. Offline Reordering

The situation: $q$ queries arrive in input order, but answering them in input order requires expensive data structure operations. Answering them in a different order would be much cheaper.

The transformation: read all queries, reorder them, process, then output answers in original order.

Techniques enabled by offline reordering:

• Sort queries by right endpoint: enables sweep-line with a BIT or segment tree
• Mo's algorithm: sort by $(\lfloor l/\sqrt{n}\rfloor ,r)$ for $O((n+q)\sqrt{n})$ range queries
• CDQ divide and conquer: sort by time, then by spatial coordinate
• Parallel binary search: sort by binary search midpoint

Example: "For each query $[l,r]$, count distinct elements." Online requires a persistent segment tree. Offline with Mo's algorithm: $O((n+q)\sqrt{n})$ with trivial code.

Preserves: every query's answer, since you remember the original index. Requires: the problem is offline (you can read all queries before answering any). Interactive / forced-online problems are excluded.

7. State-Space Reduction

The situation: the natural DP state is $(i,j,k)$ with dimensions $n\times n\times n$. Too much memory or time.

The transformation: observe that only the difference $j-k$ matters, not $j$ and $k$ individually. Replace the state with $(i,j-k)$ -- now the DP is $n\times 2n$ instead of $n^3$.

Common reductions:

• "Position and velocity" -> "position and relative velocity" (when only differences matter)
• "Visited set as bitmask" -> "unvisited set" (sometimes one is smaller)
• "Two pointers $(l,r)$" -> "length $r-l$ and one pointer" (when transitions depend on length)
• Profile DP: only store the boundary between processed and unprocessed cells, not the entire grid

Example: "DP over intervals $[i,j]$" -- the state space is $O(n^2)$ intervals. If the DP transition only depends on interval length, collapse to $O(n)$ states by length.

Preserves: the value of every reachable state. Requires: the reduction is sound — i.e., two original states that map to the same reduced state really do have the same future. Verify by stress-testing against the un-reduced DP on small inputs before trusting it.

How to Spot a Transformable Problem

Signal in the Problem	Likely Transformation
Coordinates up to ${10}^9$, but $n\le 2\times {10}^5$	Coordinate compression
"Count X satisfying complex condition"	Complement counting
Many range-add operations, then read array	Difference array
"Sum over all pairs/subsets/subarrays"	Contribution reframe
Bipartite graph + optimization	König / flow duality
Queries in arbitrary order, expensive online	Offline reordering
DP with redundant dimensions	State-space reduction

If none of these click, ask: "What known problem does this remind me of?" Then figure out the transformation that maps this problem to that one.

Practice Problems

Problem	Transformation	Source
CF 61E -- Enemy is Weak	Coordinate compression + BIT inversions	CF
CF 1538F -- Interesting Function	Contribution by digit position	CF
CF 276C -- Little Girl and Maximum Sum	Difference array + sort	CF
CF 1515E -- Phoenix and Computers	State-space DP reduction	CF
CF 1208E -- Let Them Slide	Offline + sliding window per row	CF

---

See also: Problem Pattern Recognition for the constraint-to-algorithm mapping that often follows a transformation, and Problem Reduction Guide for the broader art of reducing unfamiliar problems to known ones.