I can't seem to figure out why my F gets TLE. I used the same trick as the editorial. Link.

Is it some cache-friendly stuff that I am missing? Or is there some other stupid thing that I am doing in my code.

Could have solved G for the first time in contest today. But I am so bad at implementation :((

BTW today's contest seemed a lot less mathy. Good job!

I have an $$$O(N \log N + \sum |S_i|)$$$ solution for E. Observe that the string having maximum LCP with $$$S_i$$$ would be, the one before it and the one after it, when we sort the array $$$S$$$. So, we manage two multisets $$$L$$$ and $$$G$$$, each sorted non-decreasing and non-increasing. Now the rest of the solution is basically calculating the LCP value. Submission here.

After I continually get WA in C, I got impatient and finally got -58 in this round.

After seeing the editoral, I thought my mistake is quite stupid.

:(

Problem E can be easily solved using Trie with a complexity of $$$O(\sum {|S_i|})$$$. Here is my solution

I passed E with Time Complexity $$$O(n\log^{2} \sum S_i)$$$. Maybe the TL limit should be a little tighter.

I use double hash to solve E. My idea is converting all possible prefixes using double hash into a map

For each string I do binary search the answer tp check whether a certain prefix exist in the map

Thanks for the problemset! I love E and G (can't solve G on contest but the double fenwick tree + compression is cool!)

Thanks for the round. Really one of my favorite rounds which includes diverse problems in different topics.
btw, it's my first rated round.

@chokudai I think Task C has weak test cases. I have dmed you the details.

G is solvable using treap. Submission

For problem F, during contest I have almost figured out the solution but failed the complexity analysis part. I could not convince myself that it is O(N^2) rather than O(N^3), until reading the editorial and realize that maybe it is similar to this problem https://codeforces.net/contest/581/problem/F.

I have seen this problem/idea during virtual participation recently but missed such observation during today's contest. Although it is a pity, still thanks to writers for providing such invaluable problems.

Explanation for $$$F$$$ (Same Editorial's idea but trying to make it more clear):

Let $$$dp[i][is\_chosen][cnt]$$$ be the number of subsets with $$$cnt$$$ connected components over the subtree rooted at node $$$i$$$. $$$is\_chosen$$$ is $$$0$$$ or $$$1$$$ and represents whether the subsets include $$$i$$$ or not. After processing the $$$k^{th}$$$ child of $$$i$$$, $$$dp[i]$$$ should have the number of subsets over $$$i$$$ and the subtrees rooted at its first $$$k$$$ children.

When processing the $$$(k+1)^{th}$$$ child (let it be $$$j$$$), all we have to do is to merge $$$dp[j]$$$ to $$$dp[i]$$$, i.e., iterate on every $$$cnt_i$$$-$$$cnt_j$$$ pair and add their contribution $$$dp[i][is\_chosen_i][cnt_i]\cdot dp[j][is\_chosen_j][cnt_j]$$$ to $$$merged\_dp[is\_chosen_i][cnt_i+cnt_j-(is\_chosen_i\ \&\&\ is\_chosen_j)]$$$.

After processing the $$$(k+1)^{th}$$$ child, just assign $$$merged\_dp$$$ to $$$dp[i]$$$. Note that we subtract $$$(is\_chosen_i\ \&\&\ is\_chosen_j)$$$ because if both $$$i$$$ and $$$j$$$ are chosen, they are merged into $$$1$$$ component. We need to take care here because the expression $$$cnt_i+cnt_j-(is\_chosen_i\ \&\&\ is\_chosen_j)$$$ can be $$$-1$$$.

Proof that complexity is $$$O(N^2)$$$:

Observe that when we iterate on every $$$cnt_i-cnt_j$$$ pair, we can imagine this (in terms of iterations count) as iterating on every pair of nodes where the first node is from the currently merged subtrees and the second node is from the new subtree to be merged. Hence, every pair of nodes will be considered only once, i.e., at their lowest common ancestor. Since we have in total $$$\dfrac{N\cdot (N-1)}{2}$$$ pairs, the total number of iterations is bound by that count.

Submission.

Does anyone know how the test cases for E is generated?

I hashed every prefix using a mod of 10^9+7 with a random base (tracking the hashes of different lengths separately). I thought because of the low number of test cases on atcoder, that would be enough. But surprisingly I still failed 3/33 test cases. It passed when I switched to a different (and larger) mod.

give me test cases where

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

int main(){
    int n, m;
    cin>>n>>m;
    vector<int> deg(n, 0);
    for(int i = 0; i<m; i++){
        int a, b;
        cin>>a>>b;
        deg[--a]++, deg[--b]++;
    }
    int deg1 = 0, deg2 = 0;
    for(auto e: deg){
        if(e==1){
            deg1++;
        }
        if(e==2){
            deg2++;
        }
    }
    if(n==1 || (deg1==n-2 && deg2 == 2)){
        cout<<"Yes\n";
        return 0;
    }
    cout<<"No";
    return 0;
}

this will give the wrong answer.

for problem C