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: Practical coding for everyone
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
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.