How did you approach C and D, Can you explain your thinking process?

Is E Floyd warshall?

https://codeforces.me/contest/1157/problem/E the same problem D in the contest just replace n with m ^_^

got stuck on both C and D... there a ~3000 rank and ~600 performance gap between those who finished ABCD fastest and slowest...

Nice solution for E. The idea of using a sky node is very elegant.

how to approach on problem D? I got stuck on D ...

Problem G can be solved in $$$O(N|S_\max| + |S_\max|^4)$$$ (where $$$|S_\max| = 10$$$), which is more efficient than the $$$O(K|S_\max|^2)$$$ solution in the editorial.

First, we define a string set $$$T$$$, called "the set of strings that might be the answer."

Next, we consider how to find these strings in the set. We first sort the strings in $$$S$$$ lexicographically in ascending order.

String $$$S_1$$$ is definitely a candidate, so we add it to $$$T$$$.

At this point, any string that might be the answer must start with $$$T_1$$$ as a prefix.

Thus, we directly brute-force check whether $$$S_2$$$ can be a valid string, with a time complexity of $$$O(|S|^2)$$$. The method works by maintaining two pointers, $$$i = 0$$$ and $$$j = 0$$$, and incrementing them as $$$i \gets (i+1) \mod |S_1|, j \gets (j+1) \mod |S_2|$$$. If $$$S_{1,i} \gt S_{2,j}$$$, then $$$S_2$$$ is not a valid answer. If $$$S_{1,i} \lt S_{2,j}$$$, then $$$S_2$$$ might be an answer, and we add it to $$$T$$$.

By following this approach, we find that only the first $$$|S_\max|$$$ elements might be valid answers. Therefore, the time complexity for this part is $$$O(|S_\max|^3)$$$.

When $$$k = \infty$$$, using $$$T_{m=|T|}$$$ repeatedly would be optimal, but since $$$k$$$ is finite, we need to consider how to maintain this.

We observe that the answer must have the following structure:

A certain number of $$$T_m$$$, followed by a certain number of $$$T_{m-1}$$$ (which could be zero), followed by a certain number of $$$T_{m-2}$$$ (which could be zero), and so on, ending with a certain number of $$$T_1$$$ (which could also be zero).

Therefore, we can use dynamic programming (DP), where $$$f_{i,j}$$$ represents the lexicographically smallest string that can be formed using elements from $$$T_{\leq i}$$$, totaling $$$j$$$ elements.

The transition for this DP can be done in $$$O(|T|K^3)$$$, which includes the complexity for string concatenation.

We find that $$$K$$$ is a bit troublesome, but we make a bold assumption: for the first $$$k - |S_\max|^2$$$ strings, we only pick $$$T_m$$$, and only the last $$$|S_\max|^2$$$ strings need further processing.

Here, we discard the DP and directly apply the approach from the official editorial, achieving $$$O(|S_\max|^4)$$$.

Finally, we realize that the previous sorting step is unnecessary. We can directly build a Trie and traverse it to find the first $$$|S_\max|$$$ strings.

E question is so disgusting! The input a, b, and c actually have the same side, so I adjusted it for 40 minutes!

https://atcoder.jp/contests/abc416/submissions/67945292 Can someone help me find the counter test case for my solution ?!

when will rating get updated?

I think today's ABC is good as well. From problem C to F, the topics are [dfs or backtrack], [greedy + binary search or two pointers], [floyd], [dp on trees].

By the way, my solution to problem F is a little bit different from that in editorials.

I use dp[u=1/2/.../n][j=0/1/2][p=0/1/2.../k] to denote the maximum values, where

u denotes the subtree of node-u

j = 0 denotes that node-u is white

j = 1 denotes that node-u is black, and there is still a chance to extend the path to its parent

j = 2 denotes that node-u is black, but we can not extend the path to its parent anymore

p denotes the number of black paths we already have.

Had a bruh moment on E.

I did:

int a, b, c;
cin >> a >> b >> c;
dist[a][b] = c;
dist[b][a] = c;

instead of

int a, b, c;
cin >> a >> b >> c;
dist[a][b] = min(dist[a][b], c);
dist[b][a] = min(dist[a][b], c);

Kept getting WA :(

Can someone please help me with D, I have everything AC except 2 test cases which are TLE. Here's my code:

~~~~~
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target("popcnt")
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
const int dim = 2e5+7;
const int mod = 1e9+7;
const long long inf = 625e9+1;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> superset;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int n,m;
        cin >> n >> m;
        vector<int> a(n),b(n);
        for(int i=0;i<n;i++) cin >> a[i];
        for(int i=0;i<n;i++) cin >> b[i];
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        long long sum = 0;
        for(int i=0;i<n;i++) {
            auto stat = lower_bound(b.begin(),b.end(),m-a[i]);
            int pos = stat-b.begin();
            if(stat!=b.end() && (a[i]+b[pos])%m<(a[i]+b[0])%m) {
                sum+=(a[i]+b[pos])%m;
                b.erase(stat);
            }
            else {
                sum+=(a[i]+b[0])%m;
                b.erase(b.begin());
            }
        }
        cout << sum << endl;
    }
    return 0;
}

~~~~~

https://atcoder.jp/contests/abc416/submissions/68006865

i've read the editoral for E, i already build a sky node, multi edges, and etc but kept getting WA, can anyone help pls

jpr[i] = minimum distance to go to the sky for node i