 # Invitation to Alohomora 2021

I guess fenwick tree approach will work even then but we’ll deal the queries offline with coordinate compressionn

1 Like

For Jiggly Puff problem, how to find the perfect bipartite matching fast?

Thanks , Got it.

1 Like

When will the problems be added to the practice section so that we can submit again 3 Likes

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

1 Like

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.

2 Likes

Okk , Thanks @sudipandatta and @samarth2017

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.

A=2^N-2(N+1)-N(N-1)

Basically for any general K answer would be

A=2^N-2\times\sum_{i=0}^K {N \choose i}
1 Like

Network where all edges are of unit capacity.

Got it thanks can u please help me by sharing how to start dynamic programming

@regex0754 when will the editorials be published

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.

Reference

Say S(A) → sum of all points in region A. Now the problem asks use to find S(B)-S(A).

S(B)-S(A)=S(B)+S(C)-(S(C)+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 ;
void solve(){
int n;
cin >> n ;
while(n--){
int x,y,v ;
cin >> x >> y >> v  ;
x+=mxX,y+=mxX ;
f.upd(x,v) ;
f.upd(y,v) ;
int ans=f.qry(2*mxX)-f.qry(x-1)-f.qry(y-1) ;
cout << ans << '\n' ;
}
f.clear()  ;
f.clear()  ;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int TC  ;
cin >>TC ;
while(TC--)
solve() ;
}


1 Like

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 1 Like