300iq's blog

By 300iq, 14 months ago, In English

Hello everyone, this summer at Petrozavodsk was my second ICPC contest, now it will be held as OpenCup round.

XX Open Cup Grand Prix of Kazan takes place on Sunday, September 8, 2019, at 11:00 AM Moscow time

The link to the contest. You need an Open Cup login to participate.

To ensure Codeforces traditions, I will say thanks to the testers Benq, wxhtxdy, whzzt, sunset, TLE, ko_osaga, rushcheyo, jiry_2, gamegame, CauchySheep. Also thanks to izban with help in tasks choosing.

UPD: Now the contest is loaded to the gym!

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

»
14 months ago, # |
  Vote: I like it +31 Vote: I do not like it

The contest will start in less than 30 minutes!~

»
14 months ago, # |
  Vote: I like it +74 Vote: I do not like it

Thanks, everyone, for participating! Editorial pdf: link

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

    Can you give the pdf link of problems, its hard to login.

»
14 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Hello! I was the tester, and I really liked problem H here. It is easily my best problem of 2019. Please solve it!

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

    (^з^)-☆ ♥ ♥ ♥ ♥ ♥ ♥

»
14 months ago, # |
  Vote: I like it +38 Vote: I do not like it

My D passed a stress test but failed on test 9. Do anyone have any idea for the reason?

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +28 Vote: I do not like it
    10 11 3
    1 2
    1 3
    1 8
    1 9
    3 4
    3 5
    4 5
    6 7
    6 8
    7 8
    9 10
    
    

    Answer is 4.

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

      Finally I found a stupid bug and ACed. Thank you for the nice problem set:)

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    On the other hand, we got AC on problem A which failed our stresstests 8) (not sure if it satisfied input constraints but we were treating input just as a chordal graph of treewidth <=3) But we managed to find the but afterwards

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe your algorithm of recognition is not correct for arbitary chordal graph with small treewidth?

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That part was trivial. Just find a vertex whose neighbourhood is a clique and remove it . Moreover, naive way of recognition gives you n^2 time, but you can do it with lexbfs in linear or n log n time (I don't remember), what gives a much better complexity than what was written in editorial, since the latter dp part is linear. But anyway, that linear dp part has constant factor sth like 100000, so yeah xD. Our bug was in processing the Join nodes, but it was very hard to find a test where it fails (it was once per a few thousands in our stresstests), so I am not surprised we managed to pass system tests. We didn't think if it is possible to find a failing tests that is compliant with problem constraints, but this should be possible.

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, if with arbitary chordal graph you found it with several thousand iterations, probably Apollonian network will require much more iterations :)

          So it was hard for me to predict your bug :(

          Anyway, hope you liked this problem xd

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

            I was the one to read it and state "well, it's rather obvious — just standard connectivity dp over bounded treewidth" and delegated coding it to Marek xD. So well, let's say that coding these is kind of a masochistic pleasure, like geometry which I forced myself to enjoy xD. And we can brag afterwards that we actually coded on a competition something that nobody sane ever attempts to code xD.

            • »
              »
              »
              »
              »
              »
              »
              14 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Real masochistic pleasure comes from the first solution of J. I spent slightly more than a full day to solve it in that way. Everybody should upsolve J in that way XD

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

                For even more 'pleasure', solve it in basically the same way, but with a LinkCutTree instead of HLD (which I just did).

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Sorry for necroposting, but could you please share how you wrote the generator for chordal graphs with bounded treewidth?

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

        I am not sure that's the exact way we used during contest, but what I would do right now is to start with a triangle and repeatedly find random 3 vertices that form a triangle and create a new vertex and connect it to all vertices of that triangle (since it needed to have tw<=3).

»
14 months ago, # |
  Vote: I like it +103 Vote: I do not like it

I also love the problems, especially F, H and J. One of the best rounds ;)

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

    I really liked F and especially H as well!

»
14 months ago, # |
  Vote: I like it +18 Vote: I do not like it

In K, isn't there $$$K^2$$$ possible candidates? Doing Inclusion-Exclusion over that many elements is too much right?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, there are around $$$70$$$ possible candidates. But with described optimizations solution works much faster than $$$2^{70}$$$.

»
14 months ago, # |
  Vote: I like it +16 Vote: I do not like it

How can I get an Open Cup login QwQ

»
14 months ago, # |
  Vote: I like it +20 Vote: I do not like it

I think the first step of A can be done by removing 3-degree vertex repeatedly.

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

    Well, if you will delete arbitrary vertex of degree 3 it won't work, because at some moment you can delete some border vertex of the triangle, and there may be no possible variant to continue this decomposition :)

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

    Depends on what kind of decomposition you're aiming for. We deleted vertices with degree 3 whose neighbourhood is a clique, but we can get some different decomposition than one described in statement (because of what ~300iq said), but it didn't matter to us at all. Maybe it is important to some other solutions.

    • »
      »
      »
      14 months ago, # ^ |
      Rev. 3   Vote: I like it +20 Vote: I do not like it

      Yes, it was not correct way for "Apollonian Network". However it works when we ignore planarity and we can obtain a tree decomposition of tree-width -4- 3 in O(N). Then we must be able to construct O(N) DP.

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

        Exactly, that's what we did during contest :)

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What's "tree decomposition of tree width 4"?

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

          For Apollonian Network you can build tree decomposition with treewidth 4

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

            To be precise, bags are of size <=4, so the treewidth is <=3 xD

            • »
              »
              »
              »
              »
              »
              »
              14 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              For dp part, what are the states for each bag (k4)? I feel there are too many (like if the corners are used, if the edges are used). But then merging three such states to get the parents state is yet another nightmare. Any simpler way to think about it?

              • »
                »
                »
                »
                »
                »
                »
                »
                14 months ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                Actually you don't need info about edges, just maintain connected components of its vertices and their degrees :)

                Key idea is that in fact you can look at path like a "connected set of vertices with degrees <= 2 and exactly two vertices with degree = 1".

»
14 months ago, # |
  Vote: I like it +9 Vote: I do not like it

300iq Can you share the problem set here as pdf or something for ppl without Open cup logins please :)

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

    Soon I will load the contest to codeforces gym, don't worry.

»
14 months ago, # |
  Vote: I like it +30 Vote: I do not like it

It's funny that problems H and J were kinda similar and during competition I thought that H will be solved by augmenting paths and J will be solved by parametric search but it turned out to be exactly opposite xD

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    XD, for me it looks impossible to use augmenting paths, when you have queries on segments? :P

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's why I had no idea how to solve it xD. By the way, augmenting paths looked impossible in J as well, I have to admit that none of us understands anything from that solution even now :(

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

        Oh, that is sad, I thought that this solution should be simple to come up with but impossible to write :)

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

        I already told you swistakk, as the age passes you are not as clever as you were in your young days, so don't repent if any problem is not solved.

»
14 months ago, # |
  Vote: I like it +13 Vote: I do not like it

In problem E how to do Gaussian Elimination in $$$O\left(\frac{(n+60)^2}{64}\right)$$$ per every new vector?

  • »
    »
    14 months ago, # ^ |
    Rev. 3   Vote: I like it +20 Vote: I do not like it

    Store the basis in form $$$base[i]$$$ — the vector of the maximum price which has its first bit set at $$$i$$$ or None. When adding, iterate over the set bits $$$i$$$ of the new vector. As usual, if $$$base[i]$$$ is None, put it there and break. If the price of $$$base[i]$$$ is lower than the new one, swap your vector with $$$base[i]$$$ and continue as if the new vector was in the basis and you were adding $$$base[i]$$$ to it.

»
14 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Could someone please shed some more light on problem C? I don't really get the idea from the editorial.

  • »
    »
    8 months ago, # ^ |
    Rev. 5   Vote: I like it +18 Vote: I do not like it

    Let's do three DPs:
    $$$f(u, S):$$$ Number of cactuses rooted at $$$u$$$, and the nodes in set $$$S$$$ are available.
    $$$g(u, S):$$$ Same as $$$f$$$, but $$$u$$$ can create at-most $$$1$$$ sub-tree. That is, number of cactuses rooted at $$$u$$$ on nodes from $$$S$$$, such that $$$u$$$ is attached to only one other node or part of only one cycle.
    $$$h(u, v, S):$$$ Number of cactuses rooted at $$$v$$$ with nodes from $$$S$$$, that loops back to $$$u$$$. (Assuming there is already a path from $$$v$$$ to $$$u$$$, this dp should create a path from $$$u$$$ to $$$v$$$, including the possibility of $$$u\to v$$$.)

    Transitions for f(u, S)
    Transitions for g(u, S)
    Transitions for h(u, v, S)
»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone give me 8th test of the problem D, I can't find my bug :(

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

    You may write stress-test, it is not very hard in this problem.

    • »
      »
      »
      14 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I wrote stress-test and found my mistake after my comment :) Thanks anyway!