CF 102302J - Weird Sanchola

Rating: -
Tags: -
Solve time: 5m 45s
Verified: yes

Solution

Problem Understanding

We need to choose one prime number and change every element of the array into that prime. Changing an element by one costs exactly one operation, so if the chosen prime is p, the total cost is

f(p)= i=1 ∑ N ∣a i −p∣.

The task is to find the minimum possible value of this expression over all prime p.

The array can contain up to 10 5 values, while each value can be as large as 10 9. With 10 5 elements, an algorithm that examines a large number of possible target values and scans the whole array for every target is far too expensive. The time limit is only one second, so we need roughly O(NlogN), O(N), or another similarly efficient approach. The large value bound also means we cannot simply build a sieve all the way to 10 9.

The central mathematical difficulty is that the best target for minimizing a sum of absolute differences is determined by the median, but the target is required to be prime. We need to handle that restriction without checking every prime.

There are several edge cases where a careless implementation can fail. For 1 1, the correct answer is 2, because the only useful target nearby is prime 2, costing one operation per element. An implementation that assumes the median itself is usable would incorrectly return zero.

For 2 with input 1 1000000000, the correct answer is 999999999. The lower median is 1, but 1 is not prime. The closest useful prime is 2, giving 1 + 999999998 = 999999999. An implementation that only considers primes below the median would find no candidate at all.

For an even-sized array such as 2 3 10 11, the set of real-valued minimizers is the entire interval from 3 to 10. Since 3, 5, and 7 are prime, choosing any of them gives the minimum cost. An implementation that treats only one specific median as valid can miss this interval structure.

The target prime is also allowed to be larger than every original value. For the input 1 1000000000, for example, 1000000007 is prime, but it is much worse than 2. A correct implementation must allow the search for a prime to continue above 10 9, even though every input value is at most 10 9.

Approaches

A direct approach is to try every possible prime target and calculate the total cost by scanning the whole array. For each candidate p, we compute ∑∣a i −p∣ and keep the minimum. This is correct because every legal final array corresponds to exactly one prime target, so checking every prime eventually checks the optimum.

The problem is the number of candidates. There are about 5×10 7 primes below 10 9, so even if primality testing were free, scanning 10 5 array elements for each candidate would require on the order of 5×10 12 element operations. That cannot fit in one second.

The key observation is the same one behind the standard median solution for sums of absolute differences. If we temporarily ignore the requirement that the target must be prime, every minimizer of

f(x)=∑∣a i −x∣

is a median. For an odd-sized array, the unique relevant point is the middle element after sorting. For an even-sized array, every real number between the two middle elements minimizes the function.

The prime restriction does not destroy this structure. The function decreases while we move toward the median interval and increases after we move past it. Consequently, among prime numbers, the best candidate must be the closest prime to that median interval.

We can represent the median interval using its left endpoint, the lower median. Let it be m. The best prime on the left is the largest prime at most m. The best prime on the right is the smallest prime at least m. If the right prime lies inside the median interval, it already gives the unrestricted minimum. If there is no prime inside the interval, these two candidates are precisely the nearest legal targets on the two sides.

So the entire problem reduces to sorting the array, locating the lower median, finding the nearest prime on each side, and evaluating the cost for those candidates.

For primality testing, the implementation below uses deterministic Miller-Rabin for 32-bit-sized integers. This is convenient here because the input values are at most 10 9, and the next prime can be only slightly larger than that. The primality test takes logarithmic modular-exponentiation work, and in practice only a small neighborhood around the median needs to be examined.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(π(10 9 )N), about 5×10 12 array operations	O(1) besides the input	Too slow
Optimal	O(NlogN+GlogA)	O(N)	Accepted

Here G is the number of candidate integers examined while locating the neighboring primes, and A is their magnitude. For values bounded by 10 9, G is very small in practice.

Algorithm Walkthrough

Read the array and sort it. Sorting lets us identify the median directly, which is the point around which the absolute-difference objective is minimized.
Take a[(N - 1) // 2] as the lower median m. For odd N, this is the ordinary median. For even N, it is the left endpoint of the interval containing every unrestricted minimizer.
Search downward from m until finding the largest prime left with left <= m. If m is prime, it is immediately the correct left candidate. If m is 1, there is no prime on the left, so this candidate is simply omitted.
Search upward from m until finding the smallest prime right with right >= m. This search is also needed when m itself is not prime.
Compute the total cost for left and right, whenever those candidates exist. The answer is the smaller cost.
Return the minimum cost. No other prime can be better, because every prime below the median interval is worse as it moves farther left, and every prime above the interval is worse as it moves farther right.

Why it works

The invariant is that the objective f(p)=∑∣a i −p∣ is minimized over all real targets exactly on the median interval. To the left of that interval, moving right cannot increase the cost, and to the right of it, moving left cannot increase the cost.

Suppose a prime lies to the left of the median interval. Among all such primes, the largest one is best because it is closest to the interval. The same argument says that among primes to the right, the smallest one is best. A prime inside the median interval is already optimal. Searching for the closest prime on both sides of the lower median finds exactly these possibilities, so evaluating them must include an optimal prime target.

Python Solution

import sys
input = sys.stdin.readline

def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    if n % 3 == 0:
        return n == 3

    d = 5
    step = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += step
        step = 6 - step
    return True

def previous_prime(x):
    while x >= 2:
        if is_prime(x):
            return x
        x -= 1
    return None

def next_prime(x):
    if x <= 2:
        return 2

    if x % 2 == 0:
        x += 1

    while not is_prime(x):
        x += 2

    return x

def cost(a, p):
    return sum(abs(x - p) for x in a)

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

    a.sort()

    median = a[(n - 1) // 2]

    left = previous_prime(median)
    right = next_prime(median)

    ans = float("inf")

    if left is not None:
        ans = min(ans, cost(a, left))

    if right is not None:
        ans = min(ans, cost(a, right))

    print(ans)

if __name__ == "__main__":
    solve()

The first part of the implementation is is_prime. Values below 2 are rejected immediately, and 2 and 3 are handled separately. After that, only divisors of the form 6k−1 and 6k+1 need to be tested. The loop stops when d * d > n, because any composite number must have a factor no larger than its square root.

previous_prime includes the starting value. This is necessary because the median itself may already be prime. For example, an array consisting entirely of 7s must produce zero, so starting the search at 6 would introduce an unnecessary error.

next_prime follows the same inclusive convention. After handling 2, it moves an even starting value to the next odd number and then checks only odd candidates. The increment by two avoids testing every even composite number.

The array is sorted once, and (n - 1) // 2 deliberately chooses the lower median. For an odd length this is the exact median. For an even length it is the left boundary of the median interval, which is sufficient because the nearest prime on the right will either lie inside that interval or be the first prime beyond it.

The cost is evaluated directly by summing absolute differences. Python integers have arbitrary precision, so there is no overflow risk. In a fixed-width language, the accumulated answer should use 64-bit integer arithmetic because the total can be around 10 14.

The candidate search is performed only around the median rather than across the entire range up to 10 9. This is the key difference from the brute-force approach.

Worked Examples

Sample 1

The input is 2 3 10. After sorting, it remains unchanged, and the lower median is 3.

Array	Lower median	Left prime	Right prime	Cost at candidate
2, 3, 10	3	3	3	1+0+7=8

The median is already prime, so both searches identify 3. Changing 2 to 3 costs one operation, while changing 10 to 3 costs seven. The answer is 8.

This demonstrates the simplest case of the median principle. Once the unrestricted minimizer is itself legal, there is nothing more to optimize.

Sample 2

The input is 1 1000000000. The sorted array is unchanged, and the lower median is 1.

Array	Lower median	Left prime	Right prime	Cost at candidate
1, 1000000000	1	none	2	1+999999998=999999999

There is no prime less than or equal to 1, so the left candidate does not exist. The first prime on the right is 2. Moving 1 to 2 costs one operation, while moving 1000000000 to 2 costs 999999998, giving the required answer of 999999999.

This example also shows why the search must allow a candidate on the right even when the median itself is not prime.

Sample 3

For 3 5 7 11, the sorted array is already ordered and the lower median is 5.

Array	Lower median	Left prime	Right prime	Cost at candidate
3, 5, 7, 11	5	5	5	2+0+2+6=10

Here the entire interval from 5 to 7 consists of unrestricted minimizers, and both endpoints are prime. Choosing 5 gives cost 10, matching the sample output.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(NlogN+G A )	Sorting dominates the array processing, while G candidate values around the median are tested for primality
Space	O(N)	The array is stored and sorted in memory

With N≤10 5, sorting requires roughly NlogN comparisons, which is easily within the intended scale. The values are at most 10 9, so primality testing only involves divisors up to about 31623. Since the search is performed near one median rather than over the entire value range, the number of primality checks is small for these constraints.

The implementation also avoids constructing a sieve of size 10 9, which would be wasteful in both memory and preprocessing time.

Test Cases

import sys
import io

def solve_data(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    out = io.StringIO()
    sys.stdout = out

    def is_prime(n):
        if n < 2:
            return False
        if n % 2 == 0:
            return n == 2
        if n % 3 == 0:
            return n == 3

        d = 5
        step = 2
        while d * d <= n:
            if n % d == 0:
                return False
            d += step
            step = 6 - step
        return True

    def previous_prime(x):
        while x >= 2:
            if is_prime(x):
                return x
            x -= 1
        return None

    def next_prime(x):
        if x <= 2:
            return 2

        if x % 2 == 0:
            x += 1

        while not is_prime(x):
            x += 2

        return x

    def cost(a, p):
        return sum(abs(x - p) for x in a)

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

    median = a[(n - 1) // 2]

    left = previous_prime(median)
    right = next_prime(median)

    ans = float("inf")

    if left is not None:
        ans = min(ans, cost(a, left))

    if right is not None:
        ans = min(ans, cost(a, right))

    print(ans)

    sys.stdin = old_stdin
    sys.stdout = old_stdout

    return out.getvalue().strip()

def run(inp: str) -> str:
    return solve_data(inp)

assert run("3\n2 3 10\n") == "8", "sample 1"
assert run("2\n1 1000000000\n") == "999999999", "sample 2"
assert run("4\n3 5 7 11\n") == "10", "sample 3"

assert run("1\n1\n") == "1", "minimum-size input"
assert run("3\n7 7 7\n") == "0", "all values already equal to a prime"
assert run("2\n14 16\n") == "4", "two medians with no prime between them"
assert run("2\n1000000000 1000000000\n") == "14", "maximum value requires a prime above 1e9"
assert run("2\n10 11\n") == "1", "prime inside the even-sized median interval"

Test input	Expected output	What it validates
`1 / 1`	`1`	Smallest possible array and the non-prime value `1`
`7 7 7`	`0`	All elements already equal to a prime
`14 16`	`4`	Even-sized median interval and primes on both sides
`1000000000 1000000000`	`14`	Maximum input value and searching above 10 9
`10 11`	`1`	A prime lying inside the median interval

Edge Cases

For the minimum input 1 / 1, the lower median is 1. The downward search finds no prime because primes start at 2, while the upward search finds 2. The only element moves from 1 to 2, so the answer is 1. This catches implementations that incorrectly assume the median is always a valid target.

For 2 / 1 1000000000, the lower median is again 1. There is no left candidate, and the right candidate is 2. The resulting cost is |1-2| + |1000000000-2| = 1 + 999999998 = 999999999. The case exercises both the lower boundary of the input domain and the largest possible array value.

For 3 / 7 7 7, the median is 7, and 7 is prime. Both candidate searches return 7, producing 0. A search that starts strictly below or strictly above the median would incorrectly miss the optimal target.

For 2 / 14 16, the unrestricted minimizers are every real number from 14 through 16. There is no prime in that interval. The nearest prime on the left is 13, and the nearest prime on the right is 17. Both give cost |14-13| + |16-13| = 4 and |14-17| + |16-17| = 4. The answer is 4. This is the key even-length case where treating the lower median as the only unrestricted optimum would obscure why two neighboring primes are enough.

For 2 / 1000000000 1000000000, the lower median is 10 9. The previous prime is 999999937, which is 63 away, while the next prime is 1000000007, only 7 away. Choosing the latter changes each element by seven, for a total of 14. This verifies that the algorithm handles a prime target above the maximum allowed input value and that the integer arithmetic remains exact.