### maroonrk's blog

By maroonrk, history, 3 months ago,

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!

• +132

 » 2 months ago, # |   +30 How to solve A? 🤡
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   0 Thanks, now I get it.
•  » » » 2 months ago, # ^ |   0 Can you share your solution please?
•  » » » » 2 months ago, # ^ |   0 here you go (Link to submission)
•  » » » » » 2 months ago, # ^ |   0 neat solution, thanks :)
•  » » » 2 months ago, # ^ |   0 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.
•  » » » » 2 months ago, # ^ |   0 I knew this implicitly but I was too lazy to calculate
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
 » 2 months ago, # |   0 I haven't solve anything. I don't understand it's not my day, or the contest was quite difficult ?
 » 2 months ago, # |   0 How to solve B!?
 » 2 months ago, # |   +21 Trying to solve C == Communicating with aliens
•  » » 2 months ago, # ^ |   0 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)$.
•  » » » 2 months ago, # ^ |   0 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$.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +6 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
•  » » » » 2 months ago, # ^ |   +25 My dp method is same as yours, but I solve it with inclusion-exclusion method in $O(n^2)$. submission
 » 2 months ago, # |   +22 felt like B < C < A
 » 2 months ago, # |   0 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.
 » 2 months ago, # | ← Rev. 2 →   0 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
•  » » 2 months ago, # ^ |   0 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 :)
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   0 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?
•  » » » » 2 months ago, # ^ |   0 Yes.
 » 2 months ago, # |   0 does someone have a simpler solution for D?