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
andB
don’t have any interaction with each other.
This means:
- Anyone with blood type
O
orAB
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
which can also be written as
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')))