Nice contest. Thnx, Mike!

The system testing is going on for last >4 hrs. Is there a way I can submit problems while system testing goes on for contests?

loved this round. the problems were so unique but system testing is not ending :'(

Good round. I done abcde. We will be waiting for new and interesting rounds from MikeMirzayanov. Thanks for fast editorial.

Problems were really nice. Thanks!

Please someone tell me, why did I get TLE on problem B with this approach??

int main() { // Code int t; cin >> t;

int total = 0;

while(t--)
{
    int n;
    cin >> n;

    vector<int> arr;

    int temp;

    for(int i = 0; i < n; i++)
    {
        cin >> temp;
        arr.push_back(temp);
    }

    int freq[26] = {0};

    string result = "";

    // trace traversal
    for(int i = 0; i < n; i++)
    {
        // letter frequency traversal 
        for(int j = 0; j < 26; j++)
        {
            if(arr[i] == freq[j])
            {
                freq[j]++; // add the frequecy
                result = result + char(97 + j);
                break;
            }
        }
    }
    cout << result << endl;
}
return 0;

}

Can someone tell when rating gets updated.

Here is how i explain C:

Same as Mike, i have:

Cnt0 = the number of x that only appear in A

Cnt1 = the number of x that only appear in B

(1<= x <= k )

(Remember, if a number satisfy Cnt1 condition -> both Cnt0 and Cnt1 is increased) Call Cnt0-k/2= y

So imagine that we have an answer array C of size k, then we put all numbers from A to C, and then what we do next is to replace each number in array C that belongs to A by numbers from B (we can choose to put a number in C from A/B if it appears in both arrays) -> Check if y <= Cnt1

When the answer if no? when there is x (1 <= x <= k ) that doesnt appear in both 2 arrays or y<0 (cant have enough k/2 numbers in C from A).

Sorry if my English is bad.

Another idea for problem F

We can get all the bridges in the graph using Tarjan.

If the edge is a bridge then it's impossible to make a cycle by this edge.

Sort edges by weight and the first edge that is not a bridge surely will make a cycle, then find it by dfs.

submission: https://mirror.codeforces.com/contest/1927/submission/245226535

Another solution for D: Build 2 segment trees on array: for min and max values on range (vertices store min/max value and index). Then we can answer on query: if max(L, R).value == min(L, R).value then answer is -1 -1, else min(L, R).index max(L, R).index

Can anyone share the $$$n^2$$$ solution about G? Thanks a lot.

Great round with unique problems, thanks!

Problem G

$$$O(N^{2})$$$ time complexity

UPDATED https://mirror.codeforces.com/contest/1927/submission/245921562

D using Segment Tree too.

Could you please explain the dry run of the solution of E. Suppose, n=7, k=4 Why, the permutation 1,4,5,7,2,3 6 would not be valid? Why I have to take in this way: 1,8,3,5,2,7,4 ?

Another idea of problem G:

Because every cell must be colored, I considered greedy.
Enumerate each $$$i$$$ from $$$1$$$ to $$$n$$$, suppose that at this moment, all cells from $$$1$$$ to $$$i-1$$$ are colored.
Thinking greedily, it is definitely necessary to color as many cells as possible in $$$i+1$$$ to $$$n$$$ while coloring the cell $$$i$$$, suppose the number as $$$l$$$.
So preprocess the one with the highest number of stained cells out of all the painting schemes starting with $$$i$$$.
Then it is easy to dynamically maintain the $$$l$$$ for each $$$i$$$.

I am not sure if this algorithm is correct. It is even $$$O(N)$$$.

upd: this algorithm is probably wrong. In the last case of the sample, my implementation will use $$$a_3$$$ twice.

Thank you for the contest. I finally reached expert.

hey , the contest counted as unrated for me and I have solved a problem ?????

Is it possible to detect whether an edge belongs to a cycle by just DFS in linear time?

Thanks for the tutorial. I was said that G can be resolved in O(n^2) can someone say me how?

Can someone explain G in simple terms

can someone please explain the editorial of $$$F$$$ in details?

Can anyone tell me why is this giving wrong answer (for problem F). 245356240

My idea here is, find the 2 nodes with minimum edge weight(say n1 & n2) and then do dfs from one of the node(n1) untill you reach another node(n2). In this way you will end up finding a cycle.

What is wrong in this??

1927D - Найди различные! is required almost similar thought as 622C - Не равный на отрезке.

Не знал, что в Диве 3 встречается снм

Is a very nice competition.The question is quite thought-provoking.I like it.

For problem F, can anyone tell me how to solve it if it also asks to minimize the number of vertices in the found cycle? Thanks.

waiting for a rollback :(

Anyone knows how to solve DFS problems in Python? I seem to encounter runtime errors (I assume it's segmentation fault).

For problem F, I found an $$$O(m)$$$ algorithm. 1 DFS to find the minimum edge on a cycle and 1 DFS to get that cycle.

I do sys.setrecursionlimit(10**6) but it will not pass in Python. The same algorithm in C++ passes, but I assume if recursion gets deep enough, even C++ will not be able to do it.

Is it the case that for $$$n \gt 10^5$$$ I should not use DFS? I'm not sure if there's a pattern to iterative DFS (stackless) but I find it a bit hard to shuffle the moments when I'm leaving the node and which metadata to keep.

Does anyone know if there are any traps in Test 19 of Problem F? It seems that the sorting of edges requires O(mlogm), and the DFS to find a path requires O(n), but I keep getting TLE. Or am I just too silly to see some stupid bugs 245508630? I would really appreciate some advice!

I've recently gained an AC verdict on problem G, and I've decided to share my O($$$n^2$$$) solution. The reason for this is that I found the other explanations (including the editorial) not as deep as I would have liked them to be. So here it goes:

Let $$$dp[i][j]$$$ be the minimum number of charges to use in order to paint all cells up until at least index $$$j$$$, with the restriction that we may only use charges up until index $$$i$$$ (both are inclusive).

As always in DP, let's assume the worst initially, and gradually improve on them later on, so set all values to $$$+\infty$$$. To paint all cells until index 0 ($$$j=0$$$), we don't need to use any charges, so let all $$$dp[i][0]=0$$$.

We will use two loops to fill our DP table: the outer loop will gradually allow the use of more and more charges, while in the inner loop we'll try to paint more and more cells using only the allowed charges, but at the same time, also trying to use the least possible of them.

In each iteration of the outer loop, we're allowing the use of 1 more charge compared to the previous iteration. So the natural thing to do is to try to improve on the previous results. For this, we'll see what we can do with the recently allowed charge at index $$$i$$$. We could either not use this charge at all, use it to the left, or use it to the right.

Not using this charge means $$$dp[i][j]=dp[i-1][j]$$$, using this charge to the left means $$$dp[i][j]=dp[i-1][i-A[i]]+1$$$ and using this charge to the right means $$$dp[i][i+A[i]-1]=dp[i-1][i-1]+1$$$. Don't forget to add the boundaries 0 and N, of course a few of these indices may exceed them! Naturally, it's possible for any of these subproblems that we've already found a more optimal solution, in these cases don't actually set them to these candidate values. Also, the case when we use the charge at index $$$i$$$ to the left isn't valid when $$$j \gt i$$$. Notice that when we use $$$i$$$ to the right, it has a constant $$$j$$$ value, so we don't need to put that into the inner loop. Also, because of the fact that we've only updated our DP table at edge cases of the possibilities the recently allowed charge offers, it's possible that we have a higher value at a lower $$$j$$$, so let's solve this issue using a loop after the first inner loop that fixes these values. Note that this doesn't increase our O($$$n^2$$$) time complexity.

So why does this work? Because we only use lower $$$i$$$s to compute the optimal solution for higher $$$i$$$s, and these lower $$$i$$$s are guaranteed to already be solved. Why is that? Because we never set a new value for a lower $$$i$$$.

Except I lied to you (I'm sorry), this does NOT work. We can see this solution failing for test case 11 in the example input. There is 1 more case to consider. That is, when we use 2 charges at indices $$$i$$$ and $$$j$$$ such that $$$j \lt i \lt j+A[j]$$$ and $$$i-A[i]+1 \lt j$$$. In this case, using charge $$$i$$$ to the left and charge $$$j$$$ to the right may give us the optimal solution, but our algorithm skips these cases. The proof is left as an exercise for the reader. We can solve this by saying $$$dp[i][j+A[j]-1]=dp[j-1][i-A[i]]+2$$$. We aren't setting a lower $$$i$$$ here either, nor are we reading a higher $$$i$$$ solution, since $$$j-1 \lt i$$$ (from the case description). So these requirements are still met.

And with that, we've solved the problem! I hope that this comment was helpful for anyone who wasn't able to come up with a solution for this problem on his/her own. Thanks for reading!

My submission for reference: 245501934

So I want to wonder that why the problem C couldn't accept this code?

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mpr make_pair
#define fr first
#define sc second
inline int read(){
	int res=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
	return res*f;
}
const int N=2e5+5;
int t,n,m,k,a[N],b[N],ta[N],tb[N];
bool solve(){
	n=read(),m=read(),k=read();
	for (int i=1;i<=n;i++){
		a[i]=read();
		if (a[i]<=k) ta[a[i]]++;
	}
	for (int i=1;i<=m;i++){
		b[i]=read();
		if (b[i]<=k) tb[b[i]]++;	
	}
	int ca=0,cb=0;
	for (int i=1;i<=k;i++){
		if (ta[i]>0&&tb[i]<=0) ca++;
		else if (ta[i]<=0&&tb[i]>0) cb++;
		else if (ta[i]<=0&&tb[i]<=0) return 0;
	}
	if (ca>k/2||cb>k/2) return 0;
	return 1;
}
signed main(){
	t=read();
	while (t--){
		if (solve()) puts("YES");
		else puts("NO");
		for (int i=1;i<=k;i++) ta[i]=tb[i]=0;
	}
	return 0;
}

F can be solvable using bridges, find the smallest weight edge (u,v) which is not a bridge ,it will be the answer, and for simplicity the required path will be largest path between u,v (can be found using dfs).

Can someone please help me find the test case on which my code is failing.
It is failing test case 6 of problem G. code

Can someone please explain to me why solution in java 245738199 is giving TLE whereas same solution in c++ (245745549) works

Why my DFS in F TLE in Test19 https://mirror.codeforces.com/contest/1927/submission/245777873

alternate solution for F first remove all the bridges from the graph now every edge in graph has atleast one cycle so choose the one which has minimum weight and and get the cycle

#include<bits/stdc++.h>
using namespace std; 
char nl = '\n';
using i64 = long long;
int n, m;
vector<vector<array<int, 2>>> g;
vector<array<int, 2>> brij;

vector<bool> visited;
vector<int> tin, low;
int timer;

void dfs(int v, int p = -1) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    for (auto& to : g[v]) {
        if (to[0] == p) continue;
        if (visited[to[0]]) {
            low[v] = min(low[v], tin[to[0]]);
        } else {
            dfs(to[0], v);
            low[v] = min(low[v], low[to[0]]);
            if (low[to[0]] > tin[v])
                brij.push_back({v, to[0]});
        }
    }
}

void find_bridges() {
    timer = 0;
    visited.assign(n, false);
    tin.assign(n, -1);
    low.assign(n, -1);
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
}

void solve(int t) {
    // cout << "test #" << t << nl;
    cin >> n >> m;
    g.clear(); g.resize(n); 
    brij.clear();
    for(int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        u--; v--;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    find_bridges();
    for(auto& e : brij) {
        for(int i = 0; i < g[e[0]].size(); i++) {
            if(g[e[0]][i][0] == e[1]) {
                g[e[0]].erase((g[e[0]].begin() + i)); break;
            }
        }
        for(int i = 0; i < g[e[1]].size(); i++) {
            if(g[e[1]][i][0] == e[0]) {
                g[e[1]].erase((g[e[1]].begin() + i)); break;
            }
        }
    }
    pair<int, int> ini;
    int cur = INT_MAX;
    for(int i = 0; i < n; i++) {
        for(auto& a : g[i]) {
            if(a[1] < cur) {
                cur = a[1];
                ini = make_pair(i, a[0]);
            }
        }
    }
    for(int i = 0; i < g[ini.first].size(); i++) {
        if(g[ini.first][i][0] == ini.second) {
            g[ini.first].erase(g[ini.first].begin() + i); break;
        }
    } 
    for(int i = 0; i < g[ini.second].size(); i++) {
        if(g[ini.second][i][0] == ini.first) {
            g[ini.second].erase(g[ini.second].begin() + i); break;
        }
    } 

    // bfs form ini.first to ini.second
    vector<int> p(n, -1);
    queue<int> q;
    q.push(ini.first);
    p[ini.first] = ini.second;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(auto& c : g[u]) {
            if(p[c[0]] != -1) continue;
            p[c[0]] = u;
            q.push(c[0]);
        }
    }
    vector<int> ans;
    int x = ini.second;
    while(1) {
        ans.push_back(x);
        if(x < 0 || x >= n) break;
        x = p[x];
        if(ans.back() == ini.first) break;
    }
    cout << cur << " " << ans.size() << nl;
    for(auto& a : ans) cout << a + 1 << " "; cout << nl;
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt = 1;
    cin >> tt;
    for(int t = 1; t <= tt; t++) solve(t);
}

Unable to understand how problem D will be solved.Can anyone give me a hint