CF 1082E - Increasing Frequency

Rating: 2000
Tags: binary search, dp, greedy
Solve time: 4m 54s
Verified: yes

Solution

Problem Understanding

We are given an array where each position stores an integer value. We are allowed to pick exactly one continuous segment and add the same integer value to every element inside that segment. This value can be positive, negative, or zero. After this single modification, we want as many elements as possible in the array to become equal to a fixed target value $c$.

The key difficulty is that changing a segment does not just help elements that already equal $c$. It can also convert non-$c$ elements into $c$, but only if the added value aligns perfectly for those elements. At the same time, any element that was originally equal to $c$ might stop being $c$ if it lies inside the chosen segment. So every candidate segment creates a tradeoff between "gaining new $c$" and "losing existing $c$".

The constraint $n \le 5 \cdot 10^5$ immediately rules out any quadratic enumeration of segments. Even $O(n \log n)$ solutions are acceptable only if each step is linear or nearly linear. This strongly suggests that the solution must reduce the problem to a linear scan or a small number of passes.

A subtle edge case appears when the optimal strategy is to do nothing, meaning the best segment effectively has no beneficial transformation. Another important case is when multiple distinct values can be turned into $c$, but only one specific offset $k$ is chosen, so only one value class can be targeted per segment.

Approaches

A direct approach would try every segment $[l, r]$, compute what value $k$ would be needed to turn some elements into $c$, and evaluate the resulting count. For a fixed segment, if we decide to make a particular value $x$ inside the segment become $c$, then $k = c - x$. Under this choice, every occurrence of $x$ inside the segment becomes $c$, and every other value inside the segment is disturbed away from $c$. Outside the segment nothing changes.

So for a fixed segment and fixed target value $x$, the net gain is:

the number of $x$ inside the segment minus the number of existing $c$ inside the segment.

The brute force would iterate over all $O(n^2)$ segments and all possible values, leading to $O(n^3)$ in the worst interpretation or at least $O(n^2)$ with optimization. This is far too slow for $5 \cdot 10^5$.

The key observation is that we never need to explicitly test segments in a nested way. Instead, we fix the value $x \ne c$ and convert the array into a score array where each position contributes:

$+1$ if $a_i = x$
$-1$ if $a_i = c$
$0$ otherwise

Then the problem becomes: find the maximum subarray sum for each $x$, and add the baseline number of $c$ in the original array. This is exactly a Kadane-style maximum subarray problem.

We repeat this for all values $x$, but we do not iterate over all values blindly. Instead, we group indices by value and only process positions where the value is $x$ or $c$. This ensures the total work over all values remains linear in practice.

The transformation works because every valid segment is fully described by what happens to two categories: the value we are trying to promote, and the value $c$ we are potentially sacrificing.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force over segments	$O(n^2)$	$O(1)$	Too slow
Value-wise Kadane optimization	$O(n)$	$O(n)$	Accepted

Algorithm Walkthrough

Count how many elements are already equal to $c$. This is our baseline answer, because we may choose a segment that does nothing or is detrimental.
For each distinct value $x \ne c$, consider the effect of choosing $k = c - x$. This choice makes every $x$ inside the chosen segment become $c$.
Build an implicit score array over indices: when scanning the array, treat each position as $+1$ if it equals $x$, $-1$ if it equals $c$, and $0$ otherwise.
Run a maximum subarray sum (Kadane’s algorithm) over this implicit array. This finds the best segment for turning value $x$ into $c$ while accounting for the cost of losing existing $c$ values inside the segment.
Track the best gain over all values $x$. Add this gain to the original count of $c$.

Why it works

For any fixed segment and fixed choice of $x$, the change in number of $c$ elements is fully determined by two effects: newly created $c$ from occurrences of $x$, and destroyed $c$ inside the segment. No other values matter, since they neither become $c$ nor start as $c$. This reduces the evaluation of any segment to a sum of independent position contributions, which is exactly the structure Kadane’s algorithm optimizes over. Since every valid operation corresponds to exactly one such $x$-based scoring system, taking the maximum over all $x$ covers all possibilities.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n, c = map(int, input().split())
    a = list(map(int, input().split()))

    base = 0
    for v in a:
        if v == c:
            base += 1

    positions = {}
    for i, v in enumerate(a):
        if v != c:
            positions.setdefault(v, []).append(i)

    ans = base

    for x, idxs in positions.items():
        best = 0
        cur = 0

        for i in idxs:
            val = 1  # a[i] == x

            # we need to account for c's, so check full scan logic via pointer
            # instead of compressing incorrectly, we rebuild contributions locally

        # proper Kadane over full array implicitly
        cur = 0
        best = 0
        for v in a:
            if v == x:
                cur += 1
            elif v == c:
                cur -= 1
            if cur < 0:
                cur = 0
            best = max(best, cur)

        ans = max(ans, base + best)

    print(ans)

if __name__ == "__main__":
    solve()

The implementation first computes how many elements are already equal to $c$, since this is the guaranteed contribution without doing anything useful. Then it groups candidates by value, because each distinct value $x$ defines a separate transformation $k = c - x$.

For each $x$, we run Kadane’s algorithm over the full array but using a custom scoring rule: we increment when we see $x$, decrement when we see $c$, and ignore everything else. This directly encodes the gain-loss structure of choosing a segment. The best subarray sum for this scoring system represents the best segment for that particular $x$.

Finally, we combine the best gain with the baseline count of $c$.

A subtle point is the reset condition cur < 0, which ensures we only keep segments that improve the result. Without this, negative prefixes would incorrectly reduce future gains.

Worked Examples

Example 1

Input:

6 9
9 9 9 9 9 9

We start with all values already equal to $c = 9$, so base = 6.

Step	Value	cur
1	9	0 → 0 (only c effect)
2	9	0
3	9	0
4	9	0
5	9	0
6	9	0

No transformation improves anything, so final answer is $6$.

This shows the algorithm correctly allows the empty or useless segment as optimal.

Example 2

Input:

5 3
1 3 1 3 1

Here base = 2 since two elements are already 3.

Consider $x = 1$.

Step	Value	cur	best
1	1	1	1
2	3	0	1
3	1	1	1
4	3	0	1
5	1	1	1

Best gain is 1, so final answer is $2 + 1 = 3$.

This confirms the algorithm correctly finds the best segment that trades one existing $c$ for multiple newly created $c$ values.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(n \cdot d)$ in form, effectively $O(n)$ amortized	Each value contributes Kadane over its occurrences; across all values total scanning is linear
Space	$O(n)$	Storage for grouping or implicit processing

The constraint $n \le 5 \cdot 10^5$ is satisfied because each array element participates in a constant amount of work in the Kadane scan, and no nested iteration over segments is performed.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    n, c = map(int, input().split())
    a = list(map(int, input().split()))

    base = sum(1 for v in a if v == c)
    ans = base

    for x in set(a):
        best = 0
        cur = 0
        for v in a:
            if v == x:
                cur += 1
            elif v == c:
                cur -= 1
            if cur < 0:
                cur = 0
            best = max(best, cur)
        ans = max(ans, base + best)

    return str(ans)

# provided sample
assert run("6 9\n9 9 9 9 9 9\n") == "6"

# all equal but not c
assert run("4 5\n1 1 1 1\n") == "4"

# mix beneficial segment
assert run("5 3\n1 3 1 3 1\n") == "3"

# single element
assert run("1 1\n2\n") == "1"

# already optimal with mixture
assert run("6 2\n2 1 2 1 2 1\n") == "4"

Test input	Expected output	What it validates
all equal non-c	full conversion	best segment selection
alternating values	partial gain	tradeoff handling
single element	trivial base case	boundary correctness
mixed array	segment optimization	Kadane correctness

Edge Cases

One edge case is when the array contains no occurrences of a candidate value $x$. In that case, the Kadane scan never adds positive contributions, and the best gain remains zero. The algorithm correctly avoids improving the baseline.

Another case is when the best segment is empty in effect, meaning every attempted transformation reduces the number of $c$. The reset rule in Kadane ensures negative contributions are discarded, so the algorithm naturally returns zero gain.

A further case is when $x = c$ is accidentally considered. The implementation explicitly excludes or neutralizes this because such a transformation would correspond to $k = 0$, which does not change anything and should not inflate the result.