TripleM5da's blog

By TripleM5da, history, 22 months ago, In English

 Hey everyone!

I'd like to invite you to participate in the JCPC 2022 contest on the gym on Jan/22/2023 13:00 (Moscow time)

The problems were created by me (Yes only me).

I'd like to thank IsaacMoris and El-Ged_Sevawy for helping me prepare the contest and also mahmoudbadawy for helping (can't remember what he did thou).

Also onsite participants might note that statements changed that's because someone I don't like changed my statements for the onsite contest so I decided to publish the original statements here.

Btw spoiler for the contest theme:

Announcement of JCPC 2022
  • Vote: I like it
  • +118
  • Vote: I do not like it

| Write comment?
»
22 months ago, # |
Rev. 4   Vote: I like it +2 Vote: I do not like it

When will the editorial be released? If not, how to solve D, E, H, J?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it
    Problem D
    Problem E
    Problem H
    Problem J
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Any idea for problem I?

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it
        Really fun problem!
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Any idea for problem G please

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it
            Spoiler
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              but in the example we can see that - with u = 7 and v = 1, the output is "No" even though v <= maxVal, which was 10 in the initial array - with u = 6 and v = 3 the output is "Yes" since it matchs your idea

              are you sure that the idea was right or it's the first hint of the problem

              • »
                »
                »
                »
                »
                »
                »
                »
                21 month(s) ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Sorry I got confused between u >= v and u < v, I corrected the above.

»
22 months ago, # |
  Vote: I like it +10 Vote: I do not like it

So how to solve C...?

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

    Get any maximum matching for the graph then remove edge(1,match[1]) and run try_khun(1) on the rest of the nodes after that remove nodes 1 and new_match[1] from the graph

    Do the same for all other i nodes from 2 to $$$N$$$.

    Complexity $$$O(N^2)$$$

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

      Isn't this $$$O(N^3)$$$? (One iteration of Kuhn is $$$O(N^2)$$$)

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        Well yes but no, it's $$$O(N^3)$$$ per say but under given constraints it should pass easily.

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

    The problem asks for the lexicographically minimal perfect matching in a bipartite graph. Let's solve it in $$$O(N M)$$$, where $$$M$$$ is the number of edges in our graph (in our problem, $$$M = O(N^2)$$$.

    First, find any matching. Denote the corresponding mate for vertex $$$i$$$ in the left side as $$$L(i)$$$ and the corresponding mate for vertex $$$i$$$ in the right side as $$$R(i)$$$. We will iteratively adapt this matching to be lexicographically minimal.

    Let's consider vertex $$$i$$$ (in order from $$$1$$$ to $$$N$$$) and its match, $$$L(i)$$$. Let's suppose we want to match $$$i$$$ with some $$$j$$$. One correct approach would be to first unmatch $$$(i, L(i))$$$ and $$$(R(j), j)$$$, forcefully match $$$(i, j)$$$ and run one iteration of Kuhn's algorithm to match $$$R(j)$$$ without visiting $$$i$$$ in the left side; however, this would be too slow ($$$O(N^2 M)$$$), as we have to do this $$$O(N^2)$$$ times.

    However, as stated above, we can match $$$i$$$ with $$$j$$$ if and only if there is an alternating path from $$$L(i)$$$ to $$$R(j)$$$ without visiting vertices $$$1, 2, \ldots, i$$$ in the left side. Then, for a given $$$i$$$, we can run a simple DFS starting from $$$L(i)$$$ to find all reachable vertices on the right hand side via an alternating path (starting with an unmatched edge). Notice that this is done on the transpose of the original graph, as non-matching edges flow from right to left and matching edges now flow from left to right. Then, we can connect $$$i$$$ with the minimum (yet-unassigned) $$$j$$$ such that there is an edge $$$(i, j)$$$ and $$$j$$$ is marked as reachable.

    Complexity is $$$O(N M) = O(N^3)$$$.

    Can it be done faster/easier?