Choose your favorite topics!

fix your grammar

I do it!

Me too.

same

Don't ask such questions while the contest is still ongoing,will explain after the contest ends.

It's correct, don't ask such questions when the round is going on.

Pawns: Occupy the squares in the upper right section 7*7, specifically in the first seven rows and the rightmost seven columns. Rooks: Placed on diagonal squares, except for 4 squares occupied by pawns in the upper right region

- P - P - P - P
- - - - - - R -
- P - P - P - P
- - - - R - - -
- P - P - P - P
- - R - - - - -
- P - P - P - P
R - - - - - - -

...

I hope this helps

Quite a difficult contest I guess? Whether on average or just for me.

i had dp[u][i] = answer for the subtree rooted at u, and there were a total of i things placed at u at some point of time (ignore u — parent of u edge for now) and then just transition to parent as :

i) you do operation on u — v(where u is parent), dp[u][i + 1] += dp[u][i] * dp[v][j] * i * j

ii) dp[u][i] += dp[u][i] * dp[v][j]

Answer is just sum of dp[1][i]

https://atcoder.jp/contests/arc171/submissions/50014666

Let $$$dp(x,y)$$$ denote the answer for the subtree of $$$x$$$ and in which the subgraph of this subtree has degree of $$$x=y$$$. Note that $$$y$$$ is upper bounded by number of children of $$$x = child(x)$$$ (tree rooted at $$$1$$$). Initialise $$$dp(x,0)=1$$$ and $$$0$$$ otherwise. So suppose children of $$$x$$$ are $$$c_1,c_2,.......,c_k$$$, and first $$$m$$$ children are processed. Consider a new vector $$$temp$$$ for which $$$temp(y)=dp(x,y)$$$. So the updates while going from $$$m$$$ to $$$m+1$$$ are :

• The subgraph does not contain the edge $$$xc_{m+1}$$$. In that case multiply $$$\sum_{j=0}^{child(c_{m+1})}dp(c_{m+1},j)$$$ to $$$temp[y]$$$ for all $$$0\leq y\leq child(x)$$$. Complexity is $$$O(child(x)+child(c_{m+1}))$$$.

• The subgraph contains the edge $$$xc_{m+1}$$$. In that case add $$$(y+1)(j+1)dp(c_{m+1},j)dp(x,y)$$$ to $$$temp(y+1)$$$ for all $$$0\leq y\leq child(x)$$$ and $$$0\leq j\leq child(c_{m+1})$$$. Complexity is $$$O(child(x)child(c_{m+1}))$$$.

• Set $$$dp(x)=temp$$$ and continue.

Thus total complexity is $$$O(n^2)$$$ as can be easily computed from the above conditions.

Here is the submission: code

Thank you, fixed now.

Nevermind, I was confused. The following placement is possible:

P.P
P.P
.R.

I have created a tutorial and practice contest to help you understand how to compute the sum of $$$\prod deg(u)!$$$ over all spanning subgraphs using DP.

I found B quite harder than C and D, so it depends on the person i would say. And no, C wasnt standard to me, it was just easier for me personally

Took 50mins on B. 15 on C and 25 on D. I think for me C = D, just i didnt identify the easy (standard) way to find chromatic number fast instead submitted wrong guesses