### Mafia2's blog

By Mafia2, history, 4 weeks ago, NOTE — This problen is not the from any ongoing contest. You are given an array of N integers. X[i] is the number of distinct values that occur to the left of index i and not on or to the right of index i. Y[i] is the number of distinct values that occur to the right of index i and not on or to the left of index i. Determine the absolute difference of X[i] , Y[i] for every index 1 <= i <= N. ****Constraint**** 1<=T<=10 1<=N<=2*10^5 -10^9<=Ai<=10^9 Comments (13)
 » You can't just say This problen is not the from any ongoing contest without stating where you got it from. That's extremely sus.However, I think this is from Ode 2 Code Round 2, which has already ended, so I think it's safe to put a solution here. I won't until someone else confirms it though.
•  » » So,if the contest has already ended,then I think you can share your solution.
•  » » » Put a link to the contest and proof that it has ended, otherwise I cannot let myself post the solution knowing that you may be cheating.
•  » » » » The contest was ODE 2 CODE ,on visiting the site again it says you cannot attend this test as it has already ended.And I don't know how to add screenshot so that I can give you proof.
•  » » Yeah, I can confirm this is from Ode 2 code only.
 » Now it has been 3 days to post this question and there are so many great coders at this community, so plz anyone can tell me how to solve this question?
 » 4 weeks ago, # | ← Rev. 2 →   Seems to work on my tests, but I don't have ways to verify it) ~~~~~ Spoiler#include /*Author: _KitCat_*/ #pragma GCC optimize ("O3") #define ll long long #define pii pair #define vi vector #define pb push_back #define mp make_pair #define um unordered_map #define iospeed cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0); #define fin for(int i = 0; i < n; i++) #define rep(a,b,c) for(int a = b; a < c; a++) #define TESTS int tests; cin >> tests; while(tests--) #define nl '\n' #define print(STRUCT) for(auto VALUE : STRUCT) cout << VALUE << ' '; cout << endl; #define all(x) x.begin(), x.end() #define int long long #define f first #define s second using namespace std; struct Comparator{ bool operator() (const pair& lhs,const pair& rhs) const{ if (lhs.first == rhs.first) return lhs.second < rhs.second; return lhs.first < rhs.first; } bool operator() (int a, int b) const {return a > b;} }; void solve(){ int n; cin >> n; vi arr(n); map count; //remember how many times each element occurs fin { cin >> arr[i]; ++count[arr[i]]; } vi x(n); vi y(n); set S; //set keeps distinct elements that occur to the left of //current index and wont be futhermore fin{ x[i] = S.size(); --count[arr[i]]; if(count[arr[i]] == 0) S.insert(arr[i]); //if there would be no more such elements to the right of current index //we can add it to our set } //resetting set and map S.clear(); count.clear(); fin ++count[arr[i]]; for(int i = n-1; i >= 0; i--){ y[i] = S.size(); --count[arr[i]]; if(count[arr[i]] == 0) S.insert(arr[i]); } fin{ cout << abs(x[i]-y[i]) << ' '; } } signed main() { iospeed; TESTS solve(); return 0; } ~~~~~
•  » » Although you have added comments in your code but can you plz elaborate your thought process what you have done.
•  » » » To solve this problem we need to 1) calculate values in array X, 2) calculate values in array Y, 3) get answer by counting absolute differens between |X[i] — Y[i]|. Actually method of calculating values in array X and Y is almost the same (you can see that in code, for X we just start from the beginning and for Y from the end). So the only thing we need to understand is how to calculate array X. What is the value of the first element X? Obviously it is 0, as there are no items before element at 0 position. And what is the answer for X? If there no elements equal to arr in range [1, n) X = 1, otherwise X = 0. So basicly to find out X[i] we need to know the value of X[i-1] and how many times arr[i] occurs in range (i, n). One of the way to do it is using MAP. (if constraints would allow, we actually could use simple array, where at some index j we will keep how many times j occurs in arr (for example if we have arr = [1,2,2,5,4,5,3,5], our array that count how many times each element occurs would be [0, 1, 2, 1, 1, 3]), but we cannot create such big array (10^9) as we will get TimeLimit or MemoryLimit, so we will use map.) Now for some position i we know if element arr[i-1] will occur later in the array. If it will, we don't need to do anything, but if is won't X[i] = X[i-1] + 1. Thats it! I wrote a little bit overcomplicated code, adding easier version with some comments. Spoiler#include /*Author: _KitCat_*/ #pragma GCC optimize ("O3") #define ll long long #define pii pair #define vi vector #define pb push_back #define mp make_pair #define um unordered_map #define iospeed cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0); #define fin for(int i = 0; i < n; i++) #define rep(a,b,c) for(int a = b; a < c; a++) #define TESTS int tests; cin >> tests; while(tests--) #define nl '\n' #define print(STRUCT) for(auto VALUE : STRUCT) cout << VALUE << ' '; cout << endl; #define all(x) x.begin(), x.end() #define int long long #define f first #define s second using namespace std; struct Comparator{ bool operator() (const pair& lhs,const pair& rhs) const{ if (lhs.first == rhs.first) return lhs.second < rhs.second; return lhs.first < rhs.first; } bool operator() (int a, int b) const {return a > b;} }; void solve(){ int n; cin >> n; vi arr(n); map count; //remember how many times each element occurs fin { cin >> arr[i]; ++count[arr[i]]; } vi x(n); vi y(n); x = 0; //there are no elements before element at index 0 y[n-1] = 0; //there are no elements after elment at last index for(int i = 1; i < n; i++){ x[i] = x[i-1]; --count[arr[i-1]]; if(count[arr[i-1]] == 0) x[i]++; } //resetting map count.clear(); fin ++count[arr[i]]; for(int i = n-2; i >= 0; i--){ y[i] = y[i+1]; --count[arr[i+1]]; if(count[arr[i+1]] == 0) y[i]++; } fin{ cout << abs(x[i]-y[i]) << ' '; } } signed main() { iospeed; TESTS solve(); return 0; } `
 » I thinks maintaining 2 map ( 1 for the left part (initially empty) and other for the right-part (initially contains all elements)) and when you iterate from left to right you have to increase the left[a[i]]++ and right[a[i]]-- ( and when right[a[i]]==0 then just erase it from the right map). and just take the difference between the size of these two map and just print it for each indexes. I think this will work if i am not wrong.
 » Anyone got test link for round 3?
•  » » Me
 » For each ai, find it's contribution to X[i] and Y[i]. Something like : for ai, all i > last occurence of ai, it will contribute in X. Similarly for Y