tourist's blog

XX Open Cup: GP of Gomel
By tourist, 4 years ago, In English

XX Open Cup Grand Prix of Gomel takes place on Sunday, February 16, 2020, at 11:00 AM Petrozavodsk time.

The links to the contest:

You need an Open Cup login to participate.

I'm the writer of all the problems. Let's discuss them here after the contest!

UPD: Thanks for your participation! Editorial is available.

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

Comments Comments (14)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it +26 Vote: I do not like it

When I login into the page I get the following message: "The virtual contest is in progress. You are not allowed to participate".

EDIT: Now both links given for Div 1. seem broken to me.

EDIT2: fixed, thanks :D

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

How to solve B and H?

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

How to solve E?

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

    Let $$$P(X) = \sum p_i \cdot x^i$$$. We need to find several first coefficients of $$$Q(x) = P(x) ^n$$$.

    We can write equation $$$Q'(x) = (P(X) ^ n)' = n \cdot (P(x) ^ {n-1})P'(x) = n \cdot Q(x) / P(x) *P'(x)$$$

    So $$$P(x) \cdot Q'(x) = n \cdot Q(x) \cdot P'(x)$$$. If we write everything about $$$x^m$$$ it will give us a way to represent (m+1)-th of coefficient of Q(x) from deg(P) previous.

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

Only after reading editorial for A I noticed that it's guaranteed that n is divisible by k. :)

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

How can I obtain an opencup account? I've messaged snarknews on CF but got no response.

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

There is linear solution for F based on fact we can calculate $$$f(k) = \sum\limits_{t\geq n} bin(k, t)$$$ for all k in linear time

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

Instead of matching algorithms for G we can use much much simpler approach (especially when compared to blossom): take arbitrary unmatched vertex and match it to its random neighbour — if it that random neighbour was already matched before then unmatch it

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

    What about the bipartite part? This method works for it too?

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

      Yeah, works like a charm for both bipartite and non-bipartite case :)

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

We can use the symmetric chain decomposition of the boolean lattice to solve the bipartite case for G constructively. You can read pages 5 and 6 of this slide.

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

Will the mirror of this contest available anytime soon on Codeforces gym?

→ Reply