We knew about this solution, but we didn't think it could pass the TL. Also, the fact that this is googleable is less of a concern for the onsite.

We also considered some slight modification to the cost function or further limit the set of allowed operations, but doing so complicated the statement too much.

The value of chromatic polynomial $$$C(x)$$$ when $$$x=-1$$$ can be computed in $$$O(2^nn^2)$$$ by subset power series.

You know what you can do for 63 points? Add vertices in layers. The top layer is made up by all vertices with indegree 0 (in the resulting DAG), the second layer by all vertices with indegree 0 when those are removed and so on. Each layer has to contain no internal edges and each of its vertices has to be connected to the previous layer; this means a sequence of layers uniquely defines a DAG. You can just generate all valid pairs of (this layer, previous layer) and do a DP where each state is (vertices in all layers so far, last layer). Much simpler and much more intuitive, since it just fixes the wrong idea "add vertices one by one and keep the set of those added so far".

We're aware. The point is to solve it without knowledge of chromatic polynomials.

I read your code for problem A, but I wasn't able to understand it.

(Is it calculating C(-1) where C is chromatic polynomial?)

I saw that lots of Chinese students are very strong in the problems like problem A. (efficient bitmask dp, squeeze 3^n poly(n) -> 2^n poly(n) )

Is there any material to study about this?

How do you store the states for A? $$$O(3^n)$$$ memory is obviously too much. For my last submission, I stored a vector of pairs $$$(B,dp[A][B])$$$ for each $$$A$$$ but this only works because the number of nonzero states is sparse. Is there a better way to do this?

If you just want to rotate, the 2 lines you print should be identical. The rotation is uniquely defined by the id of the original shape and by the new partial shape.

The on-site contestants had the checker freely available as a binary. Showing them just the checker log would be meaningless without also seeing the input, and we did not want to give them the test cases.

Map stores nonzero dp[i][x] — dp[i][x-1]

I'm not sure if that solution is the same as me, but after I looked into that submission, I think the idea is the same as mine.

In the official solution, the author mention a data structure called 'range tree' and in subtask 7 we don't have to use range tree. The idea of this solution comes from the idea from solving subtask 7.

The idea is to keep values in the multiset, but the hard part is when we update the root of a subtree into the set. Consider the non-decreasing array C[u,t] in the official solution, when we update the value of the root of a subtree, one element of C[u,t] will be increased, and the array won't be non-decreasing anymore. We try to fix that by resetting the values after that t.

For example: 0 2 2 3 4 4 4 5 5 6 9 9 9

may be changed into 0 2 2 3 7 4 4 5 5 6 9 9 9

so we must reset into 0 2 2 3 7 7 7 7 7 7 9 9 9

To process the reset, we can simply erase items in the multiset and if the last item does not match, just subtract the value there.

The misleading part is that, this sounds like each update takes $$$\mathcal{O}(N)$$$. If we update each nodes, the time would be $$$\Omega(N^2)$$$, but that's wrong, because we can analyze that for each deleted values, they must have been inserted beforehand. Since we can insert only $$$\mathcal{O}(N \log{N})$$$ values (from merge small into large trick), the erasion (sum of all operations) would be also $$$\mathcal{O}(N \log{N})$$$ also. So the amortized time is $$$\mathcal{O}(\log{N})$$$ per operation, and it takes $$$\mathcal{O}(\log{N})$$$ to change the value of the last element. So the update is in $$$\mathcal{O}(\log{N})$$$ amortized.

Therefore, the running time of the whole solution is $$$\mathcal{O}(N \log^{2}{N})$$$ due to merge small into large in $$$\mathcal{O}(N \log N)$$$ and each operation takes $$$\mathcal{O}(\log{N})$$$ on top.

Not sure if this is correct or not, but it is my idea during the contest. My submission: 57889967

But why time complexity is O(3^n)? I know it is right because it runs like O(3^n), but I can't prove it.

here is almost same solution, but without using the fact that answer is m/2 times the ways to construct the DAGs. In this solution I calculate the answers for each subset using the same method and the complexity is the same (but it's kinda slow and there are some constant optimizations used there)

привет If you sort the fruits by D, you can have a straight forward O(n^2) solution For each new day, we can build a dp(u) which is the maximum total of juiciness we can have from the subtree of u. i.e building from bottom to top if d(i) = D(which is the current day), we can have dp(i) = w(i) + sum of dp(v) (v is u's children)

dfs(u): sum<->for(v:child[u])dfs(v),sum+=dp(v) dp[u]=sum if d(u)=D: dp[u]+=w(u)

We can build HLD over this to optimize the code Call f(i) as dp(i) when (D=d(i)) See that if a node i has been calculated, it will remain as f(i) (when d(i)=D) or the sum value of its child (after some days)

Once dp(i) is no longer f(i) -> when a new node p in its subtree is ripe, dp(i) will add w(p). Build hld, and maintain a set. TC: O(n.log^2)