Petr's blog

European Championship 2024 (EUC) Editorial
By Petr, history, 5 weeks ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +186
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by Petr (previous revision, new revision, compare).

→ Reply
»
5 weeks ago, # |
  Vote: I like it -22 Vote: I do not like it

OMG!Endless editorial!

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you!

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a dp solution for problem B

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Helpful. +1

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Did someone tried to solve B using binary search and maximum bipartite matching? I tried but got TLE (253131171).

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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...

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +39 Vote: I do not like it

      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$$$.

      → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for replying. It would be really helpful if you can share your code.

      → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

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<k;++i) mi=std::min(mi,abs(A[i]*1ll-B[n-1-i])*1ll);
                
                // Pair k largest (n-k) ai's elements, with (n-k) smallest bi's elements
                for(ull i=k+1;i<n;++i) mi=std::min(mi,abs(A[i]*1ll-B[i-k])*1ll);

                ans=std::max(ans,mi);
            }
            return ans;
        }

Thanks

→ Reply
»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

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?

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dario2994 (previous revision, new revision, compare).

→ Reply
»
3 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

i am studying this solution

can 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<bits/stdc++.h>
using namespace std;
long long H,h[200003],gg;
int n,k;
vector<long long>V;
map<long long,int>mp;
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<n;i++){
		cin>>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<<X<<' '<<Y;
}
→ Reply