GOTHAM - Editorial

PROBLEM LINK:

Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest

Setter: Aditya Kumar Singh
Tester: Daanish Mahajan

DIFFICULTY:

Easy

PREREQUISITES:

Multiset, Greedy

PROBLEM:

N district having some capacity of people given in the array. For each Q query, you are given two numbers X and P. P peoples are dropped at district X. Each dropped person moves forward to get shelter in the district. If someone unable to find a location will die. You have to find the total distance traveled by people who will get shelter.

EXPLANATION:

We can use a multiset of pairs to store all the districts with their capacity.
For each query: we can fill the nearest right district until they are not full and remove them once it got full and If some people are left to be accommodating and there is no vacant space on right they are going to die.

Even there are up to (10^9) people at each query the complexity will be under (NlogN+QlogN) always as the nearest right district will be either completely used and removed or remain and queries will continue.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define is insert
#define rep1(i,a,b) for(long long i=a;i<=b;i++)
#define F first
#define S second
#define file ifstream fin("input.txt");ofstream fout("output.txt");
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fr(n) for(long long i=0;i<n;i++)
#define rep(i,a,b) for(long long i=a;i<b;i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;

void solve()
{
    ll n,a,q,k,x;
    cin>>n;
    set<pair<ll,ll> >se;

    rep(i,1,n+1)
    {
        cin>>a;
        se.is({i,a});
    }

    cin>>q;
    fr(q)
    {
        ll dis=0,ini;
        cin>>x>>k;
        auto it=se.lower_bound({x,0});
        while(it!=se.end() && k>0)
        {
            if(it->S>k)
            {
                dis+=(k*(it->F - x));
                se.is({it->F,it->S - k});
                se.erase(it);
                k=0;
            }
            else
            {
                dis+=(it->S*(it->F-x));
                k-=it->S;
                auto itr=it;
                it++;
                se.erase(itr);
            }
        }
        cout<<dis<<endl;
    }
}
int32_t main()
{
    #ifndef ONLINE_JUDGE
    freopen("inputf.in", "r", stdin);
    freopen("outputf.in", "w", stdout);
    #endif
    fast;
    ll t=1;
    // cin>>t; 
    while(t--)
    solve();
    return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
# define ll long long int  
# define pb push_back
# define pll pair<ll, ll>
# define pli pair<ll, int>
# define mp make_pair
 
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();
        // char g = getc(fp);
        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;
            }
            // cout << x << " " << l << " " << r << endl;
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        // char g=getc(fp);
        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,' ');
}
 
const int maxn = 1e5, maxq = 1e5, maxv = 1e9;
 
int main()
{   
    int n = readIntLn(1, maxn);
    int cap[n + 1];
    set<int> s;
    for(int i = 1; i <= n; i++){
        cap[i] = (i == n ? readIntLn(1, maxv) : readIntSp(1, maxv));
        s.insert(i);
    }
    int q = readIntLn(1, maxq);
    while(q--){
        int x = readIntSp(1, n), k = readIntLn(1, maxv);
        auto it = s.lower_bound(x);
        ll ans = 0;
        while(it != s.end() && k > 0){
            int id = *it;
            int rem = min(cap[id], k);
            k -= rem; cap[id] -= rem;
            ans += (ll)(id - x) * rem;
            if(cap[id] == 0)s.erase(it);
            it = s.lower_bound(x);
        }
        cout << ans << endl;
    }   
    assert(getchar()==-1);
} 
3 Likes

It could also be solved in O(N+Q) where there is an okish constant factor with Q , I used path compression technique
Link to my Code
It’s O(N+Q) because in average we are not going more than twice on one node.

4 Likes

Thanks …

1 Like

Can someone help me out with what is wrong with this approach:-
‘’’
int n; cin >> n;
vector v(n);
fr(i, n)cin >> v[i];
set st;
for (int i = 0; i < n; i++)st.insert(i);
int q; cin >> q;
while (q–) {
int x, k; cin >> x >> k; x–;
auto it = st.lower_bound(x);
if (it == st.end()) {
cout << 0 << endl;
continue;
}
ll res = 0;
vector toerase;
for (auto i = it; i != st.end(); i++) {
int ind = *i;
int val = v[ind];
if (val > k) {
res += (ind - x) * k;
v[ind] -= k;
k = 0;
break;
}
if (val == k) {
res += (ind - x) * k;
v[ind] -= k;
toerase.pb(ind);
k = 0;
break;
}
else {
res += (ind - x) * v[ind];
k -= v[ind];
toerase.pb(ind);
}
}
for (int i = 0; i < toerase.size(); i++) {
st.erase(toerase[i]);
}
cout << res << endl;
}
‘’’
solution link
got it just made stupid mistake of using int instead of Long long :frowning:
AC

3 Likes

My code is using same algorithm but giving TLE why ??? Solution

Very Nice problem, but certainly the difficulty shouldn’t be Cake-Walk.

18 Likes

I would love to watch any video editorial of this problem :slight_smile: !

5 Likes

anyone explain algorithim of this question ??? .please explain easy steps

1 Like

@deepu_coder binary_search on each query

i am not able to understand when u are erasing elm when that ai=0 then in next query how u are getting deleted elment count also for distance .
arr={1,2,3,4,5}
x,k=4,4
x,k=3,5<----- then for it how u are counting 4 in b/w 3 and 5 as 4 is erased in previous query ??

Used fast output

True. I solved this problem very quickly, but I could see it occur as an easier C in CodeForces Div2. It’s definitely more of an ‘Easy’ problem, due to its heavy implementation and requirement of set and binary search, although it may not have the hardest idea.

1 Like

can u explain the time complexity of the solution

Yes i have the same doubt!

To add all N elements to the set (or multiset), you’ll take (N log N) operations. To find the next element on the right it takes at most (log N) operations (binary search) per query and in case we exhaust all the places at given district removal is done in (log N) as well.

So in total it adds up to (N log N + Q log N) operations. There’s a mistake in the editorial as it states (N + Q log N) which is obviously incorrect, but it doesn’t change the whole thing miuch for the given constraints.

5 Likes

just simply subtracting the x from the current iterator gives u the distance between iterator and the district where citizens are dropped i.e - for x,k = 3,5 =>
it = 3;
as it->S = 3 which is not greater than k
d += (it->f-x)(it->s) = (3-3)(3) = 0;
k -= it->s => k = 2
as 4 is deleted so it = 5
for it = 5 , it->s > k
d += (5-3)*(2) = 4
here

thank you very much…

1 Like

I found a solution with union-find data structure but I still getting WA! I made a tester and tested it with quiet a few testcases with the original constraints.Can someone figure out where I am getting wrong?Here is the link to my codeGOTHAM_Sol.cpp

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
ll n;
cin>>n;
map<ll,ll>ad;
for(ll i=1;i<=n;i++)
{
ll c;
cin>>c;
ad.insert(pair<ll,ll>(i,c));
}
ll q;
cin>>q;
while(q–)
{
ll t,d;
cin>>t>>d;
map<ll,ll>::iterator itr;
itr=ad.lower_bound(t);
// cout<<“LOwerBOund-”<second<<endl;
ll ans=0;
if(itr==ad.end())
{
cout<<0<<endl;
}
else
{

		for(;itr!=ad.end();itr++)
		{
			cout<<d<<"-"<<itr->second<<endl;
			if(d==0)
			{
				break;
			}
        	else if(itr->second>d&&d>0)
			{
				ans+=(itr->first-t)*d;
				d=itr->second - d;
			//	cout<<d<<" ";
			//	map<ll,ll>::iterator it=itr;
			//	itr++;
			    ll t1=itr->first;
			    ll t2=itr->second-d;
				ad.erase(itr->first);
				ad.insert({t1,t2});
			}
			else 
			{
				ans+= (itr->first-t)*itr->second;
				d=d-itr->second;
				ad.erase(itr->first);
			//	cout<<d<<" ";
				
			}
		
		
	}
	cout<<ans<<endl;
	
	}
	
return 0;
}

}
hello can someone please point out the error in my code. i have dry run the program few times. i am unable to find the error… I am complete beginner…

give a link or use ``` to format your code