### Petr's blog

By Petr, history, 2 months ago,
• +186

 » 2 months ago, # |   +3 Auto comment: topic has been updated by Petr (previous revision, new revision, compare).
 » 2 months ago, # |   -22 OMG!Endless editorial!
 » 2 months ago, # |   0 Thank you!
 » 2 months ago, # |   0 Is there a dp solution for problem B
•  » » 2 months ago, # ^ |   0 I am also interested.
 » 2 months ago, # |   0 Helpful. +1
 » 2 months ago, # | ← Rev. 2 →   0 Did someone tried to solve B using binary search and maximum bipartite matching? I tried but got TLE (253131171).
•  » » 2 months ago, # ^ |   +23 I did :) I would not say I am proud of that but I thought about doing a binary search + checking Hall's theorem statement on the graph. It can be shown that it is enough to check Hall's condition only for subsegments of appetizers in the sorted order. However, $O(n^2 \log C)$ would probably be too slow, so I just initially set the answer to infinity and then looking at all subsegments decrease this value as long as Hall's condition does not hold. This leads to an $O(n^2)$ solution. Huge overkill though...
•  » » » 2 months ago, # ^ |   +39 My approach was also using Hall's theorem; I thought about how to optimize $O(n^2$ $log$ $C)$ to $O(n^2)$ for a bit before realizing it's easier to optimize it to $O(n$ $log$ $C)$.For each element, let's say $x_i$ elements of $b$ are $\geq a_i+ans$ and $y_i$ elements of $b$ are $\leq a_i-ans$. Then, you want for all $i \leq j$, $x_i+y_j \geq j-i+1$, or $x_i+i \geq j+1-y_j$, which you can check by finding looking at the prefix minimum of $x_i+i$ and making sure that it's $\geq j+1-y_j$.
•  » » » 2 months ago, # ^ |   0 Thank you for replying. It would be really helpful if you can share your code.
•  » » » 2 months ago, # ^ |   0 I checked for hall in $O(n²\log{C})$ and it passed :). Maybe methods with a higher constant TLE. For all elements in $a$ you calculate $(l_i,r_i)$ such that $a_i$ can match with everyone from $b_1$ to $b_{l_i}$ and from $b_{r_i}$ to $b_n$. Now for each $(l,r)$ you want to calculate how many $(l_i,r_i)$ there are such that $l_i \leq l \leq r \leq r_i$, which is quite easy to do with a 2d prefix sum. I did have to do that prefix sum with a global array instead of a vector of vectors to get AC though.
 » 2 months ago, # | ← Rev. 2 →   -7 Poblem B, please, help me to figure out what's wrong with the code below:  ull solve(){ std::sort(A.begin(),A.end()); std::sort(B.begin(),B.end()); ull ans=-1; for (ull k=0;k<=n;++k){ ull mi=1e15; // Pair k smallest ai's elements, with k largest bi's elements for(ull i=0;i
 » 2 months ago, # |   -8 Is there any solution for problem F that use the alternate method they propose here? $O(K\sqrt(K)$ wouldn't enter with the k=10^6 right?
•  » » 2 months ago, # ^ |   0 you can use bitsets to make it $O(\frac{k\sqrt{k}}{w})$
 » 2 months ago, # | ← Rev. 2 →   0 Can someone explain the third paragraph of the proof in problem K("Now, note that if we swap free elements in A and C...")?I know the proof's idea is to swap the smallest $n_{b}$ numbers from A and C to B.I also agree with the solution about the truth that free elements in B and C can be swapped without break the conditions.But why the third paragraph swap free elements in A and C?I can't understand the necessity.I'm also doubt with the sentence at the end:"for the same reason.".Thank you.
 » 2 months ago, # |   0 Auto comment: topic has been updated by dario2994 (previous revision, new revision, compare).
 » 2 months ago, # |   -20 i am studying this solutioncan anyone explain this how we are calculating value of H in this solution like in this loop..for(int i=x;i<=N;i+=x) xx+=cnt[i];Your text to link here... Here is the complete code #pragma GCC optimize("Ofast,unroll-loops") #include using namespace std; long long H,h[200003],gg; int n,k; vectorV; mapmp; bool cmp(long long A,long long B,long long C,long long D){ return __int128(A)*D<__int128(B)*C; } long long A=3e18,B=1,X,Y; int N=4e7; //long long s[200003]; int cnt[40000003]; void add(int x,int y){ if(cmp(A,B,H,1ll*x*y)) return; long long xx=n-V.size(),yy=y; for(int i=x;i<=N;i+=x) xx+=cnt[i]; for(auto i:V) xx+=(i+x-1)/x; if(cmp(xx,yy,A,B)) A=xx,B=yy,X=x,Y=y; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k; for(int i=0;i>h[i]; H+=h[i]; if(h[i]>4e7) mp[h[i]]++, V.push_back(h[i]); else cnt[h[i]-1]++; } // for(auto i:mp)gg+=min(k,int(sqrt(i.first))); for(int i=N;i>0;i--) cnt[i]+=cnt[i+1]; for(int i=k/2;i>0;i--){ add(i,k-i); add(k-i,i); } cout<
 » 11 days ago, # |   0 Can someone please explain the solution of problem B .