hmehta's blog

Topcoder SRM 804 & International Coding Challenge w/ $300 in Prizes
By hmehta, history, 4 years ago, In English

Single Round Match 804 & International Coding Challenge

Topcoder and Cognizance'21 IIT Roorkee are excited to bring you International Coding Challenge along with SRM 804. The round is scheduled to start at 07:00 UTC-4 on April 23, 2021. 

Please Note: The contest will be rated but won't award you points on the TCO21 Stage 4 leaderboard. The contest's number of problems will differ from a traditional SRM. The problems are intended for division 1 but the registration is open to everyone. All contestants will participate in the same division. The Coding Phase duration will be 150 mins instead of the traditional 75 mins.

Prizes: 
Winner: $200
Runner-Up: $100

Registration is now open for the SRM in the Arena or Applet and closes at 06:55 UTC-4. The coding phase will start at 07:05 UTC-4, so make sure that you are all ready to go. Click here to what time it starts in your area

Some Important Links:: Match Results (match results, rating changes, challenges, individual test case results), Problem Archive, Problem Writing, Algorithm Rankings, Editorials and Older Editorials(SRM 710 and before),

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

Comments Comments (26)
| Write comment?
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Gentle Reminder: Round begins in 1hour and 30 mins :)

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

Where is c++17?

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

._.

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

You should appreciate that I resisted to offend TopCoder with swear words here even though the urge to do so is still really strong

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

    true

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

    But I already grabbed my popcorn :(

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

    What's wrong with TopCoder?

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

      That they hire -2 (read as "negative two") testers to test their problems

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

    I missed the round, but it seems like the 600-point problem is going to be removed? What happened?

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

      incorrect samples, solutions with same bug passed it, correct not

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

        basically classic wrong-model-solution scenario?

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

          I'm not sure, but most like solution is ok, implementation is wrong.

          How it was on round (in my case): at some moment in code there is sorted vector and you need to take (n/2)th element. It gives WA on sample, but if you take (n/2+1)th — it will passed.

          → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

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

I failed to read that $$$m \leq 18$$$ on the 500-pointer, so I found a solution with a complexity of $$$3^n$$$ regardless of $$$m$$$ instead. Unfortunately it took about 4s in the worst case. The funny thing is Radewoosh misread the problem in the same way and came up with something $$$2^n \cdot n^3$$$, which was also slightly too slow.

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

    Yeah, probably our approaches combined would give $$$O(2^n \cdot n^2)$$$, as he has a good observation while I used some techniques.

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

      Let's say we have $$$a$$$ "pairs" of colors. We want to add $$$\binom{a}{i}$$$ for each $$$i$$$ and $$$i$$$-tuple of disjoint subsets of vertices with a bipartite coloring. So we want something like $$$\sum_i \binom{a}{i} f^a = (1 + f)^a$$$ in terms of subset convolution ($$$f$$$ denotes the number of bipartite coloring for each subset of vertices). It can be done in $$$O(2^n n^2)$$$; we replace the polynomial multiplication with exponentiation during the well-known subset convolution algorithm.

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

        Could you elaborate? What exactly is going on with the $$$(1 + f)^a$$$ part, and what does it mean to replace polynomial multiplication with exponentiation? (I'm assuming you're talking about the subset convolution algorithm toward the bottom of https://codeforces.me/blog/entry/72488)

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

          Sure. Sorry that I was misunderstanding your algorithm and "bipartite coloring" part was wrong. Now that I implemented (https://ideone.com/r2HnIX ), I hope it's correct.

          Let $$$\mathcal{F}$$$ be the set of functions $$$2^{\{1,\ldots,n\}} \to \mathbb{C}$$$. For $$$f, g \in \mathcal{F}$$$, we define $$$f + g$$$ by pointwise addition and $$$f g$$$ by subset convolution. For $$$f \in \mathcal{F}$$$ and $$$a \in \mathbb{C}$$$, we define $$$a f$$$ by pointwise scalar multiplication. This way we have $$$\mathcal{F}$$$ as a $$$\mathbb{C}$$$-algebra.

          We set $$$f, g, h \in \mathcal{F}$$$ as follows: For $$$S \subseteq \{1,\ldots,n\}$$$, let $$$f(S)$$$ be the number of ways to color the vertices in $$$S$$$ in red and blue so that there are no adjancent pair of a red vertex and a blue vertex, $$$g(S)$$$ be $$$1$$$ if $$$S$$$ is an independent set, and $$$h(S)$$$ be $$$1$$$. Then the answer to the problem is of the form $$$(f^a g^b h^c)(\{1,\ldots,n\})$$$.

          (In my previous post I somehow distinguished the empty set, but this wasn't needed. It might sometimes be useful if we have non-distinguishable colors etc.)

          As it is presented in your link or in the paper, the algorithm for subset convolution consists of three steps: (1) (so-called?) zeta transformation, (2) polynomial multiplication $$$2^n$$$ times, (3) Möbius transformation. To compute $$$f^a$$$, noting that (1) and (3) have linearity, we just need to replace the step (2) with exponentiation (some polynomial to the $$$a$$$-th) $$$2^n$$$ times. There is a handy algorithm to exponentiate a polynomial in $$$O(n^2)$$$, so the overall time complexity is still $$$O(2^n n^2)$$$. Actually this is correct for any $$$a \in \mathbb{C}$$$ as long as we have $$$f(\emptyset) = 1$$$, since $$$f^a$$$ has a nice power series expansion. It is also similar for any combination of $$$\mathbb{C}$$$-algebra operations, like $$$\log f$$$.

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

What has happened with the results? This SRM literally vanished.

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

    Actually, maybe this is the right course of action? Just forget about it and pretend that it has never happened.

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

How to solve the 500 points problem ?

I got the idea of using Inclusion Exclusion principle to get the number of colorings.

For every bitmask of fixing the unlucky edges, how do we find the number of configurations of the graph ?

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

hmehta is there no editorial draft this time??

→ Reply