→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
29:29:45
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

AdnanShamsi's blog

Help needed in CSES Problem

By AdnanShamsi, history, 4 years ago, In English

Sliding Cost

https://cses.fi/problemset/task/1077

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

cses, #sorting, searching

AdnanShamsi
4 years ago
14

Comments (11)

Show archived | Write comment?

spookywooky

4 years ago, # |

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.

→ Reply

AdnanShamsi

4 years ago, # ^ |

in pdbs multiset upper_bound work as lower_bound vice-versa https://codeforces.net/blog/entry/11080?#comment-533322

→ Reply

tautology

4 years ago, # |

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.

→ Reply

Shameek

4 years ago, # ^ |

← Rev. 4 →

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 element

2) sum

so 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] = 3

now 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<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define sz 200100
typedef tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, 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;
	vector<ll>a(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;
}

→ Reply

tautology

4 years ago, # ^ |

Thanks for explanation. Now I got it.

→ Reply

Atul2608

4 years ago, # |

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.

→ Reply

NerfThis

4 years ago, # ^ |

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.

→ Reply

bipinpathak

4 years ago, # |

← Rev. 2 →

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 <bits/stdc++.h>
using namespace std;
void add(int i, vector<long long> &a, long long d) {
    i++;
    int n=a.size();
    while(i<n) {
        a[i]+=d;
        i+=i&-i;
    }
}
long long sum(int i, vector<long long> &a) {
    i++;
    long long ans=0;
    while(i) {
        ans+=a[i];
        i-=i&-i;
    }
    return ans;
}
int find(vector<long long> &a, int target) {
    int low=0, high=a.size()-2, mid;
    while(low<high) {
        mid=low+(high-low)/2;
        if(sum(mid, a)<target) {
            low=mid+1;
        } else {
            high=mid;
        }
    }
    return low;
}
void solve() {
    int n, k, i, index;
    long long cost;
    cin>>n>>k;
    vector<long long> givenOrder(n), active(n+1, 0), cumlativeF(n+1, 0);
    vector<pair<long long, int>> numToIndex(n);    
    for(i=0; i<n; i++) {
        cin>>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<n; i++) {
        givenOrder[numToIndex[i].second]=i;
        //givenOrder[i] = index of element in BIT
    }
    for(i=0; i<n; i++) {
        //add givenOrder[i] to window
        add(givenOrder[i], cumlativeF, 1);
        add(givenOrder[i], active, numToIndex[givenOrder[i]].first);
        if(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<<cost<<" ";            
            //removing givenOrder[i-k+1] for future windows
            add(givenOrder[i-k+1], cumlativeF, -1);
            add(givenOrder[i-k+1], active, -1*numToIndex[givenOrder[i-k+1]].first);
        }
    }
    cout<<endl;
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

→ Reply

puspendra_09

16 months ago, # |

Sorry for necroposting, but this problem can be solved by using multiset only ..
maintain two multiset, first one will contain elements smaller (k + 1) / 2 elements while the second multiset will contain largest (k / 2) elements of a subarray of size k.

This problem is the advanced version of this problem Link with also delete operations.

Code

void solve() { int n , k; cin >> n >> k;

int a[n];
for(int i = 0; i < n; i++) {
    cin >> a[i];
}

multiset<int> smaller , bigger;

int i = 0 , j = 0;
int sumSmaller = 0 , sumBigger = 0;

while(j < n) {
    if(smaller.size() == bigger.size()) {
       bigger.insert(a[j]);
       int ele = *bigger.begin();
       bigger.erase(bigger.begin());
       smaller.insert(ele);
       sumSmaller += ele;
       sumBigger -= ele;
       sumBigger += a[j];
    }
    else {
       sumSmaller += a[j];
       smaller.insert(a[j]);
       int ele = *smaller.rbegin();
       sumSmaller -= *smaller.rbegin();
       smaller.erase(--smaller.end());
       bigger.insert(ele);
       sumBigger += ele;
    }

    if(j - i + 1 < k) {
       j++;
    }
    else if(j - i + 1 == k) {
       int median = *smaller.rbegin();
       int ans = 0;
       ans += smaller.size() * median - sumSmaller;
       ans += sumBigger - bigger.size() * median;

       cout << ans << " ";

       int temp = a[i];
       if(smaller.find(temp) != smaller.end()) {
         if(smaller.size() == bigger.size()) {
          int eles = *bigger.begin();
          bigger.erase(bigger.begin());
          smaller.insert(eles);
          sumSmaller += eles;
          sumBigger -= eles;
         }
         sumSmaller -= temp;
         smaller.erase(smaller.find(temp));
       }
       else {
         if(smaller.size() != bigger.size()) {
          int eles = *smaller.rbegin();
          smaller.erase(--smaller.end());
          bigger.insert(eles);
          sumSmaller -= eles;
          sumBigger += eles;
         }
         sumBigger -= temp;
         bigger.erase(bigger.find(temp));
       }
       i++;
       j++;
    }
}

}

→ Reply

xruto

16 months ago, # |

← Rev. 2 →

Here is my solution : ) Tags of my solution 1) BIT tree 2) Two Pointers 3) Compressing 4) STL

Code :https://ideone.com/BUXxJO

→ Reply

hydra_cody

11 months ago, # |

← Rev. 2 →

Easily Code with priority queue

  ll n,k;
  cin>>n>>k;
  vl aa(n);
  fo(i,n){
    cin>>aa[i];
  }
  prq_mx<pl> l;
  prq_mn<pl> r;
  ll mid=(k+1)/2;
  ll c=0;
  ll lsum=0,rsum=0;
  fo(i,n){
    while(Sz(l) && l.top().se<=(i-k))l.pop();
    while(Sz(r) && r.top().se<=(i-k))r.pop();
    if(c<mid){
      r.push({aa[i],i});
      rsum+=aa[i];
      l.push(r.top());
      lsum+=r.top().fi;
      rsum-=r.top().fi;
      r.pop();
      c++;
    }else{
      l.push({aa[i],i});
      lsum+=aa[i];
      r.push(l.top());
      rsum+=l.top().fi;
      lsum-=l.top().fi;
      l.pop();
    }
    if(i-k+1<0)continue;
    ll med=l.top().fi;
    ll ans1=(mid*med)-lsum + rsum-((k-mid)*med );
    cout<<ans1<<" ";
    if(aa[i-k+1]<=l.top().fi){
      lsum-=aa[i-k+1];
      c--;
    }else rsum-=aa[i-k+1];
  }
  cout<<nline;

→ Reply