MEXYARR Editorial

editorial
, , , ,
1

PROBLEM LINK:

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

Setter: Manuj Nanthan
Tester: Aryan, Takuki Kurokawa
Editorialist: Pratiyush Mishra

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

You are given an array B containing N integers, each of which is either −1 or a non-negative integer. Construct any integer array A of length N such that:

  • 0≤A_i≤10^9 for every 1≤i≤N
  • If B_i≥0, A must satisfy mex(A_1,A_2,…,A_i)=B_i
  • Otherwise, B_i=−1 , which means there is no constraint on mex(A_1,A_2,…,A_i)

If there does not exist any array satisfying the constraints, print −1 instead.

Note: The mex of a set of non-negative integers is the smallest non-negative integer that does not belong to it. For example,
mex(1,2,3)=0 , mex(0,2,4)=3 , mex(0,0,0)=1

Quick Explanation

Take two sets x and y. x contains integers coming in B_i as positive integers and y contains the remaining integers from 0 to N-1.
Construct greedily from B_1 to B_n.
If B_i is -1 , print the elements from y set. else If B_i is positive , print the previous element of set x.
In this way we can construct valid array.
Note that it won’t be possible to create array A if for any i we have B_i \geq (i+1) or for any i, there is a B_j such that 0 \leq j < i and B_j > B_i

Explanation

There can be multiple ways to go about its implementation, one of which is discussed here.

First we check if for any i, if there exists any B_j such that 0 \leq j < i and B_j >B_i. If such B_j exists then it won’t be possible to create array and we would return -1.

Now we would create two separate sets slots and elements where slots represents the available slots of A that needs to be filled, while elements represents the available elements that can be used to fill the slots.

Let’s talk about the way we will go about filling. We will first remove duplicates from array B, i.e say array B = \{-1,1,1,1,2\}, then we would change duplicates to -1, so B would become \{-1,1,-1,-1,2\}. This way we would have increasing order of positive numbers and -1s. Now we will loop through array and upon reaching a positive value, we would loop through all available slots in A in increasing order and fill elements from set elements till Mex(A_1,A_2.....A_i) becomes B_i. If for any case we do not have slots available to fill then also it won’t be possible to create array A and we would return -1.

TIME COMPLEXITY:

In this algorithm, we iterate through the array and when we find any positive B_i, we loop through all the available slots available and remove them from set after filling it. Thus we are basically iterating the array twice and in second iteration of going through availble slots, we are accessing from a set that takes O(logN) time, thus total time complexity would be O(NlogN).

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution

1 Like
2

Hello, I think I have the same algorithm but it was giving WA on several test cases. Please kindly look at this solution: CodeChef: Practical coding for everyone
I tried it with small cases, including corner cases, and couldn’t figure out where the mistake may be.

1 Like
3

Same question from Codeforces Question

10 Likes
4

I solved it using stack.
https://www.codechef.com/viewsolution/61096440

1 Like
5

Can anyone please help me out with this one?

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define vi vector<int>
#define mii map<int,int>
#define fr(i,n) for(ll i=0; i<n; i++)
#define Fast_IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

//const int N = 1e5+7;
//int a[N];
void solve();

int main() {
	Fast_IOS;
	int tt; cin >> tt;
	while (tt--)
	solve();
}

void solve() {
	int n; cin >> n;
	int arr[n];
	map <int, int> m;
	int num;
	vi check;
	fr(i,n) {
		cin >> num;
		arr[i] = num;
		if (num >= 0) {
			m[num]++;
			check.pb(num);
		}
	}
	if (is_sorted(check.begin(), check.end())) {
		vector<int> ans;
		int j = 0;
		int valid = 0;
		for (int i = 0; i < n; i++) {
			while (m[valid] > 0) {
				valid++;
			}
			if (arr[i] > i+1) {
				cout << -1 << endl; return;
			}
			if (arr[i] != -1) {
				m[arr[i]]--;
				if (j > 0) {
					 if (check[j] != check[j-1])
						ans.pb(check[j-1]);
					else {
						ans.pb(valid);
						valid++;
					}
				}
				else {
					ans.pb(valid);
					valid++;
				}
				j++;
			}
			else {
				ans.pb(valid);
				valid++;
			}
		}
		for (auto x: ans)
			cout << x << " ";
		cout << endl;
	}
	else {
		cout << -1 << endl;
	}
}
6

why is my solution getting TLE ? I am also using a set ;(
link

7

@admin

One more problem duplicated. XOR and AND is also exactly the same as a problem on hackerearth. This context should be unrated.

1 Like
8

can i know what is the intution behind taking stack like is there any way to modify the problem into some standard stack problem i will be greatful if u explain it thank u @mysteri0us

9

your solution does not handle the case when mex is decreased
b[j] > b[i] (0 <= j < i)
5
0 -1 -1 3 2
expected -1
I think testcases were weak

1 Like
11

At any index prefix mex can be made equal to [cur_mex, cur_mex + count(previous indices where you can put some value)]. So I used stack to store indices of previous unused (-1)'s and pop them after using. You can also use a queue or vector or set instead.

12

Yes I forgot to add a condition for that trivial case. I guess there is no test case of that type.

13

If i am not wrong you are finding the position of the iterator using lower_bound.In that case the time complexity of the erase function is O(n) since whenever you delete an element, the other elements have to be shifted by 1 place. That is why the total complexity becomes of the order O(n^2).
The erase function will work only if you erase either the first or last element in each operation. Hope that helps!

14

Can anyone explain what am I missing here
for the testcase [0, -1, 2, -1, 5, -1, -1]
0<=2<3
and B2>B3, If this holds up then how is this a valid testcase, i.e the answer isn’t -1 ? if not then what am I missing?

15

Don’t consider indices with value -1 while checking this.

1 Like
17

Hey @jedi21 :wave:
In your code you are not considering the case of duplicate b[i] >= 0.