- A: Author: Giove, Prepared by: Giove
- B: Author: antontrygubO_o, Prepared by: antontrygubO_o.
- C: Author: Petr, Prepared by: MZuenni
- D: Author: Petr, Prepared by: Petr
- E: Author: MZuenni and dario2994, Prepared by: MZuenni
- F: Author: dario2994, Prepared by: bicsi
- G: Author: Giove, Prepared by: bicsi
- H: Author: Petr, Prepared by: Petr
- I: Author: Giove, Prepared by: Giove
- J: Author: bicsi, Prepared by: Martin Kacer.
- K: Author: antontrygubO_o, Prepared by: antontrygubO_o.
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...
Auto comment: topic has been updated by Petr (previous revision, new revision, compare).
OMG!Endless editorial!
Thank you!
Is there a dp solution for problem B
I am also interested.
Helpful. +1
Did someone tried to solve B using binary search and maximum bipartite matching? I tried but got TLE (253131171).
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...
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$$$.
Thank you for replying. It would be really helpful if you can share your code.
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.
Poblem B, please, help me to figure out what's wrong with the code below:
Thanks
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?
you can use bitsets to make it $$$O(\frac{k\sqrt{k}}{w})$$$
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.
Auto comment: topic has been updated by dario2994 (previous revision, new revision, compare).
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...
Can someone please explain the solution of problem B .
can anybody tell why this solution of Problem I(eye) is getting wrong answer on test 27 while this 269511518 getting accepted!!
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..
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 :(