maroonrk's blog

AtCoder Regular Contest 171 Announcement
By maroonrk, history, 10 months ago, In English

We will hold AtCoder Regular Contest 171.

The point values will be 400-600-600-600-800-1100.

We are looking forward to your participation!

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

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

Both BCD have 600 points?

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

Hope I get perf that >=1800

→ Reply
»
10 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Wow. Excited!

→ Reply
»
10 months ago, # |
  Vote: I like it +24 Vote: I do not like it

I hope i can reach 1500 tonight.

→ Reply
»
10 months ago, # |
  Vote: I like it +18 Vote: I do not like it

I just hope I can AC A qwq.

→ Reply
»
10 months ago, # |
← Rev. 3   Vote: I like it -65 Vote: I do not like it

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

    same

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

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

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

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

    → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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

    → Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I struggled to solve A. And I attempted to solve B and C but failed. :(

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

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

    → Reply
»
10 months ago, # |
  Vote: I like it -60 Vote: I do not like it

trash round

→ Reply
»
10 months ago, # |
  Vote: I like it +6 Vote: I do not like it

AtCoder Regular Countings 171

→ Reply
»
10 months ago, # |
  Vote: I like it +63 Vote: I do not like it

Never felt more badass:

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone tried simulated annealing in D?

→ Reply
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

My approach for A : First try to place all the rooks on the board and then count the the number of places available for pawns. The optimal way of placing rooks would be spreading them out as far as possible from the center and placing them on the diagonal of the board. For example for N = 5 and a = 2, the optimal placement would be :

.....
.♜...
.....
...♜.
.....

Then just work out some cases to derive the formula. Here's a link to my submission https://atcoder.jp/contests/arc171/submissions/50010665

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial for problem C says:

The answer is the sum of $$$\Pi_{v \in V}{deg(v)}$$$ for all spanning subgraphs. This can be calculated in $$$O(N^2)$$$.

So... how to calculate it in $$$O(N^2)$$$?

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

    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

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

      Can you please elaborate more on what you mean by "i things placed at u"?

      If $$$u$$$'s last child's subtree size is $$$x$$$, I saw from your code that $$$dp[u][i]$$$ can hold positive values up to $$$i=subtree\_size[u]-x+1$$$. So what does $$$i$$$ exactly represent in the $$$dp$$$ state? and how is this approach equivalent to the Editorial's? i.e., Sum of $$$\prod_{i=1}^{N}degree[i]!$$$ over all sub-forests of the original tree.

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

        I was giving my approach not the editorials one. Things plsced at i means the total # ot distinct numbers that the node u has had (ignoring u — par[u] edge)

        Now, when you consider the u — par[u] edge, either you swap or you dont. If you swap, there are a total of (# of numbers placed at u) * (# of numbers placed at par[u]) ways to swap, because you could choose to swap at any point of time

        → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 4   Vote: I like it +8 Vote: I do not like it

    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

    → Reply
»
10 months ago, # |
  Vote: I like it +16 Vote: I do not like it

"6

1 4 4 5 5 6"

is a hack for many AC solutions on B. ex: https://atcoder.jp/contests/arc171/submissions/50020308 (sorry whoever it is, just picked randomly)

basically, solutions which dont check if every cycle of size >1 of a number also ends on that number havent been given WA.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone elaborate on the solution of B?

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

the editorial for C said that the answer "equals to the sum of $$$\prod deg_v$$$. Shouldn't it be $$$\prod deg_v!$$$ instead?

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How can we place 1 Rook and 4 Pawns on a 3x3 board? It seems the editorial claims it is possible, but I can't find a way.

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    P.P
P.P
.R.
    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      It's wrong, there is a pawn in front of pawn at (2,1) and (2,3)

      Correct placement
      → Reply
»
10 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone please explain how to implement the Editorial's idea in problem $$$C$$$ using $$$O(N^2)$$$ $$$dp$$$? i.e., Sum of $$$\prod_{i=1}^{N}degree[i]!$$$ over all sub-forests of the original tree.

I believe the solutions described in this page until now are related to the other idea of modelling the swaps directly.

EDIT: After giving it a second thought, I believe the editorial is referring to the previously mentioned dp solution, and the reference to sum of $$$\prod_{i=1}^{N}degree[i]!$$$ over all sub-forests is just to indicate that the dp solution's answer is equivalent to the formula's result.

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

    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.

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

      Your time complexity analysis is incorrect, the loop is not bounded by O(n) per node, but it amortizes to O(n^2) as a whole. (Counter case : any tree with 1 as root, and n / 2 subtrees on both sides of 1)

      To actually prove the O(n^2) total complexity of that tree dp, the core idea is that every pair of nodes contribute to the time complexity exactly once (at their lca)

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

        You are correct, my bad. I had a feeling something was wrong since it looked too easy.

        Thanks for pointing that out, I don't fully grasp your LCA idea, but I'll think about it and update the tutorial.

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

      also im not sure whats intended for C, since you claim its hard, but it can be done in one line in O(logn)

      answer is independent of tree by trivially contributing edge contribution. Each edge is part of exactly 2^(n — 2) subsets of edges, and contributes 2 to the degree sum when it is present. Thus the answer is (n — 1) * 2^(n — 2) * 2

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yes, it's of course easy with combinatorics (even the first problem can be solved in $$$O(n)$$$). Thanks for sharing the combinatorics approach though.

        I meant hard in the sense that, if you are forced to use the same DP defnition, i.e, $$$dp[i][d]$$$ represents the sum of $$$f$$$ over all subgraphs where degree of node $$$i$$$ is exactly equal to $$$d$$$, then the transitions would require some extra effort. Definitely DP is overkill, but I was trying to apply the same idea from ARC problem to this one to see if I fully understand the concept.

        Spoiler

        Maybe the transitions can be done in an easy manner as well, and I'm just missing something obvious. Do let me know. Thanks!.

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

      Hi adaptatron,

      Thanks for your effort. But I already understand this solution. However, it models the concept of swaps directly (even though it is equivalent to the formula's result). The Editorial gave me an impression at first that there is some other $$$DP$$$ solution which models the formula itself directly, but looks like there is not.

      Note: I know how the swaps concept is equivalent to the formula, but I was just interested to know if there is another solution that evaluates the formula directly.

      → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Why Problem C&D has the same point(600) as Problem B?
I think they are surely more difficult than B, especially C.
I quite like C, and believe it deserves 700!
Is C(or some part of it) a well-known problem in Japan or somewhere?

→ Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

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

      B for me is just looking at the sample3 and the solution comes out directly.
      May be it really depends on the person...

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

        i quickly found what we are being asked to count exactly (divide into groups and condition for groups to be in the same cycle) but then i kept getting ideas which led to nowhere to solve that :(

        → Reply