MANGOMKT - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Flame Storm
Tester: Harris Leung
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Graphs & Observation

PROBLEM:

You have a simple graph (unweighted, undirected graph containing no self-loops or multiple edges) G with N vertices and M edges. There is an edge between two sellers if and only if they are neighbors. When you buy a mango from a seller numbered XX, the following occurs:

  • Seller X keeps his price the same.
  • Every seller Y who is a neighbor of X increases their price by 1, that is, A_Y=A_Y+1 for every Y who is a neighbor of X.
  • Every other seller Z who is not a neighbor of X decreases their price by 1; that is, A_Z=A_Z−1 for every Z who is not a neighbor of X.

You need to process Q queries and find the minimum amount of money you need to pay so that you can buy exactly one mango from every seller when the query is ?.

Other queries involve the addition and deletion of the edges from the given graph.

QUICK EXPLANATION:

Let’s say S is the sum of the initial prices given to us and E is the number of edges in the graph at the output query time. Then the answer for each query will be:

S+(E-X)

where X is the missing edges in the graph at the query time.

EXPLANATION:

You might be wondering which seller to go to first and then who will be next. You may be trying to find a sequence in which order you need to visit the seller. Because if this is not where you are stuck, then you are on the right track.

So why does the order of visiting the seller doesn’t matter?

Let’s consider two nodes of the graph say u and v. Now think of the two scenarios possible:

1) u and v have an edge between them.

  • In this case, what happens when we visit the seller u first the seller v is going to increase his/her price by 1. Or, if you visit seller v first, then the seller u is going to increase his/her price by 1.

  • Hence for every edge the overall price increases by 1 for you.

2) u and v don’t have an edge between them.

  • In this case, what happens when we visit the seller u first the seller v is going to decrease his/her price by 1. Or, if you visit seller v first, then the seller u is going to decrease his/her price by 1.

  • Hence for every edge the overall price decreases by 1 for you.

Hence we can make two observations from the above scenarios:

  • It doesn’t matter which node you visit first or which node you visit last.
  • For every edge, the price increases by 1 while for every missing edge the price decreases by 1.

Therefore we just need to track the number of edges in the graph when we process the output query. If we know the number of edges in the graph then we can easily calculate the missing edges and so our answer.

TIME COMPLEXITY:

O(N+M+Q)

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
	cin >> n >> m;
	long long sum = 0;
	for (int i = 1; i <= n; i++) {
	    long long x;
	    cin >> x;
	    sum += x;
	}
	long long edges = (long long)m, unused = ((long long)n * (n - 1)) / 2LL - edges;
	for (int i = 0; i < m; i++) {
	    int u, v;
	    cin >> u >> v;
	}
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
	    char x;
	    cin >> x;
	    if (x == '+') {
	        edges++;
	        unused--;
	        int u, v;
	        cin >> u >> v;
	    }
	    else if (x == '-') {
	        edges--;
	        unused++;
	        int u, v;
	        cin >> u >> v;
	    }
	    else if (x == '?') {
	        cout << sum + edges - unused << '\n';
	    }
	}
	return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
int n,m;
ll a[300001];
ll s=0;
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 {
            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,' ');
}

void readEOF(){
    assert(getchar()==EOF);
}
map<pair<int,int>,int>mp;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    n=readIntSp(1,100000);
    m=readIntLn(1,min(1LL*n*(n-1)/2,100000LL));
    for(int i=1; i<=n ;i++){
    	if(i!=n) a[i]=readIntSp(1,1000000000);
    	else a[i]=readIntLn(1,1000000000);
    	s+=a[i];
	}
	for(int i=1; i<=m ;i++){
		int u,v;
		u=readIntSp(1,n);
		v=readIntLn(1,n);
		if(u>v) swap(u,v);
		assert((mp[{u,v}]==0));
		mp[{u,v}]=1;
	}
	ll cm=m;
	int q;q=readIntLn(1,100000);
	for(int i=1; i<=q ;i++){
		char t;int u,v;
		t=getchar();
		if(t=='?'){
			char c=getchar();assert(c=='\n');
			cout << s+2*cm-1LL*n*(n-1)/2 << '\n';
			//cm=m;
		}
		else if(t=='+'){
			char c=getchar();assert(c==' ');
			u=readIntSp(1,n);
			v=readIntLn(1,n);
			if(u>v) swap(u,v);
			cm++;
			assert((mp[{u,v}]==0));
			mp[{u,v}]=1;
		}
		else if(t=='-'){
			char c=getchar();assert(c==' ');
			u=readIntSp(1,n);
			v=readIntLn(1,n);
			if(u>v) swap(u,v);
			cm--;
			assert((mp[{u,v}]==1));
			mp[{u,v}]=0;
			
		}
		else assert(false);
	}
	readEOF();
}
Editorialist Solution
#include<bits/stdc++.h>
using namespace std;

#define int long long

int32_t main()
{
  int n,edges;
  cin>>n>>edges;

  int total = n*(n-1);
  total/=2;

  int missing_edges = total-edges;

  int sum = 0;
  for(int i=0;i<n;i++)
  {
    int x;
    cin>>x;
    sum+=x;
  }

  for(int i=0;i<edges;i++)
  {
    int waste;
    cin>>waste>>waste;
  }

  int q;
  cin>>q;

  while(q--)
  {
    char ch;
    cin>>ch;

    if(ch == '+')
    {
      int waste;
      cin>>waste>>waste;
      edges++;
      missing_edges--;
    }
    else if(ch == '-')
    {
      int waste;
      cin>>waste>>waste;
      edges--;
      missing_edges++;
    }
    else
      cout<<sum+edges-missing_edges<<"\n";
  }
return 0;
}

6 Likes

Nice problem. Initially I thought that after each “?” query the whole graph is restored to it’s initial state. I’m glad that I read the problem statement again and was able to get AC!!
I hope I’ll become 5 star after this contest!! So excited!

4 Likes

Thanks. But that doesn’t seem to hold if the graph is not fully connected. For example, for 4 nodes and 1 edge, the formula does not hold. And, in this case, the order of the purchases changes to result. The constraints don’t prevent that. Cheers.

Can anyone please explain that after the '?' query, how the graph reset condition is kept intact ?

1 Like

One of the best explanations available on CodeChef

1 Like

Congo bro!!!

I am not able to understand solution properly.

What i was trying to do :

sum(initial sum of all prices)
a (array to store count of neighbours for each node)
n(number of nodes)

so for query == ?
for i=1 to n
sum=sum+a[i]-(n-a[i]-1) //(adding contribution of each node)
print sum

for queries== +
cin>>u>>v
a[u]++,a[v]++ (increasing count of neighbours for node u,v)

for queries== -
a[u]–,a[v]-- (decreasing count of neighbours for node u,v)

so basically i was taking contribution of each node separately in final answer
And according to me in solution i think contribution of each edge is there.

can anyone explain it.
Thank you.

You are very close.

should be

sum = sum + a[i] - (i - a[i] - 1)

With above change we will get correct answer which is too slow to pass. Because we are doing a loop of 1 \to n for each query, we will end up doing \mathcal{O} (N * Q). We can calculate this faster after observing that ans = \sum A[i] + (0 + 1 + \dots n - 1) + 2 * edges\_count . Therefore we only need to maintain the number of edges (it is the only thing which depends on adding and removing edges).

You need to be more specific about what part of editorial you did not understand in order for someone from community to help you out.

Suppose the graph before ‘?’ query was G with price array A. Then you choose the order of vertices (which has to minimize the total cost), while doing so the price array changes to A'. Print the answer and restore price array to A and graph remains unchanged i.e. G.

In other queries, just the graph changes.

1 Like