Блог пользователя maroonrk

Автор maroonrk, история, 11 месяцев назад, По-английски

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!

  • Проголосовать: нравится
  • +131
  • Проголосовать: не нравится

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится +63 Проголосовать: не нравится

Both BCD have 600 points?

»
11 месяцев назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Hope I get perf that >=1800

»
11 месяцев назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Wow. Excited!

»
11 месяцев назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

I hope i can reach 1500 tonight.

»
11 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

I just hope I can AC A qwq.

»
11 месяцев назад, # |
Rev. 3   Проголосовать: нравится -65 Проголосовать: не нравится

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    same

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    11 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 месяцев назад, # |
  Проголосовать: нравится -60 Проголосовать: не нравится

trash round

»
11 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

AtCoder Regular Countings 171

»
11 месяцев назад, # |
  Проголосовать: нравится +63 Проголосовать: не нравится

Never felt more badass:

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Has anyone tried simulated annealing in D?

»
11 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)$$$?

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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

  • »
    »
    11 месяцев назад, # ^ |
    Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

    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

»
11 месяцев назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

"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.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone elaborate on the solution of B?

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    11 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    P.P
    P.P
    .R.
    
    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

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

      Correct placement
»
11 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    10 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      10 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

      • »
        »
        »
        »
        10 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

    • »
      »
      »
      10 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        10 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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!.

    • »
      »
      »
      10 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
10 месяцев назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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?

  • »
    »
    10 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      10 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        10 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 :(