AGCY - Editorial

PROBLEM LINK:

Practice

Author: Vaishakh SM
Tester: Smit Mandavia
Editorialist: Vaishakh SM

DIFFICULTY:

Easy

PREREQUISITES:

Knowledge of prefix sums

PROBLEM:

Given an array, A of size N initially filled with 0's, for each query containing two integers L,R add 1 to A[L] , 2 to A[L+1]R-L+1 to A[R]. In general, add i+1 to A[L+i] for every L\leq i \leq R.

QUICK EXPLANATION:

  • In an array initially filled with 0's, use standard prefix sums to first add 1 to each L,R query, let this array be B.
  • Subtract R-L+1 from A[R+1] for each query (store the queries beforehand)
  • Take prefix sum of B and print B[1] to B[N]

EXPLANATION:

Let us first try to solve a simpler question, how can we add 1 to each L,R query, we will later see how the original question is essentially the same as this simpler question.

For adding 1 to each L,R query, we first start with an array filled with 0's (say A), then we add 1 to each A[L] and subtract 1 from each A[R]. Then we take the prefix sum of A.

Now, observe that if we take the prefix sum of 1,1,1,-3, we get 1,2,3,0. Hence we have added 1,2,3 to A[0], A[1],A[2] respectively. Using this logic we can see that in general if we have M, 1's in an array followed by -M and if we take the prefix sum of the array we have added 1,2,... M to the first M indices of the array.

Hence, we will first add 1 in an initially empty array for each L,R query, then we will subtract R-L+1 from A[R+1] for each query and take prefix sum again to get the desired result.

TIME COMPLEXITY

Time complexity is O(N + Q), where N is size of array and Q is number of queries for each testcase.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;

int main()
{
	lli t,n,q,l,r;
	
	cin>>t;
	
	while(t--)
	{
		cin>>n>>q;
		
		vector<lli> arr(n+3);
		
		vector<pair<lli,lli>> Indices;
		
		while(q--)
		{
			cin>>l>>r;
			
			arr[l]++;	
			arr[r+1]--;
			// Adding 1 to arr[l] and subtracting 1
			// from arr[r+1] as mentioned in editorial
			
			Indices.push_back({l,r+1});
		}
		
		for(int i =1;i<=n;i++)
		{
			arr[i]+=(arr[i-1]);
		}
		// Taking prefix sum to add 1 to each L,R query
		
		for(auto x:Indices) arr[x.second]-=(x.second-x.first);
		// After generating the array where the queries are increased with 1
		// I am subtracting R-L+! to r+1th index
			
		for(int i =1;i<=n;i++)
		{
			arr[i]+=(arr[i-1]);
		}
		// Taking prefix sum again
		
		for(int i=1;i<=n;i++)cout<<arr[i]<<" ";
		//Final output
		
		cout<<endl;
	}
}
Tester's Solution
    #include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
           
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
            assert(l<=x && x<=r);
            return x;
        } else {
            cerr << (int)g << "\n";
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
int main() 
{
    FIO;
    int t,n,q,k,i,j,sum_n,sum_q;
    
    t=readIntLn(1,1000);
    sum_n=0;
    sum_q=0;
    while(t--){
        n=readIntSp(1,100000);
        q=readIntLn(1,100000);
        sum_n+=n;
        sum_q+=q;
        ll arr[n+3]={0};
        while(q--){
            j=readIntSp(1,n);
            k=readIntLn(j,n);    
            arr[j]++;
            arr[k+1]--;
            arr[k+1]-=(k-j+1);
            arr[k+2]+=(k-j+1);
        }
        for(i=1;i<=n;i++)
            arr[i]+=arr[i-1];
        for(i=1;i<=n;i++)
            arr[i]+=arr[i-1];
        
        for(i=1;i<=n;i++)
            cout << arr[i] << " ";
        cout << "\n";
    }
    assert(getchar()==-1);
	assert(sum_n<=1000000);
	assert(sum_q<=1000000);
	return 0;
}
11 Likes

Can someone mention some problems like this one? I like the technique wanna solve more

1 Like

Wow, the solution seems so simple but at the same time feels hard to come up with it .

1 Like

I think these set of problems will be helpful for you.

1 Like

Can anybody tell me on which testcase my solution is giving WA?

#include<bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define fr(i,k) for(i=0;i<k;i++)
#define deb(x) cerr<<#x<<" = “<<x<<endl;
#define deb2(x,y) cerr<<#x<<” ="<<x<<endl<<#y<<" ="<<y<<endl;
#define SZ(x) (x).size();
#define ll long long
#define mod 1000000007
#define ff first
#define ss second
#define pb push_back
#define em emplace_back
#define ulli unsigned long long int
#define inf 1e18
#define endl “\n”
typedef vector<vector> vvll;
typedef vector vll;
typedef vector<pair<ll,ll>> vpll;
typedef pair<ll,ll> pll;
typedef vector vb;
void solve();

int main() {
fastio;
/#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
/

ll t;
t = 1;

cin >> t;
while (t--)
{
	solve();
}
return 0;

}

inline void solve()
{
ll n,q,i,l,h,m;
cin>>n>>q;

vector<pair<ll,ll>> v(q);
vector<ll> ans(n+1,0);
vector<ll> pre(q+1,0);

for(i=0;i<q;i++)
{
    cin>>v[i].first>>v[i].second;
}

sort(v.begin(),v.end());

pre[1] = v[0].first;
for(i=2;i<=q;i++)
    pre[i]+=(pre[i-1]+v[i-1].first);

for(i=1;i<=n;i++)
{
    l=0;
    h=q-1;
    ll idx1=-1,idx2=-1;

    while(l<=h)
    {
        m = l+(h-l)/2;

        if(v[m].first>i)
        {
            h=m-1;
        }
        else
        {
            if(v[m].second>=i)
            {
                idx2=m;
                l=m+1;
            }
            else
                l=m+1;
        }
    }

    l=0;
    h=q-1;

    while(l<=h)
    {
        m = l+(h-l)/2;

        if(v[m].first>i)
        {
            h=m-1;
        }
        else
        {
            if(v[m].second>=i)
            {
                h=m-1;
                idx1=m;
            }
            else
                l=m+1;
        }
    }

    if(idx1!=-1 && idx2!=-1)
    {
        ll b;
        b = idx2-idx1+1;

        ans[i] = (i+1)*b - (pre[idx2+1]-pre[idx1]);
    }

}

for(i=1;i<=n;i++)
    cout<<ans[i]<<" ";

cout<<endl;

}

Another Approach to solve just stimulate the process

https://www.codechef.com/viewsolution/40958260

How codechef can tag problems like this as easy

2 Likes

how this solution getting TLE(Solution: 41306165 | CodeChef) and this solution getting acc ans(Solution: 41306753 | CodeChef) … there are both same except in line 198…please can anyone tell me whats wrong here.