Petr's blog

European Championship 2024 (EUC) Editorial
By Petr, history, 2 years 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

Comments Comments (13)
| Write comment?
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Thank you!

→ Reply
»
2 years ago, hide # |
← 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
  • »
    »
    2 years ago, hide # ^ |
     
    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
    • »
      »
      »
      2 years ago, hide # ^ |
       
      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
    • »
      »
      »
      2 years ago, hide # ^ |
       
      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
    • »
      »
      »
      2 years ago, hide # ^ |
       
      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
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
← 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
»
2 years ago, hide # |
 
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
»
21 month(s) ago, hide # |
 
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;

}
→ Reply
»
21 month(s) ago, hide # |
 
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 :(

→ Reply