Hi everyone!
XX Open Cup Grand Prix of Warsaw will take place this Sunday, on September 15th 2019, at 11am Moscow time.
To enter the contest, click here (Open Cup login necessary).
The problems were created and set by Radewoosh and me. Also, thanks to the testers: Swistakk, Marcin_smu and Errichto!
The problemset was presented at this summer's Petrozavodsk camp. Thanks to everyone at AIM Tech for supporting the contest, including the tasks selection! If you want to know how to hold your own contest on Moscow Workshops in November and participate in the camp for free, look here.
If you're still unsure whether to participate and you like Pokémon, this is your lucky day! You'll be able to help quite a few of them on Sunday. Don't worry, you don't have to finish all the games and watch all the anime in order to solve the tasks! *but it's a good idea in general
Good luck!
Edit: Thanks for the participation! The editorial can be found here.
Edit 2: The contest is available at Gym. Thanks to MikeMirzayanov for helping us with uploading it!
Cutest statements ever, highly recommended.
Reminder, 15 mins to start!
How to solve B? I wrote a $$$O(nk^22^k)$$$ solution but passed in 3 seconds.
It was one of the expected solutions.
We can also solve it in $$$O(nk^3)$$$ by finding the augmenting paths in the graph in a clever way. The core idea is that you first find the flow from the left to the graph in which each augmenting path goes as far as possible, and then cut off the layers of the graph from the left and update the flow. More details in the editorial. It isn't much faster in practice, though.
Well, my solution is different to the $$$O(nk^22^k)$$$ one mentioned in the editorial. I just used a simple DP to find the minimum number of vertices that need to be cut.
That's interesting! Do you mind sharing more details about it?
Iterate $$$r$$$ from $$$2$$$ to $$$n$$$. Let's fix $$$l$$$ and $$$r$$$, and only consider the layers between $$$[l,r]$$$. Denote $$$f[S](0\leq S<2^k)$$$ as the minimum number of vertices that need to be cut such that the vertices set $$$S$$$ in the $$$r$$$-th layer is still connected with the source of the network.
For some fixed $$$r$$$ and $$$S$$$, we can note that the smaller $$$l$$$ may have a smaller value of $$$f[S]$$$, and there are at most $$$O(k)$$$ such values.
When we iterate $$$r$$$ from $$$i-1$$$ to $$$i$$$, we need to do a simple DP transition to determine which vertices in the $$$i$$$-th layer are cut. In order to store $$$f[S]$$$ for all $$$l$$$ efficiently, we can use an array $$$f[S][i]$$$, where $$$f[S][i]$$$ denotes the maximum value of $$$l$$$ such that $$$f[S]$$$ for $$$l$$$ is not larger than $$$i$$$. Thus we have a $$$O(nk^22^k)$$$ algorithm to calculate $$$f[][]$$$ for all $$$r$$$.
And what should we do to calculate the answer? You may note that we can answer a query "What is the answer of $$$[l,r]$$$?" in $$$O(k)$$$ time using $$$f[][]$$$. We only need to find the smallest $$$i$$$ such that $$$f[0][i]\geq l$$$.
We can also find that for fixed $$$r$$$, the smaller $$$l$$$ will have a smaller answer, and there will be at most $$$O(k)$$$ different intervals such that in each interval, the answers are the same for these $$$l$$$. It is not hard to figure out these intervals.
Looks very similar to our one, maybe just the thinking is different.
Auto comment: topic has been updated by mnbvmar (previous revision, new revision, compare).
When mnbvmar and Radewoosh asked me what will be the theme of their contest I, not thinking much and having absolutely no intent in guessing correctly, guessed Digimons. Imagine my surprise when they told me it is Pokemons even though I do not recall us ever talking about Pokemons/Digimons before.
How could you guess Digimons over Pokemons anyway!
It's just that Digimons are much closer to my heart than Pokemons. Had I been maximizing the probability, I would have definitely picked Pokemons, but as I said, I had no intention in guessing correctly, I meant it to be completely random guess for fun :P. Btw many people regards to Digimons as fake Pokemons, but not many people know that Digimons are actually older than Pokemons, so it can't be the case!
The theme of the contest is very nice and also the diagrams. How did you make/find the pictures for the girder stack in G, Alakazam with different spoon count for A?
I did everything (including spoons and stack) by myself. Just some time in image editors :P
And yes, I'm very proud because of the shadows in G (also by hand) XD
Have you thought about becoming a graphic designer?
Will this contest be in gym?
I hope so. mnbvmar, Radewoosh, I can assist with uploading if help needed.
Done! It's available here. Sorry for delay!
Where can I find the whole problem set (pdf)?
Can anybody explain how to solve div2 Q(Kalevich and Two New Paintings)?
Statement
I can share my solution
Let's denote bounding box as a rectangle with minimum possible area that covers all the points with edges parallel to axis. Now note that each side of a bounding box contains at least one point (otherwise we are able to shrink bounding box to a closest point in that direction). So each side of a bounding box touches at least one of our squares.
So we can only arrange our squares only in such way that each of 4 bounding box edges is touched. What are the different patterns of square intersections and how do the fill into our bounding box?
Other cases are just rotations and reflections of these four. Firstly, second case is completely useless. Secondly, we can see that in third case we can move blue square right just expanding covered area and turning it into a case one.
Now we only need to care about case 1 and case 4.
In case 1 we can always find a horizontal or vertical line that splits two squares. Let's make a scanline over this line: iterate over all meaningful positions of a splitting line and cover all points to the one side with first square and all points to the other side with second square. Square that covers a set of points can be calculated easily by finding min/max x/y. So we can do two scanlines here by sorting points by x coordinate and by y coordinate and revising all case 1 constructions.
In case 4 we can only fit this contruction into bounding box by attaching left-top corner of the red square to left-top corner of bounding box and bottom-right corner of the blue square to bottom-right corner of bounding box. Or a reflection of this case. Two points of our squares are fixed now, let's see how we can iterate over all possible combinations here. For a fixed size of one square we can easily determine set of points that are covered by one square, so we can uniquely determine set of points and size of a second square. So, let's iterate over all meaningful sizes of the red square with another scanline. Suppose, we want to keep increasing size of a red square and determine the order of points in which they will be included into this square. This is a "square distance" also known as Chebyshev distance between a top-left corner of bounding box and a point. So, we need to sort points according to it and make a similar scanline over this order of points — cover some prefix with first square and suffix with second square.
Note that if we make top-left square scanline we are making bottom-right square scanline because of symmetry. So we only need two of scanline of these type: for top-left corner and for bottom-left corner.
So, in general we need to make 4 similar scanlines that only differ in points order:
For each scanline we iterate over all positions and for each position $$$i$$$ we cover first $$$i$$$ points with one square and all other points with other square. One of these coverings is guaranteed to give a best answer.
I'm pretty sure this is correct, but I have not submited it because our div2 contest is finished and I cannot find any upsolving available. Does anyone know where we can upsolve it?
First, thank you for interesting problem sets! I really enjoyed it.
I read the editorial of problem B, and I can never figure out why the fact the good subsets form a matroid leads a generalized Hall’s theorem to hold. Would you share outline of the proof?
Just use this simple augmenting paths solution in O(nk^3), do not care about this matroid bullshit :P. However if you really want to understand that exponential solution then you can do this proof in a more direct fashion with some max-flow min-cut type argument without using any matroids, but don't ask me more.
I can describe it tomorrow more thoroughly. The basic idea goes like this:
More details will come later. :)
Thanks a lot! I'll try to understand the idea :)
So it took me more time to write this down, sorry!
Let's remind the inductive definition of "OK" and "good" subsets:
We want to prove that a subset $$$A$$$ is good if and only if there exists a flow originating in $$$A$$$, using each vertex in the network at most once and going all the way to the right layer.
Let's assume this is not true. Then there exists some counterexample $$$A$$$. Without a loss of generality, we can assume that:
Let's rule out a couple of trivial cases: if $$$A=\varnothing$$$, then the set is obviously good and there is a flow of size $$$0$$$ coming out of $$$A$$$. If there is only one layer in the graph, then all sets are OK and good, and there trivially exists a maximum flow from each subset. Now assume that $$$|A| \ge 1$$$ and there are at least two layers in the graph.
If there exists a flow $$$F$$$ of size $$$|A|$$$ from $$$A$$$, then $$$A$$$ is good: for each vertex $$$a \in A$$$, there exists a distinct vertex $$$f(a)$$$ in the second layer such that $$$F$$$ flows from $$$a$$$ through $$$f(a)$$$. Therefore, for each subset $$$X \subseteq A$$$, there exists a neighborhood $$${f(a) \mid a \in X}$$$ of size $$$|X|$$$ in the second layer. It's possible to push the flow from this neighborhood to the right end of the graph, so basing on our assumptions ("$$$A$$$ is the leftmost counterexample"), this neighborhood is good as well. Therefore, each subset of $$$A$$$ is OK, so $$$A$$$ is good.
The other way around is a bit more complicated. Assume that $$$A$$$ is good, but there is no flow of size $$$|A|$$$ from $$$A$$$. What is the obstacle to the existence of the flow? We can see it's the vertex cut $$$C$$$ of size $$$<|A|$$$. In other words, we can erase at most $$$|A|-1$$$ vertices from the network so that there won't be any path from $$$|A|$$$ to the right end of the graph. Now, consider two cases.
This is enough to prove that "a set is good <=> there is a flow from this set."
Auto comment: topic has been updated by mnbvmar (previous revision, new revision, compare).