Atcoder - Regular Contest 082 a

Description: Solution for ARC 082 a.
Publish Date: Calculating Date
Tags: [[competitive programming], [preprocessing], [cpp]]

Problem Statement

Given an array $a = a_1, a_2, \ldots, a_n$ and $1 \leq n < 10^5$ , for each element, either add one, substract one or do nothing about it in a way that results in the maximum count of same-valued elements in the array and output the count.

Solution

Notice that there are three patterns of subarrays in $a$ that can be counted.

$\ldots, x, x, x, \ldots$ : Same-valued elements can be considered as a possible maximum count.
$\ldots, x, x, x+1, \ldots$ : Elements that are only one unit apart can be considered.
$\ldots, x-1, x, x+1, \ldots$ : These can be considered, too.

For the problem, we use set<T> for the elements to only extract the value and keep track of how many elements are same-valued in a hash table where $h(n) = n$ . set<T> also allows us to automatically sort the unique elements with little cost due to its underlying data structure (B-Tree). We iterate through the array in a linear fashion ( $O(n)$ ) while noticing the above patterns.

#include <bits/stdc++.h>
 
using namespace std;
 
int N;
int counts[100000] = {};
set<int> elems;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int x;
        cin >> x;
        ++counts[x];
        elems.insert(x); // set<int> auto-sorts
    }
 
    int i0 = -1, i1 = -1, biggest = 0;
    for (int x : elems) // ordered set, monotonic
    {
        if (i0 == -1)
        {
            i0 = x;
            biggest = counts[x]; // base scenario
        }
        else if (i1 == -1)
        {
            i1 = x;
            int possible;
            if (i1 - i0 == 1) // calculate here first since we won't come back after initializing
            {
                // ..., x, x+1, ...
                possible = counts[i1] + counts[i0];
            }
            else
            {
                // ..., x, x, x, ...
                possible = counts[i1];
            }
            if (possible > biggest)
            {
                biggest = possible;
            }
            continue;
        }
        if (i0 == -1 || i1 == -1)
        {
            continue;
        }
        int d0 = i1 - i0;
        int d1 = x - i1;
        int possible = 0;
        if (d1 == 1 && d0 == 1) // ..., x-1, x, x+1, ...
        {
            possible = counts[x] + counts[i1] + counts[i0];
        }
        // else if(d0 == 1) // meaningless since this can be computed before
        // {
        //     possible = counts[i1] + counts[i0];
        // }
        // ^ Gist: ..., x-1, x, ... is the same as ..., x, x+1, ...
        else if (d1 == 1) // ..., x, x+1, ...
        {
            possible = counts[x] + counts[i1];
        }
        else
        {
            possible = counts[x];
        }
        if (possible > biggest)
        {
            biggest = possible;
        }
        i0 = i1;
        i1 = x;
    }
 
    cout << biggest << '\n';
    return 0;
}