UnstoppableSolveMachine's blog

By UnstoppableSolveMachine, history, 11 days ago, translation, In English,

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 UnstoppableSolveMachine, cookiedoth, egor.lifar. The problems are of a good quality, a number of participants can approve it.

Special thanks to gritukan for useful advices, LHiC for testing the contest, V--gLaSsH0ldEr593--V for inspiration and AIM Tech Members for the problem review.

The editorial
 
 
 
 
  • Vote: I like it
  • +167
  • Vote: I do not like it

»
11 days ago, # |
  Vote: I like it +48 Vote: I do not like it

Link in post doesn't work. Correct one is link.

»
10 days ago, # |
  Vote: I like it +33 Vote: I do not like it

Did you understand what is wrong with your solution to B ?

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +23 Vote: I do not like it

    Yes, the idea is correct, but I missed one cycle for in the implementation. More precisely:

    Wrong version
    Fixed version

    Also, because the editorial of this problem is a little bit unclear here the detailed code of the solution:

    code with comments
»
10 days ago, # |
  Vote: I like it +28 Vote: I do not like it

I am literally scared of the amount of red in this post and comments. The problems are amazing indeed.

»
10 days ago, # |
Rev. 3   Vote: I like it +25 Vote: I do not like it

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)

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    You can sort the problems by the number of the accepted solutions

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      Wasn't sure if this is accurate, but ok thanks.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it +25 Vote: I do not like it

        I think that this order corresponds the intended difficulty order.

»
10 days ago, # |
Rev. 4   Vote: I like it +10 Vote: I do not like it

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 ?

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +25 Vote: I do not like it

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

»
10 days ago, # |
  Vote: I like it +43 Vote: I do not like it

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)$$$

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    Could you explain your solution?

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +40 Vote: I do not like it

      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.

      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it +30 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          9 days ago, # ^ |
            Vote: I like it +40 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            9 days ago, # ^ |
              Vote: I like it +30 Vote: I do not like it

            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.

          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
              Vote: I like it +40 Vote: I do not like it

            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)$$$?

»
9 days ago, # |
  Vote: I like it +93 Vote: I do not like it

It's great to see that both gritukan and V--gLaSsH0ldEr593--V contributed to the contest.

»
7 days ago, # |
  Vote: I like it +25 Vote: I do not like it

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.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it +33 Vote: I do not like it

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