tfg's blog

By tfg, history, 20 months ago, In English

In yesterday's div1+2 contest problem E (1804E) required an optimization for bitmask dp looking for cycles that has appeared waaaaaay before in cf, dating back to the beta days in this problem. It seems that it wasn't that well known, looking at the number of TLE submissions, so I'm posting this blog to remind people that there are old rounds/contests and they do have some good or educational problems.

One silly lesson that I learned from an old-ish problem is that writing some combinatorics problems in polynomial form sometimes might expose some observations that might not be obvious at first glance. Perhaps if you have some similar experience you could share it in this blog, as there would be at least one person interested in seeing it (me).

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

| Write comment?
»
20 months ago, # |
  Vote: I like it -56 Vote: I do not like it

> ... there are old rounds/contests and they do have some good or educational problems

unlike modern problems

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

    You dont participate since 2018 dude. Go use your dial up internet to hate somewhere else

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

      This might be one of the sickest burns in CF history.

»
20 months ago, # |
Rev. 2   Vote: I like it +74 Vote: I do not like it

I have one cute problem that could be trivialize by writing the problem into polynomial form.

Problem: Given non-negative integer $$$N, M$$$, find the number of non-decreasing sequence $$$A$$$ with length $$$N$$$ s.t. $$$0 \le A_i \le M \text{ }\forall 1 \le i \le N$$$

Solution
»
20 months ago, # |
Rev. 2   Vote: I like it +44 Vote: I do not like it

This year's IOI had a dp problem which rewritten in polynomial form required multiplying out a lot of linear polynomials, take the derivative and evaluate at 1. We can use Leibniz's rule to see that we need to calculate the product of the linear coefficient of one factor and multiply it with all the other factors evaluated at one.

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

    This year's IOI?

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

      Obviously he means IOI 2022.

      • »
        »
        »
        »
        20 months ago, # ^ |
        Rev. 2   Vote: I like it -67 Vote: I do not like it

        Of course I know that, but it doesn't change the fact that it's wrong. Imagine someone reading the comment later this year.

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

          If you read ppavic's comment in December it will say "9 months ago", everyone will deduce that it's about IOI 2022, lol. Or maybe it's about IOI 2027 ?????!!1!1?

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

    Are you talking about IOI 2022 Fish? I didn't know that it has a solution with polynomials and derivative.

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

      No, about IOI 2022 Circuit.

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

        Lmao, i solved that problem in contest and still didnt know what he was talking about

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

After read this post I started thinking about how to optimize this problem to $$$O(n^2 2^n)$$$, It's really a cool idea (I don't know if it's the same idea) that you can first find all cycles containing vertex 20, then find all cycles containing vertex 19 and not containing vertex 20 and so on.. $$$O(n^2*2^n + (n-1)^2*2^{n-1} + ... ) = O(n^2 2^n)$$$

Unfortunately I wrote 140 lines of code in 1804E but at least I got AC in first try.

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

n/1+n/2+n/3...+n/n = n*log2(n) I forget about it every time XD

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

    nope it's $$$n\times \ln(n)$$$ but not a big problem

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

      It's also not that. If we want to be precise then it's O(NlogN). Before someone replies this with something even more precise, I know that there's a known bound for the error.

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

Late to the party, but shameless self-plug

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

    I understand $$$O(n^{2}*2^{n})$$$ solution but how to do in $$$O(n*2^{n})$$$ ?

    NVM, got it.

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

I've actually seen cycle finding bitmask dp relatively recently (only 1 year ago compared to 13 years ago) in this usaco problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=1209

Its a pretty neat trick and I agree that there might be value in practicing older problems.