XXI OpenCup GP of Nizhny Novgorod

Time: Feb 7, 11:00 UTC+3

Link: Click (OpenCup login needed to participate)

Authors: Um_nik, Merkurev, KAN, WYOCMWYH with help from I_Remember_Olya_ashmelev, Ferume, fake123 and dario2994.

The contest was used for Petrozavodsk training camp and ICPC training camp.

Editorial

Comments (22)

• 9 months ago, # ^ |

  C: The answer is ϕ(n)⋅(n−1k−1)ϕ(n)⋅(n−1k−1), which you can compute in O(k)O(k) time (note that k≤n4k≤n4 so it's barely fast enough.

  E: Compute a maximum matching (of size MM) using Edmond's Blossom Algorithm. Basically, you can reduce the problem of whether there is a vertex cover of size MM to 2-SAT (because the vertex cover must contain at least one vertex per edge in the matching), which you can solve in O(m+n)O(m+n) time. For the case M+1M+1, try all extra unmatched vertex to take into the vertex cover as well as all edges in the matching where both endpoints are taken.

• 9 months ago, # ^ |

  ← Rev. 2 →  

  +1

  The contest is still running for Div.2 :) As it was postponed 3 times, and then started, but without problems(!), and so later it restarted again :)

  UPD. It's just finished. How to solve Div.2 Problem H. "Ending by 3"?

• 9 months ago, # ^ |

  If that holds, then you can also solve the problem in O(nC1/3)O(nC1/3) without assuming that all pipi are distinct, by grouping items with equal pipi, and noticing that if we have a group of elements with equal pipi, and in the optimal solution to dp[i][k]dp[i][k] we take mm of them, then in dp[i][k+1]dp[i][k+1] we take mm or m+1m+1 of them.

  I didn't notice that all pipi are distinct during the contest, so this was what I did. I don't know how to prove that that observation holds, though.

  • 9 months ago, # ^ |

    You can prove the observation by considering this as a min-cost matching problem. The addition of one new "slot" can only add one new augmenting path, which must consist of taking one new souvenir and shuffling some others around.

• 9 months ago, # ^ |

  I'm pretty sure you can't just solve max matching just by trying random matchings; there are graphs with few max matchings, so finding one randomly is probably impossible.

  I think the editorial is referring to randomized algorithms like https://github.com/kth-competitive-programming/kactl/blob/master/content/graph/GeneralMatching.h.

  • 9 months ago, # ^ |

    I think referring to some heuristic algorithms for finding augmenting paths which don't have good time bound in non-bipartite graph.

• 9 months ago, # ^ |

  Or use a "better formula" (courtesy of Wikipedia):

  

  Of course, with a brute force when kk is small.

• 9 months ago, # ^ |

  The issue is not in calculation of lnln itself, the issue is in taking difference of them, which creates awful relative error.

  • 9 months ago, # ^ |

    But it's good enough if you use Python and tell its Bigdecimal to have, say, 50 decimal digits of accuracy.

• 5 weeks ago, # ^ |

  There is a link to the editorial in the post.

  • 5 weeks ago, # ^ |

    Thank you.

• 30 minutes ago, # ^ |

  Each multiplier is at least (1+1B√)(1+1B), there are B−−√B of them, (1+1k)k≥2(1+1k)k≥2 for any k≥1k≥1.