NO4S - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given an array A containing the elements 1, 2, 3 only.
Find the minimum number of elements that must be deleted to obtain an array such that no pair of elements sum to 4.

EXPLANATION:

Since we only have the elements 1, 2, 3, the only possible pairs that can sum to 4 are
1+3 and 2+2.

This means:

  • If the array has both a 1 and a 3, it cannot be good.
  • If the array has at least two occurrences of 2, it cannot be good.
  • Otherwise, it will be good.

Looking at this in terms of deletions:

  • We cannot have both 1's and 3's.
    This means we have to completely delete at least one of them: either delete all 1's or delete all 3's.
    If we delete all 1's, it’s optimal to not delete any 3's, and vice versa.
    So, the optimal choice here is to just delete whichever occurs less frequently among 1 and 3.
  • We also can have at most one occurrence of 2.
    So, if there are \gt 1 occurrences of 2, we must delete all but one of them.

Thus, if we define f_1, f_2, f_3 to be the counts of 1, 2, 3 in the array respectively, the answer is simply

\min(f_1, f_3) + \max(0, f_2 - 1)

The first term corresponds to deleting either all ones or all threes, and the second term corresponds to deleting all but one occurrence of twos.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        array<int, 4> freq{};
        for (int i = 0; i < n; ++i) {
            int x; cin >> x;
            ++freq[x];
        }

        cout << min(freq[1], freq[3]) + max(0, freq[2] - 1) << '\n';
    }
}