We will hold estie Programming Contest 2023 (AtCoder Regular Contest 169).
- Contest URL: https://atcoder.jp/contests/arc169
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20231209T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: maroonrk
- Tester: heno239, maspy
- Rated range: — 2799
The point values will be 400-500-600-700-900-900.
We are looking forward to your participation!
How to solve A? 🤡
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.
Thanks, now I get it.
Can you share your solution please?
here you go (Link to submission)
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.
I knew this implicitly but I was too lazy to calculate
make graph out of P, edges $$$a[i] - \gt i$$$, $$$2 \lt = i \lt 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.
I haven't solve anything. I don't understand it's not my day, or the contest was quite difficult ?
How to solve B!?
Trying to solve C == Communicating with aliens
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)$$$.
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$$$.
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
My dp method is same as yours, but I solve it with inclusion-exclusion method in $$$O(n^2)$$$. submission
felt like B < C < A
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.
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
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 :)
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.
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?
Yes.
does someone have a simpler solution for D?