Hi! Good luck guys

Good luck and have fun guys!

Good luck,everyone!Have a fantastic grade,bro!

Good luck!

Good luck guys

New Bee

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

Idea behind F ?

Is E Floyd warshall?

https://mirror.codeforces.com/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;
}

~~~~~

D and E are good problems (though I didn't solve them during the contest)

I don't understand D, can someone please explain its approach to me and it will be very helpful if you could give me the proof of the solution that you came up with..

Can anyone explain there approach for F ....cant understand the editorial

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

Please, someone help, keep getting wa on E, here's my code:

//This code was written on my laptop (2025)
/*Powered by STEPAN SIMAK*/
#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 = 5e11+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 test;
    test = 1;
    while(test--) {
        long long n,m,k,t,q;
        cin >> n >> m;
        vector<vector<long long>> g(n+1,vector<long long>(n+1,inf));
        for(int i=1;i<=m;i++) {
            long long v1,v2,w;
            cin >> v1 >> v2 >> w;
            g[v1][v2] = min(g[v1][v2],w);
            g[v2][v1] = min(g[v1][v2],w);
        }
        cin >> k >> t;
        for(int i=1;i<=k;i++) {
            int d;
            cin >> d;
            g[d][0] = t;
            g[0][d] = 0;
        }
        for(int k=0;k<=n;k++) {
            for(int i=0;i<=n;i++) {
                for(int j=0;j<=n;j++) {
                    if(i==j) g[i][i] = 0;
                    g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
                }
            }
        }
        cin >> q;
        for(int i=1;i<=q;i++) {
            long long type,x,y,tt;
            cin >> type;
            if(type==1) {
                cin >> x >> y >> tt;
                g[x][y] = min(g[x][y],tt);
                g[y][x] = min(g[y][x],tt);
                for(int i=0;i<=n;i++) {
                    for(int j=0;j<=n;j++) {
                        g[i][j] = min(g[i][j],min(g[i][x]+g[x][j],g[i][y]+g[y][j]));
                    }
                }
            }
            if(type==2) {
                cin >> x;
                g[x][0] = min(g[x][0],t);
                g[0][x] = min(g[0][x],0ll);
                for(int i=0;i<=n;i++) {
                    for(int j=0;j<=n;j++) {
                        g[i][j] = min(g[i][j],min(g[i][x]+g[x][j],g[i][0]+g[0][j]));
                    }
                }
            }
            if(type==3) {
                long long ans = 0;
                for(int i=1;i<=n;i++) {
                    for(int j=1;j<=n;j++) ans+=(g[i][j]%inf);
                }
                cout << ans << endl;
            }
        }
    }
    return 0;
}

I know brutal force can solve C, but I just wonder how is the idea below failed? If anyone can share a test case that would be great. thanks in advance!

public class ABC416_C {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("input.in"));
//         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Long.parseLong(st.nextToken());
        long k = Long.parseLong(st.nextToken());
        long x = Long.parseLong(st.nextToken());
        List<String> lst = new ArrayList<>();
        for(int i = 0;i < n;i++){
            lst.add(br.readLine());
        }
        Collections.sort(lst);
        long loop = k;
        for(int i = 0;i < loop;i++){
            int p = 0;
            long bulk = 1;
            for(int j = 0;j < k -1;j++){
                bulk *= n;
            }
            while(x > bulk){
                x -= bulk;
                p++;
            }
            System.out.print(lst.get(p));
            k--;
        }

        br.close();
    }
}