I have done using deque and map but it is giving WA, but it is passing most of my trial test cases, please somebody give me some extra testcases where my code fails or tell me what is wrong in this logic
https://www.codechef.com/viewsolution/47095605
thank you
i am doing this using binary search time complexity will be M logM but it giving TLE can anybody help please , my approach is correct i think there is some mistake in implementation
approach : let say ans is x , then check ans is possible or not if possible the search for below
otherwise for above ans , please help @cubefreak777
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define rep(i,a,b) for(int i=a; i<b; i++)
#define rrep(i,a,b) for(int i=a; i>=b; i--)
#define pb(i) push_back(i)
#define all(b) b.begin(),b.end()
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
// template<class T> using oset =tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update> ;
// st.find_by_order(k); // returns element at position k(0 based indexing)
// st.find_of_key(k); // number of element <k
// st.order_of_key(k); // return order of k
// less_equal<T> : as multiset
// less<T> : only set
const int mod = 1e9 + 7;
const int inf = 1e10 + 20;
const int mxn = 1e5 + 1;
bool check(vector<int>&v,int k,int n){
int len = v.size();
int l = 0, r = len - k;
map<int,int> m;
for(int i=r; i<len; i++){
m[v[i]]++;
}
if(m.size()==n) return true;
for(int i=0; i<k; i++){
int r = len - (k - i);
m[v[r]]--;
if(m[v[r]]==0){
m.erase(v[r]);
}
m[v[i]]++;
if(m.size()==n) return true;
}
return m.size()==n;
}
void test_case(){
int n,m; cin>>n>>m;
vector<int> v(m,0);
for(int i=0; i<m; i++){
cin>>v[i];
}
int l = 1, r = m;
int ans = 0;
while(l<=r){
int mid = (l + r)/2;
if(check(v,mid,n)){
ans = mid;
r = mid - 1;
}
else{
l =mid + 1;
}
}
cout<<ans;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1; cin>>t;
while(t--){
test_case();
cout<<'\n';
}
return 0;
}
hey i was also trying to solve the question using the similar greedy approach as you! I took me some time but i found test cases that this method won’t solve.
Try this array and you’ll understand: 1 1 3 1 1 1 2 2
Bro, Can you explain your code?. Your code looks much simpler to me
I have written the following code with the same kind of approach.
But it gives me WA on the 4th Test case.
can anyone guide me on what may be potentially missing or wrong?
Am I missing a test case or something like that?
CODE:
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define mod 1000000007
#define infinity 1e18
#define endl "\n"
#define maxValue(var) numeric_limits<var>::max()
#define minValue(var) numeric_limits<var>::min()
#define pll pair<ll, ll>
#define mp make_pair
#define ff first
#define ss second
#define vll vector<ll>
#define pb push_back
#define vs vector<string>
#define ump unordered_map
#define pq_max(var) priority_queue <var>
#define pq_min(var) priority_queue <var, vector<var>, greater<var> >
#define all(v) v.begin(), v.end()
#define mid(l, r) (l + (r-l)/2)
#define bitc(x) __builtin_popcountll(x)
#define fori(i,a,b) for(int i = (a) ; i < (b) ; i++)
#define foriRev(i,a,b) for(int i = (a) ; i >= (b) ; i--)
#define iterate(c, it) for(__typeof(c.begin()) it = c.begin() ; it!= c.end() ; it++)
#define display(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);}
#define displayArr(arr, a, b) for(int z=(a) ; z<=(b) ; z++) cout << arr[z] << " "; cout << endl;
#define scanVec(vec) for(int z=(0) ; z<(vec.size()) ; z++) cin >> vec[z];
#define printVec(vec) for(int z=(0) ; z<(vec.size()) ; z++) cout << vec[z] << " "; cout << endl;
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args){
cout << *it << " = " << a << endl;
err(++it, args...);
}
void fastInOut(){
// fast input/output
ios_base::sync_with_stdio(false);
// NULL <---> 0
cin.tie(NULL);
cout.tie(NULL);
}
void myCode(){
ll tc; cin >> tc;
fori(t, 0, tc){
ll res, n, m; cin >> n >> m;
res = m;
vll arr(m); scanVec(arr);
if(n == m){
cout << res << endl;
continue;
}
if(n == 1){
cout << 1 << endl;
continue;
}
ll l = 0;
ll r = 0;
unordered_map<int, int> f;
f[arr[0]]++;
while (l < m+1){
while(f.size() != n){
r++;
f[arr[(r)%m]]++;
}
while(f.size() == n){
// condition for proper subarray
if(l%m == 0 or r%m == m-1 or l%m > r%m)
res = min(r-l+1, res);
f[arr[l%m]]--;
if(f[arr[l%m]] == 0) f.erase(arr[l%m]);
l++;
}
}
cout << res << endl;
}
}
int main(int argc, char const *argv[]){
fastInOut();
myCode();
return 0;
}I store the rightmost occurrences of all numbers from 1 to n and dump all of them in a set(note that all of them would be unique so we don’t have to handle duplicates) and then we iterate over all indices from 1 to m deleting the right indices of the numbers which we’ve encountered. and check what is the number of elements that I’ve to delete from the right end and it’s trivial to see that it’d just be the greatest value in the set as it hasn’t been covered by the right end and is most deeply embedded in the array, and just take the min overall indices.
Example:
A=[1,2,3,2,1,1,2]
R=[2,1,5]
S=[1,2,5] (sorted R)
Here R_i represents the minimum number of elements that we have to delete from the right end to encounter the first occurrence of i. → R_1=2 as we have to delete at least 2 elements to encounter a 1,R_3=5 as we have to delete at least 5 elements from right to encounter a 3.
Now we iterate on A and calculate the answer for each index.
similarly for all i \le M
and taking minimum over all indices gives 3 (min(6,7,3…)) as the answer
I think I chose a stupid example, but the idea should be clear I suppose, do let me know if it isn’t.
@cfacto
Great Editorial !
Mine is similar but with O(m + nlogn).
Considering for each unique number, use (leftmost occurrence, -rightmost occurrence) as a 2-D point to present the number.
Then for a (i, j) (pop i from left and j from right), the number of points that are not occur are in the area where x > i && y > j.
So sliding the points from the bigest x, then required minimum y is the largest y in the area that has already slided…
I did it here you can check it
in last cases it fails i don’t know why ,
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ff first
#define ss second
#define pb push_back
#define mkp make_pair
#define pii pair<int , int>
#define nl printf("\n") ;
#define pn printf(“NO\n”) ;
#define py printf(“YES\n”) ;
#define fill(a , x) memset(a , x , sizeof(a)) ;
#define vvi vector<vector>
#define vi vector
const int mod = 1e9 + 7 , N = 4e6 + 2 ;
bool cmp(pii& a , pii& b){
if(a.ss != b.ss) return a.ss < b.ss ;
else return a.ff < b.ff ;
}
int modval(int n){ return n % mod ; }
int modadd(int a , int b){ return modval(modval(a) + modval(b)) ; }
int modsub(int a , int b){ return modval(modval(a) + modval(modadd(mod , -b) + mod)) ; }
int modmul(int a , int b){ return modval(modval(a) * modval(b)) ; }
void chef_subarrays(){
int n , m ;
cin >> n >> m ;
int a[n + 1] , b[n + 1] , arr[m + 1] ;
for(int i = 1 ; i <= n ; i++) a[i] = -1 , b[i] = -1 ;
stack st ;
st.push(0) ;
for(int i = 1 , x ; i <= m ; i++){
cin >> arr[i] ;
if(a[arr[i]]==-1) a[arr[i]] = i , st.push(i) ;
b[arr[i]] = i ;
}
int x , y = m , ans = m ;
while(not st.empty()){
x = st.top() , st.pop() ;
if(x!=0){
y = min(b[arr[x]] , y) ;
x = st.top() ;
ans = min(x + m - y + 1 , ans) ;
}
}
printf("%lld\n",ans) ;
}
int32_t main() {
// your code goes here
int t = 1 ;
scanf("%lld",&t) ;
while(t–) chef_subarrays() ;
return 0;
}
but in the below i’ve just added reverse traversal of previous , then it goes right
can someone tell me why it’s happening 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ff first
#define ss second
#define pb push_back
#define mkp make_pair
#define pii pair<int , int>
#define nl printf("\n") ;
#define pn printf(“NO\n”) ;
#define py printf(“YES\n”) ;
#define fill(a , x) memset(a , x , sizeof(a)) ;
#define vvi vector<vector>
#define vi vector
const int mod = 1e9 + 7 , N = 4e6 + 2 ;
bool cmp(pii& a , pii& b){
if(a.ss != b.ss) return a.ss < b.ss ;
else return a.ff < b.ff ;
}
int modval(int n){ return n % mod ; }
int modadd(int a , int b){ return modval(modval(a) + modval(b)) ; }
int modsub(int a , int b){ return modval(modval(a) + modval(modadd(mod , -b) + mod)) ; }
int modmul(int a , int b){ return modval(modval(a) * modval(b)) ; }
void chef_subarrays(){
int n , m ;
cin >> n >> m ;
int a[n + 1] , b[n + 1] , arr[m + 1] ;
for(int i = 1 ; i <= n ; i++) a[i] = -1 , b[i] = -1 ;
stack st ;
st.push(0LL) ;
for(int i = 1 , x ; i <= m ; i++){
cin >> arr[i] ;
if(a[arr[i]]==-1) a[arr[i]] = i , st.push(i) ;
b[arr[i]] = i ;
}
int x , y = m , ans = m ;
while(not st.empty()){
x = st.top() ;
st.pop() ;
if(x!=0){
y = min(b[arr[x]] , y) ;
x = st.top() ;
ans = min(x + m - y + 1 , ans) ;
}
}
for(int i = 1 ; i <= n ; i++) a[i] = -1 , b[i] = -1 ;
st.push(m+1) ;
for(int i = m ; i >= 1 ; i–){
if(a[arr[i]]==-1) a[arr[i]] = i , st.push(i) ;
b[arr[i]] = i ;
}
y = 0 ;
while(not st.empty()){
x = st.top() ;
st.pop() ;
if(x!=m+1){
y = max(y , b[arr[x]]) ;
x = st.top() ;
ans = min(y + m - x + 1 , ans) ;
}
}
printf("%lld\n",ans) ;
}
int32_t main() {
// your code goes here
int t = 1 ;
scanf("%lld",&t) ;
while(t–) chef_subarrays() ;
return 0;
}
Can some one please explain me how to write the code in python.
I have understood the logic but unable to write the code.
man your code is super complicated. please explain it …looks way more compact tho
awesome solution
Hopefully you have got what his isGood function is doing if not then;
int r=mid;
now he is creating a new map and puting elements from r to m .
he is iterating from r=mid to m and keep on removing the rth item and adding the left item from index zero to make sure he has the map size of binary search answer.
if now map size is n then he is sure that removing mid no. of elements are giving the result. Now he is going to search for the minimum answer .
hello, can anyone help me to find what wrong here? CodeChef: Practical coding for everyone
i am just trying to solve this problem with dp , i know it will gave me TLE, but i expected that for other tc i will get AC. Please tell me whats wrong with my approach .
Can you tell me why both below codes are different .
one is AC and second is WA (for 1 test cases);
Code1(AC) : CodeChef: Practical coding for everyone
Code2(WA): CodeChef: Practical coding for everyone
Wrong:
if(!s.empty())
{
Min=s.begin();
Max=(s.rbegin());
l=Max-Min+1;
}
Right:
if(!s.empty())
{
Min=(s.begin());
// Max=(s.rbegin());
l=m-Min;
}
Why we can’t use *(s.rbegin()) for finding max-elemnt frpm set? I also checked on gfg it is correct: Find Maximum and Minimum element in a Set in C++ STL - GeeksforGeeks .
Please help me
Thanks
Can anybody tell me why both below codes are different .
one is AC and second is WA (for 1 test cases);
Code1(AC) : CodeChef: Practical coding for everyone
Code2(WA): CodeChef: Practical coding for everyone
Wrong:
if(!s.empty())
{
Min=s.begin();
Max=(s.rbegin());
l=Max-Min+1;
}
Right:
if(!s.empty())
{
Min=(s.begin());
// Max=(s.rbegin());
l=m-Min;
}
Why we can’t use *(s.rbegin()) for finding max-elemnt frpm set? I also checked on gfg it is correct: Find Maximum and Minimum element in a Set in C++ STL - GeeksforGeeks .
Please help me
Thanks
1
4 9
4 3 3 1 2 1 4 3 3
your AC code gives: 5
your wrong code gives: 4
this is so because you are required to pop all the elements from the last till minimum index in the set. But doing s.rbegin() indicates that you are popping elements in the range max to min. where max is not necessarily the last index of given array.
I hope its clear.
Yes clear thanks 
Can you please explain your code a little bit?
line 54 to 60