BOP2 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: kingmessi
Tester: pols_agyi_pols
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You have N friends. Friend i will apply color C_i to your face.
Initially, your face has no color.
If the newly applied color differs from the previously applied color, you will feel a jolt.

Find the minimum possible number of jolts, if you can visit the N friends in any order.

EXPLANATION:

Since we feel a jolt each time the color changes, our objective is to make sure that the color doesn’t change too often.
The simplest way to do this is: whenever a new color is applied on our face, then visit all other friends who also apply this color - so that none of them will cause jolts.

This way, the only time we’ll feel a jolt is the very first time each color is applied to us.
Clearly, this is unavoidable since the first time a color is applied it will surely be different from the previously applied color.

Since we receive one jolt for each color, the answer is hence the number of distinct colors present in the array.

There are many ways to check for this.
For example, one simple way in quadratic time is as follows:

  • For each index i from 1 to N, check if C_i = C_j for any index j \lt i.
  • If no such j exists, this is the first instance of this color, so add 1 to the answer.
    If such a j does exist, it’s not the first instance, so we’ve already accounted for this color. Don’t add 1 to the answer.

There are other, faster algorithms too - for example utilizing sorting - but they aren’t needed with the low constraints here.

TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    c = list(map(int, input().split()))
    
    ans = 0
    for i in range(n):
        new = 1
        for j in range(i):
            if c[i] == c[j]:
                new = 0
        ans += new
    print(ans)