By AdnanShamsi, history, 6 months ago,

# Sliding Cost

Can someone explain how to approach this problem.

I was trying to do it using pdbs and fenwick tree but it showed me tle on last 4 test cases
https://pastebin.com/3qBy2WBW

• 0

 » 6 months ago, # |   0 Auto comment: topic has been updated by AdnanShamsi (previous revision, new revision, compare).
 » 6 months ago, # |   0 Why you erase the upper_bound() here? I would have expected to erase to lower_bound().ms.erase(ms.ub(arr[head - k]));But maybe I did understand the code wrong.
•  » » 6 months ago, # ^ |   +3 in pdbs multiset upper_bound work as lower_bound vice-versa https://codeforces.com/blog/entry/11080?#comment-533322
 » 4 months ago, # |   0 Hi, did you solve this problem, I'm also stuck on this. Saw few solutions on github having Fenwick tree in them, but couldn't the idea.
•  » » 4 months ago, # ^ | ← Rev. 4 →   +1 there is a better solution to this which i couldnt understand so i did a straightword solution which gave me AC.i have a pbds — which contains all elements of current window — now i can get the median of the currennt window in log(n)now 2 FWTs I used for — 1) count of certain element2) sumso for e.g. if i have a window 2 2 3, fwt1[2] = 2 and fwt1[3] = 1 and fwt2[2] = 4 and fwt2[3] = 3now all i need is for each window is — elements above it, sum of elements above it, elements below it, sum of elements below it.since number range is large i used cordinate compression.look at the 7 lines i marked in my code and hopefully you will understand more CODE#include #include #include using namespace std; using namespace __gnu_pbds; #define ll long long #define sz 200100 typedef tree, null_type, less>, rb_tree_tag, tree_order_statistics_node_update> pbds; ll sm[sz]; ll cnt[sz]; void upd(ll idx, ll tr[], ll add) { while (idx < sz) { tr[idx] += add; idx += (idx & (-idx)); } } ll que(ll idx, ll tr[]) { ll sum = 0; while (idx) { sum += tr[idx]; idx -= (idx & (-idx)); } return sum; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, k, idx, mid, cntlow, cnthigh, sumlow, sumhigh, low, high; cin >> n >> k; vectora(n), b(n); pbds s; for (ll i = 0; i < n; i++) { cin >> a[i]; b[i] = a[i]; } sort(b.begin(), b.end()); for (ll i = 0; i < k; i++) { idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1; upd(idx, sm, a[i]); upd(idx, cnt, 1); s.insert({a[i], i}); } for (ll i = k; i < n; i++) { mid = (*s.find_by_order(k / 2)).first; idx = lower_bound(b.begin(), b.end(), mid) - b.begin() + 1; // look at the next 7 lines everything will be clear cntlow = que(idx - 1, cnt); sumlow = que(idx - 1, sm); cnthigh = que(n + 1, cnt) - que(idx, cnt); sumhigh = que(n + 1, sm) - que(idx, sm); high = sumhigh - (cnthigh * mid); low = (cntlow * mid) - sumlow; cout << low + high << " "; idx = lower_bound(b.begin(), b.end(), a[i - k]) - b.begin() + 1; upd(idx, sm, -a[i - k]); upd(idx, cnt, -1); s.erase({a[i - k], i - k}); idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1; upd(idx, sm, a[i]); upd(idx, cnt, 1); s.insert({a[i], i}); } mid = (*s.find_by_order(k / 2)).first; idx = lower_bound(b.begin(), b.end(), mid) - b.begin() + 1; cntlow = que(idx - 1, cnt); sumlow = que(idx - 1, sm); cnthigh = que(n + 1, cnt) - que(idx, cnt); sumhigh = que(n + 1, sm) - que(idx, sm); high = sumhigh - (cnthigh * mid); low = (cntlow * mid) - sumlow; cout << low + high << endl; return 0; } 
•  » » » 4 months ago, # ^ |   +1 Thanks for explanation. Now I got it.
 » 4 months ago, # |   0 We can do this by using the prefix sum array and median of the subarray of size k of the given array . As median is the closest point to all the numbers in the subarray of k size.
•  » » 2 months ago, # ^ |   0 Using prefix sum array won't work in regard with computing the cost of converting each number to the median in a subarray, right? Because you can not say the cost is simply subarray's sum — subarray's size * its median value.
 » 4 months ago, # |   0 Here's my implementation with BIT. First tree is for storing the cumulative frequency and second one is for storing elements in the current window. code#include using namespace std; void add(int i, vector &a, long long d) { i++; int n=a.size(); while(i &a) { i++; long long ans=0; while(i) { ans+=a[i]; i-=i&-i; } return ans; } int find(vector &a, int target) { int low=0, high=a.size()-2, mid; while(low>n>>k; vector givenOrder(n), active(n+1, 0), cumlativeF(n+1, 0); vector> numToIndex(n); for(i=0; i>givenOrder[i]; numToIndex[i].first=givenOrder[i]; //storing the initial index numToIndex[i].second=i; } //order for BIT sort(numToIndex.begin(), numToIndex.end()); for(i=0; i=k-1) { //find the index of median in the cumlativeF array index=find(cumlativeF, (k+1)/2); //make every element equal to median for minimum cost cost=sum(n-1, active)-2*sum(index, active)+(k%2?numToIndex[index].first:0); cout<