ATAT Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Ashish Gangwar
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

1870

PREREQUISITES:

None

PROBLEM:

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:

atmost[i] = atleast[i] + extra - (freq[i] \times (n - i))

TIME COMPLEXITY:

O(NlogN), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

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;
}

Can someone explain the problem statement in english? I am not able to understand the example testcases either

1 Like

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.

Testcase from the contest

1
5
3 1 5 0 2

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:

arr0 = [0, 1, 2, _, _] with _ != 3
arr1 = [0, _, _, _, _] with _ != 1 
arr2 = [0, 1, 2, 3, 4] with _ != 5 
arr3 = [_, _, _, _, _] with _ != 0 
arr4 = [0, 1, _, _, _] with _ != 2

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.

6 Likes

Tester 1’s solution is O(N). It is very neat and intuitive and should be part of the editorial.

1 Like

Can someone tell me what is wrong with this [solution].(Solution: 67673114 | CodeChef)