Redaksiya

Group 1: none of the friends is afraid of either of the animals

In this group, no one is afraid of either dogs or cats, so it does not matter which pets any person has and Anton can just invite all his friends — the answer is $n$.

Time and memory complexity: $O(1)$ (it is not even necessary to read all the input)

Group 2: every friend has exactly one pet and is afraid of exactly one animal

It can be seen that here there are only two types of people: those who have dogs and are afraid of cats ("1 2" type) and vice versa ("2 1" type). These two types cannot be together since people of both types have pets that people of other types are afraid of, but people of the same type can still be together, so the answer is $max(coun{t}_{dog\_owners},coun{t}_{cat\_owners})$.

Time complexity: $O(n)$

Memory complexity: $O(n)$ or $O(1)$ (you do not need to store all the information and process it while reading)

Group 3: none of the friends has a cat

Since there are no friends with cats in this group, we can also forget about the fact that someone can be afraid of them in this group. That is, all the "$2$"'s and "$3$"'s in people's fears can be replaced with "$0$"'s and "$1$"'s respectively)

After such replacement, we can notice that there are only two possible combinations of fears: no fears or a fear of dogs. These two cases can be processed separately:

• In the case of no fears, the answer is the number of people who are not afraid of dogs.

• In the case of the fear of dogs, the answer is the number of people who do not have dogs.

Out of these two cases, we need to take the maximum answer.

Time complexity: $O(n)$

Memory complexity: $O(n)$ or $O(1)$

Group 4: every friend has at most one pet and is afraid of at most one animal

(Hint: the following solution is almost the fully correct one, but here you do not need to handle the $3$'s)

We can notice that there are four cases in which pets are "allowed to be invited": no pets, only cats, only dogs, or both. Let's determine which conditions there are for each case:

• In the case of no friends with pets invited, Anton can just invite all the friends with no pets and it does not matter if they have any fears;

• In the case of only dogs invited, a person has not to have a cat and has to not be afraid of dogs;

• The case of only cats invited is similar to the previous one, but here each person has to not have a dog and not be afraid of cats;

• To invite a friend to the party with both animals allowed, they have to not be afraid of any animal.

Here is the implementation of handling these cases on C++:

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int ans[4] = {0};
    for (int i = 0, a, b; i < n; i++) {
        cin >> a >> b;
        if (a == 0)
            ans[0]++;
        if (a != 2 and b != 1)
            ans[1]++;
        if (a != 1 and b != 2)
            ans[2]++;
        if (b == 0)
            ans[3]++;
    }
    int out = max({ans[0], ans[1], ans[2], ans[3]});
    cout << out;
}

Time complexity: $O(n)$

Memory complexity: $O(n)$ or $O(1)$

Group 5. $n\le 20$

This group was added to make the brute force solutions pass. It could be possible to implement, for example, using bitmasks:

int n;
cin >> n;
int a[n], b[n];
for (int i = 0; i < n; i++)
    cin >> a[i] >> b[i];
int ans = 0;
for (int mask = 0; mask < (1 << n); mask++) {
    bool have_c = 0, have_d = 0;
    bool afr_c = 0, afr_d = 0;
    for (int i = 0; i < n; i++) if (mask >> i & 1) {
        have_c |= a[i] & 2;
        have_d |= a[i] & 1;
        afr_c |= b[i] & 2;
        afr_d |= b[i] & 1;
    }
    if ((have_c and afr_c) or (have_d and afr_d))
        continue;
    ans = max(ans, __builtin_popcount(mask));
}
cout << ans << endl;

The point is to check all the possible combinations of friends invited and take the maximum size out of the valid ones.

Time complexity: $O(2^n)$

Memory complexity: $O(n)$

Group 6. no additional constraints

As it was said before, this solution is the extended version of the solution for the $4$-th group, but here we also need to handle the "$3$"'s. Here are the additional restrictions made for each combination of allowed pets in this group:

• no pets invited: $a\ne 3$ (no people with both pets) / not needed since $a$ needs already to be $0$ here;

• only dogs invited: $a\ne 3,b\ne 3$ (no people with both pets / both fears);

• only cats invited: $a\ne 3,b\ne 3$ (the same as for the previous one);

• both animals invited: $b\ne 3$ / not needed since $b$ needs already to be $0$ here.

This can be done by extending the if-conditions, but this can also be done using "tricks" with bitmasks, where the $0$-th bit stands for a cat and the $1$-th bit stands for a dog.

Here is an example of such implementation:

int ans[4] = {0};
for (int i = 0, a, b; i < n; i++) {
	cin >> a >> b;
	if (a == 0)
		ans[0]++;
	if (!(a & 2) and !(b & 1))
		ans[1]++;
	if (!(a & 1) and !(b & 2))
		ans[2]++;
	if (b == 0)
		ans[3]++;
}

Here, the restrictions for each combination of allowed pets can be seen more clearly.

Time complexity: $O(n)$

Memory complexity: $O(n)$ or $O(1)$.