Little Girl and Maximum Sum, Editorial | Codeforces

This is an editorial post of the codeforces problem Little Girl and Maximum Sum.

Guide To CP
Get Free Guide To Competitive Programming along with Programming Techniques
Loading

Detailed Editorial

If you observe the problem statement carefully, it is a range sum query problem that can be easily done by the prefix sum algorithm.

A range sum query has been discussed in this post. Please look into it before moving ahead.

The twist to this problem is that we have to reorder the array elements before replying to the queries in such a way that makes the sum of query replies maximum possible.


The idea behind the logic is that we have to pre-compute the queries before to find which common query/position has occurred the most.

Let understand it by an example,

3 3
5 3 2
1 2
2 3
1 3

If we look into the queries, which array position has occurred the most.

little girl and maximum sum

2nd index has occurred the most in the above queries. So, we will place maximum element of the array to that position.

In the same way, we will put the second maximum element of the array to the position which occurred second most time in the queries, and this way we will reorder the array element.

So, for the above array ordering would be {2, 5, 3} and now if we solve for the queries the total sum would be 25 which is the maximum.

Hope you got the intuition behind the ordering of the element and rest we have to just perform range sum queries to find the maximum sum.

Hope the editorial is clear to you, if you have any doubts ask it in the comment section.

Detailed Solution in C++

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
int32_t main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    
    ll t = 1;
    
    while(t--)
    {
        ll n, q;
        cin >> n >> q;
        
        vector<ll> input(n), seg(n);
        
        for(int i = 0; i < n; i++) cin >> input[i];
        for(int i = 0; i < n; i++) seg[i] = 0;
        
        /* Code to reorder the original array */

        vector<pair<ll, ll>> queries(q);
        for(int i = 0; i < q; i++)
        {
            int x, y;
            cin >> x >> y;
            
            x = x-1;
            y = y-1;
            
            queries[i] = {x, y};
            
            seg[x] += 1;
            if(y != n-1) seg[y+1] += -1;
        }

        for(int i = 1; i < n; i++)
        {
            seg[i] += seg[i-1];
        }
        
        sort(input.begin(), input.end());
        
        vector<pair<ll,ll>> v(n);
        for(int i = 0; i < n; i++)
        {
            v[i] = {seg[i], i};
        }
        
        sort(v.begin(), v.end());
        
        vector<ll> vec(n);
        for(int i = 0; i < n; i++)
        {
            ll x = v[i].second;
            vec[x] = input[i];
        }
        
        /* Code to find range sum queries in O(n) Time Complexity */
        
        ll s = 0;
        for(int i = 1; i < n; i++)
        {
            vec[i] += vec[i-1];
        }
        for(int i = 0; i < q; i++)
        {
            ll x = queries[i].first;
            ll y = queries[i].second;
            
            if(x > 0)
            {
                s = s + vec[y] - vec[x-1];
            }
            else
            {
                s = s + vec[y];
            }
        }
        
        cout<<s<<"\n";
    }
    return 0;
}

Hope you love this explanation of Little Girl and Maximum Sum. Have A look on our Mashmokh and ACM editorial

Leave a Comment

Your email address will not be published. Required fields are marked *