mnbvmar's blog

XX Open Cup: GP of Warsaw
By mnbvmar, history, 5 years ago, In English

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!

  • Vote: I like it
  • +171
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +119 Vote: I do not like it

Cutest statements ever, highly recommended.

→ Reply
»
5 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Reminder, 15 mins to start!

→ Reply
»
5 years ago, # |
  Vote: I like it +90 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B? I wrote a $$$O(nk^22^k)$$$ solution but passed in 3 seconds.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        That's interesting! Do you mind sharing more details about it?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +2 Vote: I do not like it

            Looks very similar to our one, maybe just the thinking is different.

            → Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Auto comment: topic has been updated by mnbvmar (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    How could you guess Digimons over Pokemons anyway!

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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!

      → Reply
»
5 years ago, # |
  Vote: I like it +36 Vote: I do not like it

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?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    I did everything (including spoons and stack) by myself. Just some time in image editors :P

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    And yes, I'm very proud because of the shadows in G (also by hand) XD

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +34 Vote: I do not like it

      Have you thought about becoming a graphic designer?

      → Reply
»
5 years ago, # |
  Vote: I like it +43 Vote: I do not like it

Will this contest be in gym?

→ Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Where can I find the whole problem set (pdf)?

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

Can anybody explain how to solve div2 Q(Kalevich and Two New Paintings)?

Statement

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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:

    1. by x coordinate
    2. by y coordinate
    3. by Chebyshev distance from top-left corner of bounding box
    4. by Chebyshev distance from bottom-left corner of bounding box

    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?

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like 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?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      max-flow min-cut type argument

      I can describe it tomorrow more thoroughly. The basic idea goes like this:

      • Assume it's not true that "a subset $$$A$$$ in the left-most layer is OK (as defined in the editorial) if and only if there is a flow of size $$$|A|$$$ originating from $$$A$$$." (Assume that this property holds for all layers to the right of the left-most layer.)
      • Take the smallest counterexample $$$A$$$. Then the minimum vertex cut $$$S$$$ has cardinality $$$<|A|$$$.
      • Consider two cases: either $$$S \cap A$$$ is empty or non-empty. If it's non-empty, then $$$A \setminus S$$$ (a smaller set!) is a counterexample as well — contradiction. Otherwise, there must have been a counterexample somewhere later in the graph, which contradicts our assumptions.

      More details will come later. :)

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks a lot! I'll try to understand the idea :)

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        So it took me more time to write this down, sorry!

        Let's remind the inductive definition of "OK" and "good" subsets:

        • A subset $$$A$$$ of vertices in one layer is OK if its neighborhood in the next layer to the right contains a good subset of size $$$|A|$$$.
        • A subset $$$A$$$ of vertices in one layer is good if all its subsets are OK.

        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:

        • $$$A$$$ is in the leftmost layer, and in each next layer to the right this condition holds.
        • $$$A$$$ is the smallest contradictory subset.

        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.

        • $$$A \cap C \neq \varnothing$$$. Then consider a smaller set $$$A' := A \setminus C$$$. It's a subset of $$$A$$$, so it's good as well. Moreover, consider the following cut: $$$C' := C \setminus A$$$. Obviously, $$$C'$$$ forms a cut blocking any flow from $$$A'$$$. Moreover, from some basic algebra on sets, we can see that $$$|A'| - |C'| = |A| - |C| > 0$$$. Therefore, $$$A'$$$ would be a counterexample as well, but it's smaller than $$$A$$$! Contradiction.
        • $$$A \cap C = \varnothing$$$. Without loss of generality, assume that no vertices in $$$C$$$ reside in the leftmost layer (or we can remove them safely from the cut). Now, remember that $$$A$$$ is OK. It means that the neighborhood of $$$A$$$ must contain a good set $$$B$$$ such that $$$|B|=|A|$$$. Now, $$$B$$$ is located in the second layer, and $$$C$$$ is its cut as well! Therefore, $$$B$$$ would be a counterexample as well, but it's not in the leftmost layer. This is a contradiction as well.

        This is enough to prove that "a set is good <=> there is a flow from this set."

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by mnbvmar (previous revision, new revision, compare).

→ Reply