I just have a question: Why is the algorithm for F correct? What's the intuition behind it?

"the author is lazy"

Pretty obvious from the way this editorial is written

For problem 1881F - Minimum Maximum Distance , can someone please tell the proof why it is always true to consider the longest distance between the labelled vertex and then divide it by 2 then take ceil of it.

After considering some examples it becomes somehow convincing but not very intutive about why that condition will always be true.

C was the coolest one and it's not even close

Starters were bad(ABC) but the main course was good(DEF) but i am not able to understand the bill(editorial)

Task D

If we assumed 1s can calculate 10^8 times, but in the worst condition(all a are equal to 999983), it will judge near 2000(t)*10^4(n)*10^3 times. Would it TLE?

I am a novice and thank you for your generous advice and point out my mistakes.

https://ideone.com/lyUPEZ

problem F c++ BFS code: why RTE on test 3 ???

I lost the top 150 due to hacking task D :(

Simple and insightful Video Editorials for A-E.

Why is my code for incorrect? I feel like it closely resembles the intended idea. It's prob D. Please help me My code

For F, It's always better to re-construct the tree like this.

It's related to tree diameter (I guess there's no formal proof but this blog will help Blog)

Can anyone please explain how does D solution works? Can't able understand how counting frequency of prime divisors gives our answer.

Only AC 1 problem... f**k me

If someone prefers video explanations or interested in knowing how to think in a live contest or reach to a particular solution.
Here is my live Screencast of solving problems [A -> E] (with detailed commentary in Hindi language).

Can G solved with sqrt-decomposition?, I'm getting WA2 Code

the editorial is short and to the point!!

.

Problem F solutions are based on the tree diameter, It takes some greedy proofs but in the end you can convert the problem to a direct tree diameter problem. Here's a blog

What does question C mean? please help me

Any one Feels that this contest was not for Div.3 ?

It seems to be Harder :(

How do I solve 1881G - Anya and the Mysterious String with Segment tree using Lazy propogation? This is what I've done 227967016, I haven't used Lazy propogation and it's TLE. Thank you in advance.

Why this code doesn't work for problem D?

 int n;cin>>n;
   int a[n];
   ll l=1;
   forn(i,n){
    cin>>a[i];
    l*=a[i];
   }
   ll rl=ll(pow(l,1/n));//taking n-th power
   if(ll(pow(rl,n))!=l){cout<<"NO"<<endl;}
   else cout<<"YES"<<endl;

Could someone explain me the E? How to think the dp which from right to left

I feel it was really a nice contest for anyone starting out on cp in the sense that it offers a good mix of adhoc and dsa

Имеется вопрос. Как я понимаю, на этом раунде задачи сразу проверяются на всех тестах. Тогда почему через день после раунда вердикт задачи B с "Полного решения" поменялся на "Неверный ответ на тесте 18"? Типа добавили новые тесты на некоторые задачи?

f can be solved using dp Let define d(v) as the max distance from vertex v to a labeled vertex in its subtree and define g(v) as the max distance from vertex v to a labeled vertex which is not in the subtree of v then d(v)=max(d(child of v)+1), g(v)=max(g(parent of v)+1,d(sibling of v) + 2) then f(v)=max(d(v),g(v))

F is similar to

The only change is to fix the end points of the diameter as RED nodes.

I did rerooting for F, would've gotten top 100 or something but I had to have a typo that I didn't see

I have two nicer(?) solutions than the official ones.

B: Suppose everything has length $$$l$$$ in the end. Then $$$l \mid A$$$, $$$l \mid B$$$, $$$l \mid C$$$ (proof: run the splitting apart in reverse). This is also sufficient, and uses $$$\frac{A}{l} + \frac{B}{l} + \frac{C}{l} - 3$$$ operations. The number of operations is minimised when $$$l$$$ is maximum, so $$$l := \gcd(A, B, C)$$$; to solve the problem just check if the minimum is at most 3. 228383697

(I saw a lot of people at the top of unofficial standings iterating over $$$(A + B + C) / l$$$ and testing each of them using this condition; it's quite strange to me that they didn't use GCD instead...)

G: There is no need for Fenwick trees or segment trees, you can check palindromes using just the difference array (and maintain bad positions using std::set as in the tutorial). 228383431

Problem G with sets and vectors is also possible submission

Can anybody can tell me whether my solution in F can use when it have the edge-weight?Can it be called DP?228766385

Is it possible to solve F with centroid decomposition? I had TLe attempts

Can someone explain what does this mean ~ Notice that palindromes do not appear or disappear inside a segment, but they can appear or disappear at its boundaries

Problem F: for anyone wondering about the intuition behind the solution, here's a short rundown of the logic, based on the dfs algorithm for finding the diameter of a tree.

Assuming k>=2 (otherwise the solution is trivial):

-> Assume A and B to be the two marked nodes that are the furthest away from one another in the tree. The first observation we need to make is that the maximum path from any and all nodes in the tree to a marked node will always lead to A or B, i.e. either A or B (or both) will be the furthest marked nodes from any node in the tree. This can be visualized by rooting the tree on an arbitrary node on the path from A to B.

-> Now we will consider all nodes at once and using the assumption that each node's maximum distance path will lead to A or B, whichever is furthermost from said node, we can observe that the minimum distance maximum path cannot start from a node outside the path from A to B, because it would be larger than that of a node on that path.

-> This confines the possible candidates for the node(s) which give the minimum maximum distance on the path from A to B. If we conceptually flatten this path to a line, we can see that the answer has to be given by the node(s) at its center, because they represent the minimum of the function max(distance to A, distance to B) on that line. Thus, the answer has to be (distance from A to B)/2, meaning the length of the maximum path from the node at the center of the path to either A or B (which are equidistant). In case the length is an odd number, then the center node will be slightly skewed towards A or B, increasing the length of the path by 1, hence the need to round the number d/2 up.

-> The problem is now reduced to finding the two furthermost marked nodes on the tree and halving their distance, which can be solved with a simple tweak of the standard tree diameter algorithm mentioned above.

My implementation: 232911915 Hope this helps!

can anyone explain me, in the second problem why did he minus 1 after dividing rest both numbers with minimum number??? I don't catch the idea behind that.

G can also be solved only with segment tree. In each node we keep track of the first two characters in the interval as well as the last two (or just one character if its a leaf). Then when we merge two intervals we just keep check if a palindrome is formed at the edges. Updates can also be handled very simply by just applying the shift operation to the characters we keep track of. AC with this idea: https://codeforces.net/contest/1881/submission/240931303

how is the time complexity O(2e5⋅n⋅m) of problem a? thanks in advance .

b/a−1+c/a−1≤3 question no B . what's the reason behind this logic? someone pls help me to understand

can you explain to me why in E we are updating dp[i] as

dp[i]=min(dp[i+1]+1,dp[i+a[i]+1]) and not as

dp[i]=min(dp[i+1]+1,dp[i+a[i]+1+j]+j) for all j st i+a[i]+1+j<n indexing from 0

Can somebody help me with Problem F where the code fails on Test3. I did it with rerooting. This problem is almost similar to CSES Tree Distances I.
Here's my code : `

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

int ht(int node, int par, vector<int> graph[], vector<int> &height, vector<int> &v) {
    int h = (v[node] ? 0 : INT_MIN);
    for (auto x : graph[node]) {
        if (x != par) {
            h = max(h, ht(x, node, graph, height, v));
        }
    }
    height[node] = h;
    return h + 1;
}

void dist(int node, int par, int par_ans, vector<int> graph[], vector<int> &height, vector<int> &ans) {
    vector<int> prefixmax;
    vector<int> suffixmax;
    for (auto x : graph[node]) {
        if (x != par) {
            prefixmax.push_back(height[x]);
            suffixmax.push_back(height[x]);
        }
    }
    for (int i = 1; i < prefixmax.size(); i++) 
        prefixmax[i] = max(prefixmax[i], prefixmax[i - 1]);
    for (int i = suffixmax.size() - 2; i >= 0; i--) 
        suffixmax[i] = max(suffixmax[i], suffixmax[i + 1]);

    int x = 0;
    for (auto y : graph[node]) {
        if (y != par) {
            int i = (x != 0 ? prefixmax[x - 1] : INT_MIN);
            int j = (x != suffixmax.size() - 1 ? suffixmax[x + 1] : INT_MIN);
            int partial_ans = 1 + max({i, j, par_ans});
            dist(y, node, partial_ans, graph, height, ans);
            x++;
        }
    }
    int h = (prefixmax.size() ? prefixmax.back() : INT_MIN);
    ans[node] = 1 + max(par_ans, h);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> v(n + 1, 0);
        for (int i = 0; i < k; i++) {
            int x;
            cin >> x;
            v[x] = 1;
        }
        vector<int> graph[n + 1];
        for (int i = 0; i < n - 1; i++) {
            int x, y;
            cin >> x >> y;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        if(k==1){
            cout << 0 << "\n";
            continue;
        }
        vector<int> ans(n + 1);
        vector<int> height(n + 1);
        ht(1, 0, graph, height, v);
        dist(1, 0, -1, graph, height, ans);
        int p = INT_MAX;
        for (int i = 1; i <= n; i++) {
            p = min(p,ans[i]);
        }
        cout << p << "\n";
    }
}

` The ht function calculates maximum height to reach marked vertex in subtree under node i. The dist function calculates the maximum distance using 1 + max(parent_ans, max height from other children.

why my solution is giving TLE?

int solve(){ int n; cin>>n; vector v(n); input_arr(v); unsigned int x=1; sort(v.begin(),v.end()); for (int i = 0; i < v.size(); i++) { x*=v[i];

}
if(x==1 || v[0]==v[n-1]){

    cout<<"YES\n";
    return 1;

}



int y=1;
int temp=2;
unsigned int curr=b_expo(y,n);
while (curr<x)
{
    y*=temp;
    curr=b_expo(y,n);

}
if(curr==x){
    cout<<"YES\n";
    return 1;
}
while (curr>x)
{
    y--;
    curr=b_expo(y,n);
    /* code */
}
if(curr==x){
    cout<<"YES\n";
    return 1;
}

cout<<"NO\n";


return 1;

}

int32_t main() {

int t;
t=1; // for single test case.
cin>>t;
////

while (t--)
{
    solve();

}
return 0;

}

WHY MY SOLUTION IS GIVING TLE? D. Divide and Equalize int solve(){ int n; cin>>n; vector v(n); input_arr(v); unsigned int x=1; sort(v.begin(),v.end()); for (int i = 0; i < v.size(); i++) { x*=v[i];

}
if(x==1 || v[0]==v[n-1]){

    cout<<"YES\n";
    return 1;

}



int y=1;
int temp=2;
unsigned int curr=b_expo(y,n);
while (curr<x)
{
    y*=temp;
    curr=b_expo(y,n);

}
if(curr==x){
    cout<<"YES\n";
    return 1;
}
while (curr>x)
{
    y--;
    curr=b_expo(y,n);
    /* code */
}
if(curr==x){
    cout<<"YES\n";
    return 1;
}

cout<<"NO\n";


return 1;

}

int32_t main() {

int t;
t=1; // for single test case.
cin>>t;
////

while (t--)
{
    solve();

}
return 0;

}

can some body explain d part

For problem F, can someone tell me why my submission gets TLE on test case 44?

My solution is O(n)(it only does 2 Depth First Searches) and it is a variation of the solution for Tree Distances. That is, for each vertex we calculate the maximum distance to a marked vertex along each of its neighbor connections. This can be easily calculated in a sort of dynamic programming way based on its neighbors' information. Obviously the max distance of a particular vertex to any marked vertex is the max of the values obtained from all of its neighbor directions. Now we know the max distance for each vertex and the problem is basically solved.