FENCECOL - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There’s a fence of length N. You want the i-th section to be given color A_i.
Initially, all colors are 1.

In one move, you can:

  • Color all the sections with a chosen color, or
  • Color a single section with a chosen color.

Find the minimum number of operations to achieve the desired coloring.

EXPLANATION:

Observe that if we ever perform a type 1 operation, i.e. an operation of the form “color everything with X”, then all operations made before it are useless anyway.

This tells us that in an optimal solution, there will either be 0 or 1 operation of this form - and further, if there’s one operation, it will be the very first one.

Suppose there’s no operation of type 1.
Then, since we can only use type 2 operations (which affect a single index), and every color is initially 1, the number of moves we need just equals the number of elements of A that are not equal to 1.

Otherwise, suppose our first move is to color everything X.
The number of type 2 operations needed is then the number of elements of A that are not equal to X.

So, if \text{freq}[X] denotes the number of times X appears in A,

  • Not performing a type 1 operation gives a cost of (N - \text{freq}[1]).
  • Performing a type 1 operation with 2 \leq X \leq N gives a cost of (1 + N - \text{freq}[X]).

Computing the \text{freq} array can be done in linear time, after which you can try all X and take the best answer among them.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    freq = [0]*(n+1)
    for x in a:
        freq[x] += 1
    
    ans = n - freq[1]
    for i in range(2, n+1):
        ans = min(ans, 1 + n - freq[i])
    print(ans)
1 Like