There are N arrays of N length each. You are given the Mexes of all the arrays.
For each 0\leq i\leq N-1, Ashish wants to know the atleast amount of i in all N arrays and Kryptonix wants to know the atmost amount of i in all N arrays.
EXPLANATION:
Observation 1: Suppose MEX for a particular array A is x (x > 0). Then all the numbers starting from 0 to (x-1) would occur atleast once in this array.
Observation 2 : Suppose MEX for a particular array A is x, then any number except greater than x can occur atmost (n - x) times in it.
Now in order to solve this problem we would to do some pre-computations. We would have a freq variable to store frequency of each A_i and a extra variable that would be sum of all positions where any number greater than A_i (1 \leq i \leq n) can be put.
Keeping these in mind we would loop through the array and for particular position i, we would increment frequency of A_i by 1 and increment extra by n-A_i.
Keeping these in mind, we would sort the array A and then loop from 0 to n-1. For a particular position say i, we first calculate the smallest j_{th} position in A such that A_j > i. Then all the arrays from j_{th} position to the end would have atleast 1 number as i, so atleast[i] = n-j. We can calculate atmost[i] as:
here is my O(n) solution #include <bits/stdc++.h> #define ull unsigned long long int #define ui unsigned int #define ll long long int #define f(i, n) for (ll i = 0; i < n; i++)
const ll m = 10e9 + 7;
// const ll N = 10e5 + 5;
using namespace std;
ll binpow(ll a, ll b, ll m)
{
a %= m;
ll res = 1;
while (b > 0)
{
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t;
cin >> t;
while (t–)
{
int n;
cin >> n;
ll arr[n];
vector lb(n, 0);
vector ub(n, 0);
vector pre(n, 0);
vector prefix(n, 0);
vector suffix(n, 0);
f(i, n) cin >> arr[i];
f(i, n)
{
if (arr[i] > 0)
{
pre[arr[i] - 1] += 1;
}
if (arr[i] > 0)
prefix[arr[i] - 1] += n - arr[i] + 1;
if (arr[i] < n - 1)
suffix[arr[i] + 1] += n - arr[i];
}
ll t = 0;
ll q = 0;
for (int i = n - 1; i >= 0; i–)
{
if (pre[i] != 0)
{
t += pre[i];
}
if (prefix[i] != 0)
{
q += prefix[i];
}
lb[i] += t;
ub[i] += q;
}
q = 0;
for (int i = 0; i < n; i++)
{
if (suffix[i] != 0)
{
q += suffix[i];
}
ub[i] += q;
}
f(i, n)
{
cout << lb[i] << " " << ub[i] << ‘\n’;
}
}
return 0;
}
I found an extra sweet and short solution during contest:
#include <bits/stdc++.h>
using namespace std;
long long t, n, a[300005], b[300005];
int main() {
cin >> t;
while(t--) {
cin >> n;
for(int i= 0; i < n; ++i) cin >> a[i];
sort(a, a + n), fill(b, b + n + 1, 0);
for(int i= 0; i < n; ++i) b[i + 1]+= n - a[i] + b[i];
for(int i= 0; i < n; ++i) {
auto lo= lower_bound(a, a + n, i) - a;
auto hi= upper_bound(a, a + n, i) - a;
cout << n - hi << ' ' << n - hi + b[lo] + b[n] - b[hi] << '\n';
}
}
}
Logic was the same, I just needed the number of free spots in arrays that can contain i. The prefix sum array uses an open interval so that it works immediately with {lower, upper}_bound
Unfortunately, I did not keep track of the numbers, so I ended up getting WA because I did not use long long.
You have 5 arrays, Each of these arrays is of length 5. All we know about these 5 arrays is the Mex. With the help of the Mex of each array, we can write them down like this:
You are now supposed to find out the minimum amount of occurrences of 0, 1, 2, …, n-1 in all n above arrays.
Case 0: min: 4 max: 13
Case 1: min: 3 max: 13
Case 2: min: 2 max: 13
Case 3: min: 1 max: 13
Case 4: min: 1 max: 15
In the case of 2: above we can see that 2 arrays have to contain a 2, so the min value is 2. In the above arrays we see 14 blank spaces of which 11 can be a 2. (arr4 has 3 blank spaces which are blocked because the Mex is 2). Since 11 blank spaces can be 2’s and 2 spaces are already 2’s, we know we can have at most 13 2’s.