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),
Gentle Reminder: Round begins in 1hour and 30 mins :)
Where is c++17?
._.
You should appreciate that I resisted to offend TopCoder with swear words here even though the urge to do so is still really strong
true
But I already grabbed my popcorn :(
What's wrong with TopCoder?
That they hire -2 (read as "negative two") testers to test their problems
I missed the round, but it seems like the 600-point problem is going to be removed? What happened?
incorrect samples, solutions with same bug passed it, correct not
basically classic wrong-model-solution scenario?
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.
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.
Yeah, probably our approaches combined would give $$$O(2^n \cdot n^2)$$$, as he has a good observation while I used some techniques.
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.
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.com/blog/entry/72488)
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$$$.
What has happened with the results? This SRM literally vanished.
Actually, maybe this is the right course of action? Just forget about it and pretend that it has never happened.
The last SRM was in March. What are you talking about?
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 ?
hmehta is there no editorial draft this time??
Sorry for the delay in response here, was not well over the last 7-8 days and thus couldn't reply.
Apologies everyone for the issue with the problems and not being tested, we will surely take care and if anyone of you is interested in being a tester for the next round please reach out to me: [email protected]
Thank you for your patience and I hope everyone is safe and healthy.
hey! hmehta
you said 2 days, it's been 2 weeks :)
Here's the draft https://docs.google.com/document/d/e/2PACX-1vSzXrGhJNBuMY-HyoTo-emkvDUn2eDISuKQV2vmVaXyhVDbTOBSTtegTunhovSKspv0d9S6e2m49t6J/pub