Yeah, thanks for the clarification

"If the counter is zero or below, the current node is 1 — counter steps away from being in range of the last-placed minister on its subtree"

You are not really maintaining this invariant, are you? When merging the results of children of node u, if the condition you mention isn't satisfied you are doing counter[u] = mn - 1. This could be negative but at the same time node u could be within d distance of a minister (perhaps along the child with the maximum counter value)

What am I missing here?

For me, this is one of the toughest div2D's for sure

Has the editorial blog been deleted? I couldn't open it

Explaining the whole idea is a bit difficult, I will just try to give you some idea. First sort the array, now the task is to find the number of subsequences from the first n-1 elements so that they can be put left to the maximum of the array, and the remaining elements go to the right (of course also has to satisfy that additional constraint)

say $$$dp_{i,j}$$$ stores the number of subsequences ending at the index $$$i$$$ satisfying the following condition:
$$$j \gt i$$$ and $$$a_j - a_p \le K$$$ where $$$p$$$ is the last unselected element in the prefix $$$a[1...i]$$$ (Note that I am calling the elements in the subsequence as selected and the rest as unselected).

You can refer to the below code to understand the transitions. This works in $$$O(n^3)$$$ time.

void solve()
{
    int n, K;
    cin >> n >> K;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());
    a.push_back(a.back());
    n = a.size();
    int dp[n][n];
    memset(dp, 0, sizeof(dp));
    debug(a);
    vector<bool> pref_ok(n);
    pref_ok[0] = 1;
    for (int i = 1; i < n; i++)
    {
        if (pref_ok[i - 1] && a[i] - a[i - 1] <= K)
            pref_ok[i] = 1;
    }
    for (int j = 0; j < n; j++)
        dp[0][j] = 1;
    for (int i = 1; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (a[i] - a[i - 1] <= K)
                dp[i][j] += dp[i - 1][j];
            if (a[j] - a[i - 1] <= K)
            {
                if (pref_ok[i - 1])
                    dp[i][j]++;
                for (int k = i - 2; k >= 0; k--)
                {
                    if (a[i] - a[k] > K)
                        break;
                    dp[i][j] += dp[k][k + 1];
                    if (a[k + 1] - a[k] > K)
                        break;
                }
            }
        }
    }
    cout << dp[n - 2][n - 1] - 2 << endl;
}

We can easily optimize it to $$$O(n^2log(n))$$$.

void solve()
{
    int n, K;
    cin >> n >> K;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());
    a.push_back(a.back());
    n = a.size();
    int dp[n][n];
    memset(dp, 0, sizeof(dp));
    debug(a);
    vector<bool> pref_ok(n);
    pref_ok[0] = 1;
    for (int i = 1; i < n; i++)
    {
        if (pref_ok[i - 1] && a[i] - a[i - 1] <= K)
            pref_ok[i] = 1;
    }
    vector<int> pref_sum(n);
    pref_sum[0] = 1;
    for (int j = 0; j < n; j++)
        dp[0][j] = 1;
    int last_fail = 1e9;
    for (int i = 1; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (a[i] - a[i - 1] <= K)
                dp[i][j] += dp[i - 1][j];
            if (a[j] - a[i - 1] <= K)
            {
                if(pref_ok[i-1])
                    dp[i][j]++;
                int k = min((int)(lower_bound(a.begin(), a.begin() + i,a[i] - K) - a.begin()),last_fail);
                if(k < i)
                {
                    dp[i][j] += (i-2>=0 ? pref_sum[i-2]:0) - (k >= 1? pref_sum[k-1]:0);
                }
            }
        }
        if(a[i] - a[i-1] > K)
            last_fail = i-1;
        pref_sum[i] = pref_sum[i-1] + dp[i][i+1];
    }
    cout << dp[n - 2][n - 1] - 2 << endl;
}

Yes. You just need to keep track of all unprocessed queries and the last update performed by us on a vertex. Also when dealing with i which are not divisible by B, you will need to answer queries like is a an ancestor of b(can be done via binary lifting) which incurs an additional logn factor.

AC with 2D Fenwick tree: https://codeforces.me/contest/1864/submission/220595323

Orz

Think of calculating the answer without removing any element for all the prefixes and suffixes. Then you can compute the answer corresponding to the removal of ith element in constant time

Problem D using square root decomposition : https://codeforces.me/contest/1856/submission/217356620

I too used DP. Here's my accepted solution : https://codeforces.me/contest/1849/submission/215947065

Yes

I see you are iterating through mp[v] at the end of dfs in your solution. How is the time complexity not quadratic atleast?

"Every time we copy an element over, the set it is now in will be at least 2 times larger than the set it was previously in"

This is not true right? Say set_1 = {1,2} and set_2 = {1,2,3}, size of the merged set is < 4. I think merging based on size of the subtree is better

You can use polynomial rolling hash function to hash the given strings. Modifying the hash values for query 1&2 is trivial

tbh, that problem has ATCODER written all over it lol

Same. In the first n gaps created by ai's, you can put any value except the value of ai following the gap

That was a great insight! Thanks

For problem D, how is O(n^3) passing so easily? My submission took 78ms. I thought 1e8 operations take ~1sec

What? How did this pass?

What's the full form of PAM?

Very weak pretests for D1 & D2 :( It's not just the negative answers, my submission FST'ed on a tc whose answer is +ve.

PS: I by mistake divided by 2 instead of n at someplace. After changing it, it's AC for D1&2. Frustrating.

Isn't -1 the expected output for this testcase?

In D's tutorial,

"Assume distinct node x and node y are good nodes. Let x be the root of the tree. Define si as the number of special nodes in subtree i. Think about the process we move from x to y. If we try to move the chosen node from its father to i, the variation of cost is k−2s"

What is node i? What exactly are we doing here?

In C, my O((m+n)logn) solution gave TLE on the 6th test case. Any idea why?

I have a mock round for my ICPC regionals and it ends just 5 minutes before the start of this codeforces round. Challenge accepted.

great contest

Damn! I didn't read it and got WA on pretest 4.

thanks

For D, my O(nlogn) solution gave TLE on test_case36. But isn't it good enough to pass in general?