Petr's blog

By Petr, history, 8 months 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

»
8 months 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).

»
8 months ago, # |
  Vote: I like it -22 Vote: I do not like it

OMG!Endless editorial!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a dp solution for problem B

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Helpful. +1

»
8 months 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).

  • »
    »
    8 months 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...

    • »
      »
      »
      8 months 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$$$.

    • »
      »
      »
      8 months 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.

    • »
      »
      »
      8 months 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.

»
8 months 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

»
8 months 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?

»
8 months 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.

»
7 months 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).

»
7 months 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;
}
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the solution of problem B .

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody tell why this solution of Problem I(eye) is getting wrong answer on test 27 while this 269511518 getting accepted!!

bool dfs(vvl &adj , ll u , ll par , vl &vis , vl&sym, ll &curr)
{
	if (par == 0)
	{
		sym[u] = 1; // pos;
		curr++;
	}
	else
	{
		sym[u] = (sym[par] == 0);
		if (sym[u])curr += 1;
		else curr -= 1;
	}
	vis[u] = 1;
	for (auto v : adj[u])
	{
		if (!vis[v] && par != v)
		{
			if (!dfs(adj , v , u , vis , sym , curr))
			{
				return 0;
			}
		}

		if (sym[u] == sym[v])
		{
			return 0;
		}

	}

	return 1;
}

void solve()
{
	ll n;
	cin >> n;

	vvl adj(n + 1);
	vll po(n);
	vl r(n);

	forf(n, i)
	{
		cin >> po[i].ff >> po[i].ss >> r[i];
	}

	forf(n, i)
	{
		ll cr = r[i];
		ll x = po[i].ff , y = po[i].ss;
		for (int j = i + 1 ; j < n ; j++)
		{
			if ( (po[j].ff - x) * (po[j].ff - x) + (po[j].ss - y) * (po[j].ss - y) == (cr + r[j]) * (cr + r[j])  )
			{
				adj[i + 1].pb(j + 1);
				adj[j + 1].pb(i + 1);
			}
		}

	}

	debug(adj);

	ll curr = 0;
	vl vis(n + 1, 0);
	vl sym(n + 1, 0);
	for1(n, i)
	{
		if (!vis[i])
		{
			curr = 0;
			if (dfs(adj , i , 0 , vis, sym , curr) && curr != 0)
			{
				debug(sym);
				yes;
				rtn;
			}
		}
	}
	debug(sym);

	no;

}
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what i believe is that for a connected component, you need to visit it completely and not prematurely return the answer, otherwise some of the nodes will remain unvisited and you may start a dfs for the same component again later with half of the component already visited giving wrong results..

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello i know its a bit late but can someone help me with C. I am trying with multisource BFS. first we take the leaves then move them and so on. But there is probably a greedy way of doing it.

Imagine u is a leaf node after some operations with val[u]>val[v]. Now ofc it is possible that after more operations, val[v] >= va[u] is possible. I am not able to figure this condition in the BFS.

I thought of 2 things. First if val[v] < val[u] and the neighbours of v is less than 1 then it wont be possible. Another thing i can think of is if the val[v] has immediate connection to leaves all having value greater than itself.

Not exactly sure how to do :(