Same. Good luck!

Congrats on promoting!

This time you will be 16 points away from scoring 1016

omg same although it hasn't been long only 1 month

Wow how hard is it to get plat O_O. ur CM...

Congrats bestie :))))

I cleared Bronze with 1000 or 1100 CF rating, but CF and USACO problems are different, I also know someone who passed with ~800 CF rating.

I cleared Bronze with 2350 or 2400 CF rating, but CF and USACO problems are different, I also know someone who passed with 1000-1100 CF rating.

I cleared Bronze with 1400 or 1500 CF rating, but CF and USACO problems are different, I also know someone who passed with 2350-2400 CF rating.

I cleared Bronze with 800 or 900 CF rating, but CF and USACO problems are different, I also know someone who passed with 1400-1500 CF rating.

I cleared Bronze with 500 or 600 CF rating, but CF and USACO problems are different,You need to understand.

My username could not clear bronze with 2097 CF rating and it will forever be stuck in bronze.

I cleared Bronze with 1200 or 1300 CF rating, but CF and USACO problems are different, I also know someone who passed with 0 CF rating.

I cleared Bronze with -100 or 0 CF rating, but CF and USACO problems are different, I also know someone who passed without a CF account.

As a first time gold contestant, I want to pass :clown:

From initial post :

****Do not post anything publicly about the questions (including but not limited to your scores, how you felt about the problems, any content of the problems, etc) until after the contest is over for everyone.

Try this test case:

1
abcde
baacb

The answer is 5, but many people's programs calculate the result as 4 or 6.

The process of transformation:

$$$\texttt{abcde}\rightarrow\texttt{ebcde}\rightarrow\texttt{eacde}\rightarrow\texttt{eaade}\rightarrow\texttt{eaace}\rightarrow\texttt{baacb}$$$

The contest for you ends at your 4 hour mark, or January 31 UTC-12, whichever comes sooner

Were you able to solve the second one (light and switches one) ? I couldn't come up with any proper strategy to make both the strings equal in minimal moves :(

I got full score by making a tree using pointers and some small optimisations

I didn't get P1 completely, only getting a 10/15. However, I'm pretty sure I found the bug in my implementation and that the approach is correct. Basically create a graph between character types where character c1 has a directed edge to c2 if c1 is in the input string and wants to reach c2 in the output string. Observe that each node (a distinct character type) must have an outdegree of at most 1. Otherwise, there's no way to do it. Once you know that the graph is valid, note that the answer is simply the #of edges (not including self-loops) assuming there are no cycles (not including self-loops). If there are cycles, that complicates the solution a little bit. It turns out you'll need to turn one node in the cycle into another character. If any node in the cycle has a child, it's optimal to increase the answer by the length of the cycle, since there's guaranteed to be a valid construction. Otherwise if there's another node that isn't part of any cycle, we can use that and increase the answer by the length of the cycle + 1. Otherwise, it's impossible to fix the cycle. May post some code later, but I need to grab some sleep.

This is a really clever application of binary lifting; do you know any similar problems?

P2: For the first subtask, we can use bitmask DP to solve each query independently. Let dp[m][v] be the maximum mana we can achieve if we visit the fountains represented by the bitmask m, finishing at vertex v. To transition, we can take a path ending at v and append some unvisited vertex u to the end, thus going from dp[m][v] to dp[m|(1<<u)][u]. This changes the resulting mana quantity in two ways: it increases by s * M[u], the mana we consume from u, but forces us to visit all vertices in M earlier, decreasing our total mana by D[v][u] * T[m], where D[v][u] is the length of the shortest path from v to u and T[m] is the total mana accumulation rate summed over all fountains in m. Computing this DP for each query and choosing the maximal dp[m][v] for our end vertex v is sufficient to solve the first subtask.

To solve the next few subtasks, we will compute the DP only once. The idea is that the only part of our transitions which depend on s is adding s * M[u], which happens once for every u in our mask m. Thus, we can ignore this part of our transition when computing our DP. Then, for each query, we can choose m to maximize s * T[m] + dp[m][v]. We still must iterate over every mask for each query, but we no longer have to compute the DP for every query.

To get full points, we observe that the functions s * T[m] + dp[m][v] corresponding to each bitmask are linear in s. As such, each query reduces to finding the maximum value of a set of linear functions at a point, and this is a standard problem which can be solved using the convex hull trick.

I have a different and shorter to code solution to P3. It is optimal to choose a path going up starting at a leaf, where at each node in the path the whole subtree is colored, then choose a path going down to a leaf when uncoloring. The cost of this operation is $$$2 \cdot sub_u$$$, where $$$sub_u$$$ is the subtree size of $$$u$$$ and $$$u$$$ is the top node in the path.

We can make $$$dp_{u, k}$$$ as the minimum cost for a subtree $$$u$$$ where there are $$$k$$$ paths to be used. $$$k$$$ can be $$$1$$$ or $$$2$$$. We denote $$$x$$$ as $$$\sum_{}^{} (dp_{v, 2} + sub_v)$$$, where $$$v$$$ is a child of $$$u$$$. To calcuate the $$$dp$$$ values, we can create $$$cand$$$, which stores the maximum $$$2$$$ values of $$$dp_{v, 2} + sub_v - dp_{v, 1}$$$ in decreasing order. This acts like giving a path to node $$$v$$$.

$$$dp_{u, 1} = x - cand_0$$$

$$$dp_{u, 2} = min(dp_{u, 1}, x - mx, x - cand_0 - cand_1)$$$, where $$$mx$$$ is $$$max(sub_v)$$$, which is basically giving both paths to $$$1$$$ node.

The answer is $$$2 \cdot (dp_{1, 2} + sub_1)$$$.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 200005;
const ll inf = 1e18 + 5;
vector<int> adj[N];
ll dp[N][2], sub[N];
int n;
int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        p--;
        adj[p].push_back(i);
    }
    
    for (int u = n - 1; u >= 0; u--) {
        sub[u] = 1;
        ll x = 0, mx = -inf;
        vector<ll> best;
        for (int v : adj[u]) {
            sub[u] += sub[v], mx = max(mx, sub[v]);
            x += dp[v][1] + sub[v];
            best.push_back(dp[v][1] + sub[v] - dp[v][0]);
            sort(best.rbegin(), best.rend());
            if (best.size() > 2) best.pop_back();
        }
        
        if (best.size() > 0) dp[u][0] = dp[u][1] = x - best[0];
        if (best.size() > 0) dp[u][1] = min(dp[u][1], x - mx);
        if (best.size() > 1) dp[u][1] = min(dp[u][1], x - best[0] - best[1]);
    }
    
    cout << (dp[0][1] + sub[0]) * 2 << "\n";
}