AdnanShamsi's blog

Help needed in CSES Problem
By AdnanShamsi, history, 6 months 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

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (9)
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by AdnanShamsi (previous revision, new revision, compare).

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    4 months ago, # ^ |
    ← Rev. 4   Vote: I like it +1 Vote: I do not like it

    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
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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