The MEX Foundation Contest #1 (supported by AIM Tech) that was held in the 37th Petrozavodsk Programming Camp now available in the Gym.
The authors of the contest are Jatana, cookiedoth, Egor.Lifar. The problems are of a good quality, a number of participants can approve it.
Special thanks to vintage_Vlad_Makeev for useful advices, LHiC for testing the contest, vintage_Vlad_Makeev for inspiration and AIM Tech Members for the problem review.
The editorial
Link in post doesn't work. Correct one is link.
Thanks for noticing it
Did you understand what is wrong with your solution to B ?
Yes, the idea is correct, but I missed one cycle
forin the implementation. More precisely:Also, because the editorial of this problem is a little bit unclear here the detailed code of the solution:
I am literally scared of the amount of red in this post and comments. The problems are amazing indeed.
Can somebody rank the problems from easiest to hardest (after their opinion) please, because there might be very tough problems that i won't understand even the tutorial. SO it will be easier to know which to try solving for a longer period of time. (Uh, i can already feel the down votes for this comment)
You can sort the problems by the number of the accepted solutions
Wasn't sure if this is accurate, but ok thanks.
I think that this order corresponds the intended difficulty order.
I think I dont understand problem G . i got an example that a subset has to be both blue and red . (if you choose the previous subsets in a particular way.)
n = 4; (i use numbers 1 , 2 , 3 , 4)
now if we choose :
{1} = red
{2} = red
{3} = blue
{4} = blue
{2,3} = red , {1,4} = red => {1,2,3,4} = red
{1,3} = blue , {2,4} = blue => {1,2,3,4} = blue
so what should the color of {1,2,3,4} be ?
You have to assign exactly one of two colors for each subset so that the resulting coloring will be valid.
In your example, none of valid colorings contains red subsets {1}, {2}, {2,3}, {1,4} and blue subsets {3}, {4}, {1, 3}, {2, 4}.
got it thanks
I think problem E is more interesting if we set s<=1e18 (still not too hard though). But either way, I don't understand why s was not up to 1e6, code that I submitted in the contest works in $$$O(2^n \cdot n +ns)$$$
Could you explain your solution?
This problem is equivalent to knapsack with n objects, where k-th object has size k and value of the biggest sum of weights of edges within some k vertices where our knapsack has capacity s. Determining values of objects is easily done in $$$O(2^n \cdot n)$$$. Now let's note that object with biggest ratio value/size is the only one we would want to use at least n times since otherwise we can do some exchange argument. From that we can get O(n^4) solution for that knapsack.
It's cool that this idea works.
In my opinion, the most tricky part in this solution is the proof of equivalence between the initial problem and the knapsack.
Here is the proof, which I have just realized:
Let $$$S_{i}$$$ be the subset of vertices, which have at least $$$i$$$ tokens on it. If we calculate the number of edges in each subset and then sum these values, we will get the sum of minimums, becase each edge is counted the correct number of times. It's easy to notice that $$$S_{i+1}$$$ is a subset of $$$S_{i}$$$. Also, if we have a sequence of nested subsets, we can restore the number of tokens in each vertex (sum of their sizes mustn't exceed $$$s$$$). The author's solution was finding the best sequence in $$$O(2^{n} * n * s)$$$ time by dp.
However, we can find a multiset of subsets with best value and correct sum of sizes with knapsack. We have to prove that we can order them in a sequence of nested subsets. It is true if and only if there are no pairs of intersecting, but not nested subsets.
Let there are such subsets $$$S$$$ and $$$T$$$ in the optimal answer. Let's consider set $$$S \cup T$$$. Its size is not greater than sum of sizes of $$$S$$$ and $$$T$$$, but its value is not less than sum of values of $$$S$$$ and $$$T$$$. So, we can remove $$$S$$$, $$$T$$$ and add $$$S \cup T$$$ to the answer and it won't become worse. I think that in order to get correct solution for answer restoration, we should add best subsets to knapsack in size order.
It works because the cut function is submodular.
I really enjoyed problem E because it was a cool application of submodularity. I am surprised to see it wasn't intended :)
Also, problem D looks interesting. I tried it like 2h and failed to solve :p
Yeah, the problem D has a very beautiful $$$O(N \cdot log^2)$$$ solution, though most of the participants managed to get AC with $$$O(N \sqrt{N \cdot log})$$$ approaches.
So funny that I realized just now that submodularity is in fact needed. I wanted to write a comment explaining why I think submodularity is not needed, but all along that time I was missing one thing and something I considered obvious is in fact not obvious and even false when we allow negative edges. So I think that if we allow negative edges then my solution no longer works and we have to resort to author's $$$O(2^n \cdot n \cdot s)$$$?
If we allow negative edges it can be solved in $$$O(2 ^ N * N ^ 4)$$$. You can do a dp with a simmilar state to the original solution. Let $$$dp(msk, s, fl)$$$ be the maximal score if you can only use nodes in the $$$msk$$$, have $$$s$$$ left. If $$$fl$$$ is $$$true$$$ than you still have another $$$S - N ^ 3$$$ tokens which you will use all on one mask at some point. It can be shown that you will always use at least all of that on one mask. If you have some residue of tokens when using that "special move" on some $$$msk$$$ you simply add it to the $$$s$$$ in the state. Because of that $$$s \leq N^3$$$. In thst way you "dogded" the submodularity issue. The transitions are add a token to all nodes inside of the $$$msk$$$, remove some node from the $$$msk$$$ or use the $$$ fl$$$ on the current $$$msk$$$.
Ah, sure, that's in fact very similar exchange argument that is going on in that knapsack :). Thanks!
It's great to see that both vintage_Vlad_Makeev and vintage_Vlad_Makeev contributed to the contest.
Really enjoyed solving J, although this broke my heart so bad :P. Couldn't even get AC until now (Sorry for the spam lol). I guess I will try reading how the authors implemented it tomorrow.
Actually my initially solution is basically the same except for one thing. Instead of doing sqrt decomposition for getting optimum dp state on each segment with equal mex, I implemented a segment tree with dynamic convex hull in each node. That's possible because we only need to add new lines, as the old ones which can 'disappear' will just be less optimal than the new ones. This gives you O(n logn ^ 2) complexity for the first part of this problem.
So for the second one(in which you need to choose optimal line among those in the last k elements) I used sqrt decomposition just like you implemented, but as tourist told me it can be done with another segment tree of dynamic convex hulls as well. For each line we stored in sqrt decomposition now we can find a segment of dps from which our line can be used to update answer. So we can maintain a segment tree on 'times' and add our line in proper nodes. After that to compute dp we need only to check O(log n) nodes with convex hulls, thus giving us O(n logn ^ 2) complexity overall.
Got it now xD.
Actually the first part I also figured out myself it could be done in O(n logn ^ 2) but it was more convenient for me to just implement sqrt decomposition since I needed to implement the other convex hull for dp states as well.
But idea for the second half is absolutely beautiful. I'm just speechless. Thank you for pointing this out!!!
I think problem J has a $$$O(nlog^3n)$$$ solution,it is easy to write and faster than other approaches.