STAIRCASE7 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given an array A.
Find the minimum number of element replacements needed to make A_i - A_{i-1} = 1 for every i.

EXPLANATION:

Suppose we decide to leave the elements at indices i and j (i \lt j) both unchanged.
When is this allowed?

Well, in the final array we must have:

  • A_{i+1} = A_i + 1.
  • A_{i+2} = A_{i+1} + 1 = A_i + 2
  • A_{i+3} = A_{i+2} + 1 = A_i + 3
    \vdots

Continuing this logic, we see that A_j = A_i + (j-i) must hold.
This can be rearranged to A_j - j = A_i - i.

Suppose we define a new array B with B_i = A_i - i.
As seen above, we can keep indices i and j unchanged only if B_i = B_j.

Extending this logic, if we want to keep many indices unchanged, they must all have the same B_i value, since this argument can be applied to any pair of values.

Our aim is to minimize the number of replaced elements; which is equivalent to maximizing the number of element we leave unchanged.
With the above observation, this quantity is easy to find: it’s simply the maximum number of times any element appears in the array B.

The answer is hence N minus the maximum frequency in B.
Finding the maximum frequency of an element in an array can be done in many ways: you can use sorting, or build a map/dictionary of frequencies and then look up each one to find the maximum value.
In this problem, A_i \le N means that B_i \in [-N, N] so it’s possible to use an array (with an offset) to store frequencies, allowing for true constant time updates/lookup; but using a hashmap/treemap/sorting is perfectly fine too.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    b = [a[i] - i for i in range(n)]
    b.sort()
    ans, ct, prv = 0, 0, -5*n
    for x in b:
        if x == prv: ct += 1
        else:
            prv = x
            ct = 1
        ans = max(ans, ct)
    print(n - ans)
1 Like