Heroic Calibration

Author: Udynamo

Required Knowledge : Basic, Data structures

Time Complexity : $\mathcal{O}(N \log N)$

Editorialist : Udynamo

Approach:

The goal is to find a single Balance Point $x$ that the maximum number of stones can be tuned to.

For any given stone with energy $a_i$, we can only perform one of three moves:

$\bullet$ Thor Move: Energy becomes $a_i + 1$.

$\bullet$ Hulk Move: Energy becomes $a_i - 1$.

$\bullet$ Hawkeye Move: Energy remains $a_i$.

This means a single stone $a_i$ can only contribute to a final count for the target values $a_i - 1$, $a_i$, or $a_i + 1$.

Instead of trying to pick a target $x$ and seeing how many stones can match it, we can reverse the problem: For each stone, let's find all the potential target values it could become and increment the count for each of those targets.

We can use a map data structure to count efficiently, since $a_i$ can be as large as $10^9$.

$\bullet$ The key of the map will be a potential target energy level.

$\bullet$ The value will be the total number of stones that can be tuned to that energy level.

Setter's Code:

// Author : Udynamo
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, std::less<int>, rb_tree_tag, 
tree_order_statistics_node_update> pbds;
//find_by_order(k), order_of_key(k)
#define int long long
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define vpi vector<pair<int, int>>
#define pi pair<int, int>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define maxEle(a) *max_element(a.begin(), a.end())
#define minEle(a) *min_element(a.begin(), a.end())
#define sumAll(a) accumulate(a.begin(), a.end(), 0LL)
 
using namespace std;
 
// Input Overloads
template<typename T>
istream& operator>>(istream &is, vector<T> &v) {
    for (auto &x : v) is >> x;
    return is;
}
 
const bool test_cases = true;
const int mod = 1e9 + 7, INF = 1e18;
 
void UNsolve() {
    
    int n;
    cin >> n;
    vi a(n);
    cin >> a;
    map<int, int> mp;
    for(int x: a){
        mp[x - 1]++;
        mp[x]++;
        mp[x + 1]++;
    }
    int mx = 0;
    for(auto [x, y]: mp){
        mx = max(mx, y);
    }
    cout << mx << endl;
}
 
signed main() {
 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    if (test_cases) cin >> t;
    while (t--) {
        UNsolve();
    }
    return 0;
}

Tester's Code:

def solve():
    n = int(input())
    v = list(map(int, input().split()))
    mpp = {}
    for x in v:
        for val in (x - 1, x, x + 1):
            mpp[val] = mpp.get(val, 0) + 1
    ans = 0
    for val in mpp.values():
        ans = max(ans, val)
    print(ans)

t = int(input())
for _ in range(t):
    solve()