gaurav172, vivace_jr, shaanknight, Asia West, India, IIIT Hyderabad

Topcoder_Updates, why have I not qualified? I finished 12th in the qualification round. (handle: anurudhp). I am a student, and I am located in India. I had clicked all the random registration links on the blog and registered.

I also don't see a few more users who satisfy all the criteria, like kal013 and shivensinha4.

Let $$$N = 2^n$$$ and $$$g_j = \sum_{x | f_x = j} (-1)^{\text{popcnt}(x)}$$$. This gives us $$$b_i = \sum_j \frac{g_j j!}{i! (j - i)!}$$$.

Using sequences $$$A_k = g_k k!$$$ and $$$B_k = \frac{1}{(N - k)!}$$$, we have $$$(A \star B)_{N+i} = \sum_j A_j B_{N + i - j} = \sum_j g_j j! \frac{1}{(j - i)!} = i! b_i$$$

(Intuitively, $$$B' = \sum_j \frac{1}{j!} x^{-j}$$$ multiplied by $$$x^N$$$ gives the polynomial $$$B$$$.)

(QIF in OBH) Don't know if this adds anything new, but here is my intuition for the mistake in computing articulation nodes:

$$$low_u$$$ is the lowest node (by discovery time $$$disc$$$) that you can reach if you take one back-edge from $$$u$$$.

But using $$$low_u \leftarrow \min(low_u, low_v)$$$, where $$$v$$$ is an ancestor of $$$u$$$, you effectively compute the lowest node you can reach taking any number of back-edges. And you may end up not detecting an articulation node, because you skip over it with multiple jumps.

So for the problem, you need to construct a graph where the articulation node $$$u$$$ has a back-edge (to some ancestor), and it has a descendent which has a back-edge to $$$u$$$.

The mistake itself is somewhat similar in spirit to updating knapsack in forward and reverse.

// (1)
for (int s = N - 1; s >= x; s--)
  dp[s] += dp[s - x];

// (2)
for (int s = x; s < N; s++)
  dp[s] += dp[s - x];

(1) computes the number of ways to form a sum $$$s$$$ using $$$x$$$ at most once, and (2) computes the ways to form $$$s$$$ using $$$x$$$ any number of times.

The same way we fix the knapsack DP by reversing iteration order, we can fix the DFS as:

void dfs(int u, int p) {
  disc[u] = low[u] = ++timer;
  for (int v: adj[u]) {
    if (v != p && !disc[v])
      dfs(v);
  }
  for (int v: adj[u]) {
    if (v != p)
      low[u] = min(low[u], low[v]);
  }
}

Computes $$$low$$$ in post-order instead of live updating in-order. Additionally, we can get rid of $$$disc$$$ here.

Seconded. Fun problems and a unique contest type, definitely worth trying!

How to solve F?

That makes sense. Thanks again for the wonderful blog!

Ah nice, that makes sense now, thank you!

One more thing, how do we know that $$$P_4$$$ is sufficient? i.e. if multiple points have the same $$$P_4$$$ value, can we map any permutation of them to the other set, and get a valid solution? I guess you can use some symmetry argument here, but I'm unable to find any.

It is tempting to try the same trick with $$$P_2(x,y,z)$$$, but it is the same for all the points in the set.

How is $$$P_2$$$ same for all points? Is it because the points are generated uniformly at random?

Very nice posts! Looking forward to part 4!

Ah okay, turns out I also need to disable buffering for stdout, by hSetBuffering stdout NoBuffering. It works now! submission — 117843764.

I guess without this, the flushing is environment dependent? Not sure.

IIUC the interact function is fully lazy, it forces and prints one character at a time. And this force usually forces the computation to happen.

So here, tracing back, it forces unlines which forces map show which forces solve. And solve consumes input, but only from the second query onwards. And I think all the functions I used are fully lazy.

(I might be wrong about my assumptions of which functions are lazy though.)

but have a batch of mods by the same modulo, you can preprocess something and then divide without idiv.

I don't understand what we can preprocess, and avoid idiv.

Could you elaborate on this?

Really fun contest! The choice of bugs was quite nice and very well disguised. Also bonus points for the easter eggs in the problem statements (like typo/"bug" in IIIT) :P

How to solve I?

How to solve L?

Case 57 is 998244352 2 1 998244353. (Let the modulo be $$$M = 998244353$$$)

So $$$r - l + 1 = M$$$ and $$$n m = 2 (M - 1)$$$
The answer should be $$$M^{2 (M-1)} \mod M = 0$$$.
But if you use $$$b\mod \phi(M)$$$ as the exponent, you are computing $$$0^0$$$ and the code returns 1 instead.

What is IRS?

How to solve I (Interesting Game) and K (Knowledge-Oriented Problem)?
EvenImage?

For multiplication in the finite field $$$\mathbb{F}_{2^q}$$$, we use an irreducible polynomial of degree $$$q$$$.

I can just brute force through all polynomials, and substitute all values to check for roots (and effectively reducibility), and this takes $$$O(2^{2q})$$$ to find one. In this case it is just $$$O(n)$$$, which fits in the TL.

Is there a faster method for doing this? Or is there a different way to define multiplication efficiently?

So you can calculate this dp by BST (or priority_queue) in $$$O(N\log^2N)$$$ time.

Could you elaborate on this?

India IIIT Hyderabad: codelegend, Superty, devanshg27

When will the problems be available in practice mode?

You should rotate it about its circumcenter, and the angle will be the angle subtended by AB (or BC) at the center.

Did you run the code with test case 57 as input (on the codechef IDE)?