PERMCLEAR - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Jeevan Jyot Singh
Testers: Utkarsh Gupta, Hriday
Editorialist: Nishank Suresh

DIFFICULTY:

1308

PREREQUISITES:

None

PROBLEM:

Alice has a permutation of \{1, 2, \ldots, N\}. She dislikes K of these numbers B_1, \ldots, B_K. Can you print the permutation with these numbers removed?

EXPLANATION:

This is an implementation problem more than anything else — it is enough to do exactly what is asked for.

Iterate across the values of A. Say we are currently at A_i, and we want to know whether to print it or not.
All that we really need to know is whether A_i is one of the elements of B, and to check this faster than \mathcal{O}(N) (since the constraints are such that \mathcal{O}(N^2) algorithms will TLE).

This check can be done in \mathcal{O}(\log N) or even \mathcal{O}(1), in several ways:

  • The easiest way is to use the set data structure present in most languages. Insert all the elements of B into a set S, then simply check if A_i is in S. This check is \mathcal{O}(\log N) in C++ set and Java TreeSet, and \mathcal{O}(1) in python set and Java HashSet.
  • Alternately, we can use an array. Note that all the elements are from 1 to N, so we can create an array mark of length N, such that mark_i is 1 if i is present in B and 0 otherwise. Now, we only need to look at mark_{A_i} to decide if A_i is in B, which takes \mathcal{O}(1) time.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = set(map(int, input().split()))
	for x in a:
		if x not in b:
			print(x, end = ' ')
	print('')
1 Like

please provide c++ code someone, is it possible to solve this one without STL ??

2 Likes

The second method mentioned in the editorial needs only an array and no other data structure. Here is an implementation in C++.

I will say though, in general if a problem can be easily solved using STL you might as well use it, it exists in the language for a reason.

2 Likes
#include<bits/stdc++.h>
using namespace std;
#define fo(ini,n) for(int i=ini; i<n; i++)
#define ll long long
void solve();
int main(){
  int t;cin>>t;
  while(t--){
    solve();
  }
  return 0;
}
void solve(){
  int n;
  unordered_set<int> ms;
  cin>>n;
  int arr[n];
  fo(0,n){
      cin>>arr[i];
      ms.insert(arr[i]);
  }
  int k;cin>>k;
  int brr[k];
  fo(0,k){
      cin>>brr[i];
      ms.erase(brr[i]);
  }
  for(auto values : ms){
      cout<<values<<" ";
  }
  cout<<endl;
}[quote="iceknight1093, post:1, topic:102899, full:true"]
# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/PERMCLEAR)
[Contest: Division 1](https://www.codechef.com/START55A/problems/PERMCLEAR)
[Contest: Division 2](https://www.codechef.com/START55B/problems/PERMCLEAR)
[Contest: Division 3](https://www.codechef.com/START55C/problems/PERMCLEAR)
[Contest: Division 4](https://www.codechef.com/START55D/problems/PERMCLEAR)

***Author:*** [Jeevan Jyot Singh](https://www.codechef.com/users/JeevanJyot)
***Testers:*** [Utkarsh Gupta](https://www.codechef.com/users/utkarsh_25dec), [Hriday](https://www.codechef.com/users/the_hyp0cr1t3)
***Editorialist:*** [Nishank Suresh](https://www.codechef.com/users/IceKnight1093)

# DIFFICULTY:
To be decided

# PREREQUISITES:
None

# PROBLEM:
Alice has a permutation of $\{1, 2, \ldots, N\}$. She dislikes $K$ of these numbers $B_1, \ldots, B_K$. Can you print the permutation with these numbers removed?

# EXPLANATION:
This is an implementation problem more than anything else — it is enough to do exactly what is asked for.

Iterate across the values of $A$. Say we are currently at $A_i$, and we want to know whether to print it or not.
All that we really need to know is whether $A_i$ is one of the elements of $B$, and to check this faster than $\mathcal{O}(N)$ (since the constraints are such that $\mathcal{O}(N^2)$ algorithms will TLE).

This check can be done in $\mathcal{O}(\log N)$ or even $\mathcal{O}(1)$, in several ways:
- The easiest way is to use the `set` data structure present in most languages. Insert all the elements of $B$ into a set $S$, then simply check if $A_i$ is in $S$. This check is $\mathcal{O}(\log N)$ in C++ `set` and Java `TreeSet`, and $\mathcal{O}(1)$ in python `set` and Java `HashSet`.
- Alternately, we can use an array. Note that all the elements are from $1$ to $N$, so we can create an array $mark$ of length $N$, such that $mark_i$ is $1$ if $i$ is present in $B$ and $0$ otherwise. Now, we only need to look at $mark_{A_i}$ to decide if $A_i$ is in $B$, which takes $\mathcal{O}(1)$ time.

# TIME COMPLEXITY
$\mathcal{O}(N)$ per test case.

# CODE:
[details = Editorialist's code (Python)]
```python
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = set(map(int, input().split()))
	for x in a:
		if x not in b:
			print(x, end = ' ')
	print('')

[/details]
[/quote]

I am using an unordered set still my order is getting disturbed pls help

Yes you can, just use array instead of vector in my submission: CodeChef

1 Like

I was struggling with TLE for this one, here’s my solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin>>t;

    while(t--) {
        int n , k;
        cin>>n;
        int arr[n];
        for(int i = 0; i < n; i++) {
            cin>>arr[i];
        }
        cin>>k;
        int arr2[k];
        for(int i = 0 ; i < k ; i++) {
            cin>>arr2[i];
        }
        int arr3[n-k] = {0};
        int l = 0;
        for(int i = 0 ; i < n ; i++) {
            int flag = 0;
            for(int j = 0 ; j < k ; j++) {
                if(arr[i] == arr2[j]) {flag = 1; break;}
            }
            if(!flag) {
                cout<<arr[i]<<' ';

            }
        }
     cout<<endl;
    }
    return 0;
}

Unordered set uses hashing, and does not guarantee anything about the order of elements inserted into it.

You can read its documentation here.

1 Like

Indeed, that solution will get TLE. As mentioned in the editorial, the bruteforce method of checking whether a given element exists in B will lead to a \mathcal{O}(N^2) solution, which is why you need to do something better. In this case, “better” means either using an appropriate data structure or a mark array.

1 Like

Mark array means?

1 Like

Read the second method mentioned in the editorial and/or look at the code linked in my first comment.

2 Likes

This was a fun one.
This pushes us to find a way to avoid the terrible exponential complexity, while comparing if one element exists in the A list.
I ended up using an unordered_map (C++) to save the position of each element. Then, considering each element of the A array is always greater than 0, so when second K list is given, I only modify the value to 0.
unordered_map has a constant complexity on average.

Just to complete the explanation of the problem. C++'s unordered_set also has a constant complexity according to this:
https://cplusplus.com/reference/unordered_set/unordered_set/find/

A small correction: unordered_map and unordered_set both use hashmaps in C++.

In particular, it’s wrong to say that unordered_map is logarithmic and that unordered_set works in constant time.
The truth is that they both work in \mathcal{O}(1) on average. However, under certain circumstances (which do not apply to this problem, but may apply to others), it is possible to force both to work in \mathcal{O}(N), because that is the worst-case time complexity (you can see that your link says the same thing).

In fact, if you participate in a Div3 or Educational contest on Codeforces and use unordered_map/unordered_set, it is highly likely that somebody will hack your solution and cause it to fail.

Just something to keep in mind, I don’t recommend using them if you aren’t fully familiar with when they can be forced into worst-case performance.

(Just to note, the normal map and set use a BBST as their underlying data structure, and so do provide \mathcal{O}(\log N) in the worst case)

2 Likes

I’m so sorry! You are completely right.
I was thinking that, them both using hashmaps, but I don’t know why I ended up writing unordered were logarithmic, ha!

I don’t remember exactly how the problems goes, but on average when there are not that many elements, it works fine. I usually use it when I estimate <2e5 elements, but that is my experience. I have no further knowledge over the exact criteria both use to create the hash.

I appreciate your comment, I’ll edit it to avoid confusions.