yeah, I think it would be great if these posts would contain the timezone/a time-date link like CF contests do!

Noooo :(( Which one was it ?

No.

Neither. It's by last submission.

the explanation for Plat problem can be found at this youtube channel by an AlphaStar student.

Bipartite matching, but I think that exist some solution without this.

I solved it in O(logN*logN), I can give you some hints->

Imagine the first time when you multiply by 2. Then prove that it is never optimal to use division by 2 operation subsequently. (You can only then either multiply by 2 or add 1).

Before using any multiplication operation, you can only choose divison and addition by 1, If the number is odd, obviously you can only add, but if number is even then you can add +1 or divide by 2. Try to prove that IF you choose to add +1, then it is never optimal to use division operation in any next subsequent step.

Let's say you wanna convert a->b using multiply by 2 and adding +1. Then consider the reverse, b->a using divison by 2 and subtracting 1, then if at any stage the number is odd, you can only subtract 1, but if number is even then you can do both, but IF you choose to subtract, then it is never optimal to divide again (in next step or in any next subsequent step). (Prove this again).

Please can you explain how plat A is reduced to a graph ? I found a sol but I don't really see how it reduces to find topology order of a graph..

Also how to solve Gold C please ! My only idea was that you essentially have some sort of trees (like when i point to j you can add an edge), but I can't find anything else...

Thanks by advance for your explanations :)

Gold P3 can be solved w/tree-dp.

Let $$$A$$$ be the input array (transform s.t its values are 0-indexed), and let $$$j = A[i]$$$ be the rightmost index such that in our resulting solution $$$B, B[i]+k \ge B[j]$$$.

Now, imagine we have a directed graph: Let vertex $$$i$$$ represent the value at index $$$i$$$ in our answer. For every $$$0\leq i \lt n$$$, let there be a directed edge from vertex $$$A[i]+1$$$ to vertex $$$i$$$.

Observe that once all of these edges are drawn, our graph is simply a rooted tree with root vertex $$$n$$$.

After building our graph, run a depth-first search from the $$$n$$$th vertex (yes, this technically doesn't "exist", but we relax the condition for the sake of this solution) Allow the $$$n$$$th vertex to take on some large value, say $$$B[n]=10^{18}$$$. Then, in our depth-first search, we visit all child vertices $$$v$$$ of $$$u$$$ in descending order w.r.t to their corresponding positions in array $$$B$$$.

Every time we visit a child $$$v$$$ of vertex $$$u$$$, we set $$$B[v] = B[u] - k - 1 - \sum{sz[u]}$$$, where $$$k = 10^{10}, $$$ and $$$\sum{sz[u]}$$$ is the sum of the sizes of the subtrees of vertex $$$u's$$$ children that have been processed so far. Once our dfs finishes, our target array will have been constructed.

So, why does this work?

Sketch of Correctness:

1) The time complexity of this solution is straightforward. Our graph is a tree with at most $$$n \leq 10^5$$$ nodes, so surely our solution will run in $$$O(n)$$$.

2) The tree is connected by the nature of the construction, which means array $$$B$$$ will be filled by the end of this process.

3) For every $$$0 \le i \le j \lt n$$$, $$$B[i] \leq B[j]$$$ holds. To show this, it suffices to prove that the length of the path from vertex $$$n$$$ to vertex $$$i$$$ is always greater than or equal to the length of the path from vertex $$$n$$$ to vertex $$$j$$$. This is due to the fact that $$$k$$$ >>> $$$n$$$, so $$$k$$$ is the only value that could potentially shift the inequality and is directly proportionate to the length of the path back to the root.

The proof of this is simple. Consider the transpose of this graph. Then, the following condition statement must hold:

Where $$$p[x]$$$ denotes the parent (next vertex) of $$$x$$$ along its path to the root.

Why is this true? Suppose there exists two indices such that $$$x \le y$$$, but $$$p[x] \gt p[y]$$$.

However, recall that $$$B[x] \le B[y]$$$, so it must be true that $$$B[p[x]] \leq B[p[y]]$$$ by the monotonic property of our array. But we assumed that $$$p[x] \gt p[y]$$$, which also means $$$B[p[x]] \gt B[p[y]]$$$. Contradiction.

Hence by the nature of our construction, for any vertex $$$x$$$ and $$$y$$$ s.t $$$0\leq x \leq y \lt n \implies B[x] \leq B[y]$$$.

Note that this condition is sufficient because there is always a path that leads from vertices $$$i, j$$$ to the root, and the length of the path from vertex $$$j$$$ will be a lower bound for the length of vertex $$$i's$$$ path due to the proof above.

4) For every child $$$v$$$ of a vertex $$$u, (v \lt u)$$$, setting $$$B[v] = B[u] - k - 1 - \sum{sz[u]}$$$ allows for the condition $$$B[v]+k \lt B[u]$$$ to be satisfied. Furthermore, notice that $$$B[v]+k \ge{B[u-1]}$$$, because of the contribution of $$$\sum{sz[u]}$$$ and by applying 3).

(Standard disclaimer: I am not USACO staff.)

The promotion threshold is never determined prior to the contest and depends on the results of the contest — harder contests have lower thresholds and easier contests have higher thresholds. You can clearly see this from last year's Gold contests. Therefore, we can infer the promotion threshold has never always "been 750 (as it has been in the previous competitions)."

If you have further concerns about how promotion thresholds are set, you should reach out to the USACO contest director.

You could also do 50% partials on C and full solve A and B Anyway, I think that in 4 hours you definitely have the time to try all the problems, it's important (in terms of contest strategy) to avoid being stuck for too long on the same problem (unless you are BenQ and you are 100% sure you can solve with more thinking)

Lol I made the same mistake. I had the right idea for B, but figured that I must solve C to promote, so I spent most of my time on C. I didn't leave enough implementation time for B, but if I did, it would've been promo.