I guess fenwick tree approach will work even then but we’ll deal the queries offline with coordinate compressionn
For Jiggly Puff problem, how to find the perfect bipartite matching fast?
Thanks , Got it.
When will the problems be added to the practice section so that we can submit again
Use coordinate compression, since we are concerned with relative values only.
For Jiggly Puff problem we had to find maximum bipartite partitioning right ? And is there a way other than fordFulkerson to do so ? @samarth2017 and @cubefreak777
This problem can be solved using flows. To solve flows Ford Fulkerson is one algorithm among a few others. Dinic is the most popular one though for CP. Dinic
I think you should use Dinic’s algorithm here because capacity \leq 1. Runtime would be O(N \times sqrt(N)). You might get TLE with Ford-Fulkerson.
For the problem healer I found that if both i and f are odd then only Bellossom can win and othercase Chansey will win is that observation correct.
what is a unit graph?
I guess Battle of legends can be done with somewhat a similar tree chaining algorithm like heavy-light-decomposition by always choosing the heavy children of a node as the one having the character with least value(i.e. choose child-node with ‘a’ if possible) though I’m having difficulty breaking ties . For a query you just have to follow the chain in which node is present.
Basically for any general K answer would be
Network where all edges are of unit capacity.
Got it thanks can u please help me by sharing how to start dynamic programming
can u please provide some hints for the 4th problem , since editorial is not coming
Firstly let’s add 5\times 10^5 to both X \&Y so as to eradicate the negative coordinates and bring the problem into the first quadrant. Now refer to the figure attached below.
Say S(A) → sum of all points in region A. Now the problem asks use to find S(B)-S(A).
SO we can evaluate S(B)+S(C) and S(C)+S(A) and then subtract both of them. S(C)+S(A) is just the sum of all points which have their y coordinate less than Y and
S(C)+S(B) = sum of all values of the 10^6 \times 10^6 grid - (S(D)+S(A), again S(D)+S(A) is the sum of all points which have their x coordinate less than X so we need prefix sums and point updates hence it can be easily solved with 2 Fenwick trees one for each axes.
CODE
#include "bits/stdc++.h"
#define int long long
using namespace std ;
const int mxX=5e5+1,mxN=1e6+2;
struct ft{
int a[mxN]={};
void clear(){
memset(a,0,sizeof(a)) ;
}
void upd(int i,int x){
for(;i<=mxN;i+=i&-i)
a[i]+=x ;
}
int qry(int i){
int r=0 ;
for(;i;i-=i&-i)
r+=a[i] ;
return r ;
}
}f[2] ;
void solve(){
int n;
cin >> n ;
while(n--){
int x,y,v ;
cin >> x >> y >> v ;
x+=mxX,y+=mxX ;
f[0].upd(x,v) ;
f[1].upd(y,v) ;
int ans=f[0].qry(2*mxX)-f[0].qry(x-1)-f[1].qry(y-1) ;
cout << ans << '\n' ;
}
f[0].clear() ;
f[1].clear() ;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int TC ;
cin >>TC ;
while(TC--)
solve() ;
}
bro thats really a wonderful explaination ! Thanks for ur time . I am glad I was in the right track I was thinking of 2 d prefix sums too