Invitation to Alohomora 2021

announcement
, , ,
62

I guess 2D segment tree will be two large in memory and time.
Btw How to solve for large coordinates. -1e9 <= X , Y <= 1e9.

63

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

1 Like
64

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

65

Thanks , Got it.

1 Like
66

When will the problems be added to the practice section so that we can submit again :frowning:

3 Likes
67

Use coordinate compression, since we are concerned with relative values only.

68

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
69

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

70

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
71

Okk , Thanks @sudipandatta and @samarth2017

72

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.

73

what is a unit graph?

74

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.

75
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
76

Network where all edges are of unit capacity.

77

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

78

@regex0754 when will the editorials be published

79

can u please provide some hints for the 4th problem , since editorial is not coming

80

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

image
image1365×737 67.9 KB

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[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() ;
}
2 Likes
81

bro thats really a wonderful explaination ! Thanks for ur time :grinning: . I am glad I was in the right track I was thinking of 2 d prefix sums too :smiley:

1 Like