jqdai0815's blog

By jqdai0815, history, 6 years ago, In English

SPOILER ALERT : If you didn't solve the problems in NEERC and you want to enjoy the problems, please don't read.

Spoiler
  • Vote: I like it
  • +386
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it -36 Vote: I do not like it

"about 5.7k" to you means that every self-respectful person must be able to memorize it?

You know that FFT is still considered to be quite hard algo, despite being 15 lines long?

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

    I just want to discuss the possibility of implementing(copying) this algorithm in an ICPC contest.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -17 Vote: I do not like it

      No problem setter should want you to implement this in official contest where you can't copy-paste.

      Problem B from last NEERC is a bad example of a hard problem for an official competition. Problem H is much better — harder to solve but relatively easier to implement.

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

        The intended solutuon is maximum cardinality matching. I think this algorithm should be included in the team code library, and it is not too long (~1k). I think this problem is ok in an ICPC contest.

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

        I agree with Coder. I don't like problems that require the knowledge of too advanced algorithms. Then the contests will be like "who learned the biggest amount of advanced algorithms?" and it will be just like studying. Problems that can be solved by a combination of simple algorithms and your own idea are much nicer.

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

          I don't agree on you. I think Blossom is not that advanced in the algorithmic literature, and it's not hard in implementation. Compare this to discrete k-th root (It's Adelman blah blah, I saw it in some GP but forgot) or fast linear recurrence solver. Blossom is just a textbook algorithm.

          However, your point is also valid, contests only asking for advanced algorithm is also bad. NEERC 2018 was balanced in that point, as it featured both problems.

          Also, considering that ICPC WF even features physics problem, I think your wish is very unlikely to be realized, regardless if it's right or not..?

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            Rev. 2   Vote: I like it +18 Vote: I do not like it

            I would like to add that in that NEERC problem there was no need to write complicated (I don't think I am able to code it fast without team notebook) blossom algorithm. You don't need a certificate, so you just need to compute rank of Tutte matrix. Gauss algorithm is much easier I think.

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

            Regarding blossom/Adleman I have exactly opposite view :P. Baby step giant step is pretty short and intuitive and Adleman was not about knowing it before but about coming up with it knowing BSGS. And I consider blossom as something really painful.

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

              Our teamnote have a neat implementation by Konijntje. He explained this in his blog, unfortunately in Korean :(

              The point is, whenever you have to "contract" the blossom, you don't really need that, but rather expand the blossom into two. Then, you don't need to explicitly mutate the structure, just storing blossom indices are OK. This is not addressed in wikipedia, and this trick makes implementation very easier.

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

                Nice, that's pretty short. The problem with blossom is that it's so rare and so few people know it, but I can see it becoming more widespread once people find out there is an easy implementation.

                Also, I noticed the weighted version is 3x as long as the unweighted one...

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            Rev. 3   Vote: I like it +16 Vote: I do not like it

            IMHO, the only difficult part of fast linear reccurence solving is taking a polynomial modulo another in . And it is often unnecessary (because O(n2) is good enough) or can be avoided by exploiting special structure of the characteristic polynomial in most problems involving fast reccurence solving I encountered.

            Moreover, the idea behind the algorithm is quite intuitive and arises directly from solving the linear recurrence in the most straightforward way: say you have recurrence an + 2 = 2an + 1 + 3an. Its characteristic polynomial is x2 - 2x - 3. Then a4 = 2a3 + 3a2 = 2(2a2 + 3a1) + 3a2 = 7a2 + 6a1 = 7(2a1 + 3a0) + 6a1 = 20a1 + 21a0. Similarly, .

            The transformations happenning are not just similar, they are exactly the same!

            I don't think that it is more complicated than matrix multiplication from the theoretical standpoint. From practical standpoint, there are some troubles if naive polynomial multiplication and division are not fast enough for the problem — but in this case matrix multiplication won't work as well.

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

              The "polynomial modulo" was exactly what I wanted to address. I agree is neat.

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 3   Vote: I like it +21 Vote: I do not like it

        In my opinion, problems requiring heavy library algorithms (especially those that are really rarely used in most contests) are bad in official competitions, but problem B from NEERC is an exception:

        1) There were plenty of problems to solve, most of which required only some well-known algorithms like DFS. 9 problems were enough to get into gold medals.

        2) It was easy to see that this problem requires some non-standard algorithm — one could prove that maximum matching problem in arbitrary graph can be reduced to this.

        3) The problem was not straightforward. Knowing maximum matching algorithm and being able to code it was not sufficient to solving it.

        4) The constraints were low and it was not required to restore the answer, so we could apply some techniques like Tutte matrix or even randomized Kuhn (I'm not sure actually whether it can get AC, but nevertheless) to solve the problem.

        And now compare it to problem G from World Finals 2018, which, in my opinion, is an example of a bad ''library'' problem.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it -79 Vote: I do not like it

          Any problem with 0 accepted is bad by any definition no matter how many other problems were there and how you try to justify it

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

            Do you really think so? Is problem D from NEERC also a bad problem?

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it -18 Vote: I do not like it

              I made a mistake trying to discuss something seriously, will go back to trolling as usual

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

    What does 5.7k mean in this context? 5.7k lines? 5.7k characters?

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

    FFT in 15 lines? wow. Can you please provide a link to the implementation?

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

      38799873

      FFT is 14 non-empty lines, but you also need initFFT, which is 7 non-empty lines. I guess that my implementation is not shortest.

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 3   Vote: I like it -12 Vote: I do not like it

        The following is a modest update to your FFT function implemented in 9 non-empty lines. The initFFT function is implemented in two C++ data structure constructors, and functions dealing with long long integer vectors are wrapped up in one data structure.

        46649368

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

          What the fuck is wrong with you

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            Rev. 2   Vote: I like it +33 Vote: I do not like it

            Nothing should be wrong in revising some appreciated code and sharing the update with its author.

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

          spaces in brackets LUL LMAO ROFL

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            Rev. 2   Vote: I like it +8 Vote: I do not like it

            There is nothing too funny with spaces in brackets to make some code more reader friendly, in my humble opinion.

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

              more friendly (unreadable)

              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                Rev. 7   Vote: I like it +7 Vote: I do not like it

                The following is almost the same code except for using abbreviated names, restoring the initFFT function and leaving no spaces before and after the parentheses, brackets, and operators. This is definitely less funny and more serious code that may save few precious seconds in typing space characters and long identifier names during competitive programming contest. However, this is not the same situation when someone is only practicing or revising some code. Finally, the choice is yours as to which revision is more reader friendly.

                46657091

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Very interesting exercises. Thank you!

I believe we should calculate s — t cut, not global, in problem 6. Am I right?

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

    A more detailed description is added.

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

    Seriously, how tf is that possible to find a maxcut in planar graph xD? I would have never thought it can be polynomially solvable

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

      The set of edges in a cut is bipartite. Let's look at the faces of our graph: they form cycle basis, so the graph is bipartite iff they all have even length. In dual graph it means we have to choose maximum weight subset of edges so that all degrees are even. This is equivalent to problem 1.

»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

The problems are very interesting! Now I kind of want to learn Edmonds algorithm.

»
6 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

OK, let's crowdsource solutions to these problems:

1
6
9
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    8
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Problem 8 is in Codechef, and our ICPC team used it to check our blossom implementation.

      Question (Spoiler)
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's well known in Poland (it was known even before CERC 2011 where some people already knew it) and I have to admit it's one of my favorites problems as well :)

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it
        Spoiler
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    4
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Sorry, the edges should be non-negative here. The problem should be as hard as Hamilton cycle if edges can be negative.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    2
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    3
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It seems that an edge will be chosen twice in the matching.

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

        No. Each edge has 2 vertices corresponding to it. It is taken iff the edge between those vertices is taken. Otherwise, both of those vertices are matched with one of additional deg(v) - 2 vertices. How could we take the same edge twice?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    Proof for 9
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What are some good sources on implementing general matching? Both maximum cardinality and maximum weight versions. I can find some versions (e.g. here) but I'm not sure if it is feasible to fit them into a codebook. Is there something reasonable running in o(n3)? Or does one usually just compute the rank of the Tutte matrix? Thanks!

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

    This is an algebraic approach to maximum cardinality matching with a certificate.

    The algebraic approach is slow, but it's easy to implement and remember.

    When it comes to finding a maximum matching instead of the cardinality, it becomes much more complicated. I think the combinatorial one is better.

    There are also some randomized (heuristic) and super short approaches here to find the maximum cardinality matching, and we don't know how to fail them now.

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

      http://acm.timus.ru/problem.aspx?space=1&num=1099

      This problem asks you to find max. cardinality matching in a general graph and print edges.

      Randomized solution gets WA 12 while both blossom and algebraic solutions get AC.

      Submissions for randomized and algebraic ones.

      According do Burunduk1 there are graphs where the probability for randomized algorithm to find max. cardinality matching is exponentially small.

      I read his claim here, unfortunatelly in Russian. He doesn't specify what type of graph it is.

      http://acm.math.spbu.ru/~sk1/courses/1718f_au2/conspect/conspect.pdf

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

        I increased the randomized time from 5 to 500 and it got accepted now.

        Actually, the problem puzzled me several years that if there are hard cases under the constraint we can accept in the algorithm contest (like n ≤ 1000).

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

    There is an implementation of the algorithm by Min_25 on github. It's long, so not really suitable for ACM codebooks.

    There's also a long code for weighted general perfect matching by Min_25 on github.

»
6 years ago, # |
  Vote: I like it -20 Vote: I do not like it

So many red coders discussing on this topic meaning this is probably way too difficult for me to understand. I was wondering it would be nice if the blogger put a rating on the blog. If it is above 2400 then I will probably ignore it.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Spoiler
  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it
    More spoiler