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