maroonrk's blog

estie Programming Contest 2023 (AtCoder Regular Contest 169) Announcement
By maroonrk, history, 12 months ago, In English

We will hold estie Programming Contest 2023 (AtCoder Regular Contest 169).

The point values will be 400-500-600-700-900-900.

We are looking forward to your participation!

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

»
12 months ago, # |
  Vote: I like it +30 Vote: I do not like it

How to solve A? 🤡

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

    Consider the "contribution on the answer" by each depth of the tree. This "contribution" increases overwhelmingly as the depth increases. So, for each depth, from leaf to root, consider the sum of the values on that height. If this sum is nonzero, this sum will overwhelm the value in finite time. If this sum is zero, this sum does not affect anything. Run a greedy based on this idea.

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

      Thanks, now I get it.

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

      Can you share your solution please?

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

      Actually the "contribution" is the binomial coefficient. Let $$$Z=10^{100}$$$, then the $$$i$$$-th depth (the root is the $$$0$$$-th) has the coefficient of $$$\binom{Z}{i}$$$. So ofc when $$$i$$$ gets bigger $$$\binom{Z}{i}$$$ gets surprisingly bigger too.

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

        I knew this implicitly but I was too lazy to calculate

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

    make graph out of P, edges $$$a[i] -> i$$$, $$$2 <= i < N$$$, now see that the nodes at more distance from 1 will dominate, so for all nodes at d from 1 find the sum of $$$a[i]$$$ of all such nodes, the largest d for which sum is non zero will dominate.

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

I haven't solve anything. I don't understand it's not my day, or the contest was quite difficult ?

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

How to solve B!?

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

Trying to solve C == Communicating with aliens

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

    Actually for me, it felt quite different (not necessarily easy, but still in a good way) compared to C's in previous ARCs. If you can come up with a trivial $$$\mathcal{O}(N^3)$$$, the rest should be simply optimizing it to $$$\mathcal{O}(N^2)$$$.

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

      But I thought $$$\mathcal O(n^2)$$$ is completely different from $$$\mathcal O(n^3)$$$ solution.

      My method is:$$$g[i][j]=$$$ ways to determine $$$a_1\cdots a_i$$$ and $$$a_i\neq j$$$.

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

        My method was, $$$dp[i][j]$$$ is number of prefix up to current element where $$$i$$$ comes last, repeated $$$j$$$ times. (transition is done inplace) This trivially leads to a $$$\mathcal{O}(N^3)$$$ DP. However, in here the greatest bottleneck in DP is simply shifting the DP table by one position which takes $$$\mathcal{O}(N^2)$$$ alone in the $$$a_i=-1$$$ case. So I used deques for the DP table, making it $$$\mathcal{O}(1)$$$ per row for shifting. Clearing a row is also tricky but it can be done in amortized $$$\mathcal{O}(1)$$$ using rollback ideas. This led to an $$$\mathcal{O}(N^2)$$$ solution for me.

        Implementation link

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

        My dp method is same as yours, but I solve it with inclusion-exclusion method in $$$O(n^2)$$$. submission

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

felt like B < C < A

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

For problem C, I use dp[i][j] to denote the number of ways, under the condition that, all the -1 in the first i positions have benn determined, and the last element is j.

dp[i][j] = sum of dp[i-x][y], where x=1,2,..,min(j, f(i,j)), and y=1,2,...,j-1,j+1,...,n, and function f(i,j) denotes the maximum number of j that we can have in a row from the i-th position to the left.

Note that for some fixed x, sum of dp[i-x][y] for y=1,2,..,j-1,j+1,..,n, can be computed by dpt[i-x]-dp[i-x][y], where dpt[i-x]=dp[i-x][1]+dp[i-x][2]+...+dp[i-x][n]. Next, sum of dpt[i-x]-dp[i-x][y] for x=1,2,..,min(j, f(i,j)), can be computed by prefix technique again.

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

can somebody explain to me why we need to find the depth? if the value gets replaced so A[P[i]] becomes A[P[i]] + A[i] the index still doesnt change as in P[i] doesnt become something else, only A changes, in other words only the same couple of numbers actually change A[1], can somebody tell me where did i go wrong? Problem A btw

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

    First, the modification relationship can be built as a tree. The value of a node will only be modified by its children. So the deeper the point the higher the priority. Comparisons are made according to depth, and if the sum of the nodes in the current layer is not 0, the positive and negative outputs can be judged, otherwise the next layer up is compared until the point 1 is reached.

    I'm not good at English. I hope this helps :)

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

    My thinking was the same as yours at first, but then I realized that different nodes have different effects on A[1]. This is because some nodes that affect A[1] are themselves affected by other nodes.

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

      oh i think i understand now, so p[3] say changes a[1] but p[3] can be changed by p[5] and so the depth of p[5] is 2 right?

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

does someone have a simpler solution for D?

→ Reply