TRANCHAIN - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: notsoloud
Tester: satyam_343
Editorialist: iceknight1093

DIFFICULTY:

1214

PREREQUISITES:

None

PROBLEM:

Given the blood types of N people, and knowledge of which blood type can donate to which blood type, find the maximum number of people in a blood transfusion chain.

EXPLANATION:

Looking at the possible donors/receivers, we see that:

  • Blood type O can donate to any type.
  • Blood type AB can receive from any type.
  • Blood types A and B don’t have any interaction with each other.

This means:

  • Anyone with blood type O or AB can always be placed in any chain: either at the front, or at the end depending on their type.
  • The chain can’t contain both a blood type-A person and a type-B person.

Together, this tells us that we can pick everyone with types O and AB; and after that we must choose between types A and B. Clearly, it’s best to choose whichever type has most people.

So, if c_x denotes the number of people with blood type x, the answer is

c_O + c_{AB} + \max(c_A, c_B)

which can also be written as

N - \min(c_A, c_B)

since we’re essentially excluding the people of either A or B type and taking everyone else.

The counts of the four types can be found by iterating across the array.

TIME COMPLEXITY

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    types = list(input().split())
    print(n - min(types.count('A'), types.count('B')))
1 Like