Nice contest. Thnx, Mike!

Good round!

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;

}

fast editorial

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

245202834 why it is wa 2? I'm trying to use two pointers help me please problem C

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.

I got TLE ON problem D with binary search any one have an idea why ? https://mirror.codeforces.com/contest/1927/submission/245354533

Thank you for the contest. I finally reached expert.

Interesting pset. Thanks!

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

Can someone explain me why the author’s solution for problem B is not of complexity O(N^2)? I would assume doing s += chr(97 + j) to be of O(N) since strings are immutable and don’t have append in amortized O(1) like lists do

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?

Anyone resolved the problem D with Segment Tree?

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 встречается снм

Can someone explain Problem E in an easier way? I thought of switch alternately between largest evens and largest odds but that doesn't seem to work. UPD: I solved it. Used the intuition to increase the values at even indices and decrease at odd indices.

Excellent contest.

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

Can somebody please look into this submission of b and tell why I am getting TLE? Thank you. https://mirror.codeforces.com/contest/1927/submission/245142912

I am getting a memory limit exceeded error on test case 27 in code 245453024

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 > 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.

I am trying to solve 1927D - Найди различные! using MO's algorithm. But, getting TLE. plz help me!!!

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!

My Submission

1927D - Найди различные! 3 test cases have passed completely, 4 test case it is giving me wrong answer. Any suggestion how to fix that?

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 > 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<i<j+A[j]$$$ and $$$i-A[i]+1<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<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

A

Problem-D can easily be solved by using next greater and next smaller element.

Claim : If in [l,r] we don't have all same elements then we could just pick the lth element and find its next strictly greater element or smaller as well . If that thing exists and is within r , then answer exists otherwise NOT .

TC : O(n) for precomputation and O(1) per query.

Hope it helps.

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).

B.following the string problem is getting tle can anyone get it in python

Anyone can tell me how can i optimize this code of D problem. It's showing MLE which is obvious but then how alternatively I can solve it with same approach?

def bs(s,e,a,dp):
    if(s==e):
        dp[s][e]=[False,s,s]
        return(False,s,s)
    if(s+1==e):
        dp[s][e]=[a[s]!=a[e],s,e]
        return(a[s]!=a[e],s,e)
    if(dp[s][e]!=-1):
        return(dp[s][e])
    else:
        mid=(s+e)//2
        x1,y1,z1=bs(s,mid-1,a,dp)
        x2,y2,z2=bs(mid,e,a,dp)
        if(x1 or x2):
            if(x1):
                dp[s][e]=[True,y1,z1]
                return([True,y1,z1])
            else:
                dp[s][e]=[True,y2,z2]
                return([True,y2,z2])
        else:
            if(a[y1]!=a[y2]):
                dp[s][e]=[True,y1,y2]
                return([True,y1,y2])
            elif(a[y1]!=a[z2]):
                dp[s][e]=[True,y1,z2]
                return([True,y1,z2])
            elif(a[y2]!=a[z1]):
                dp[s][e]=[True,y2,z1]
                return([True,y2,z1])
            elif(a[y2]!=a[y1]):
                dp[s][e]=[True,y2,y1]
                return([True,y2,y1])
            else:
                dp[s][e]=[False,s,e]
                return([False,s,e])
        
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().strip().split()))
    q=int(input())
    dp=[]
    for i in range(n):
        dp.append([])
        for j in range(n):
            dp[i].append(-1)
    for i in range(q):
        l,r=map(int,input().strip().split())
        if(a[l-1]!=a[r-1]):
            print(l,r)
        else:
            s,e=l-1,r-1
            ans=bs(s,e,a,dp)
            if(not ans[0]):
                print(-1,-1)
            else:
                ab=ans[1]+1
                cd=ans[2]+1
                print(min(ab,cd),max(ab,cd))

Thanks in advance !!

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 anyone explain me the second paragraph of the solution of Problem D?

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

Hi all,

I read the tutorial and got accepted on problem F, but I still have one question: What if we just choose the edge with the minimum weight and then find any cycle which contains that edge. Isn't that simpler? Do we still have to use DSU and stuff?

Thanks in advance.

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

Thanks for Python solutions besides the great contest!

someone pls explain the solution to G in simple words

difficult to get around for me

Can anyone look into my submission for F? It's MLE in TC 7.

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

I am trying for the Problem G seems like I am stuck for this test case 1 1 4 1 3 2

t = int(input())
for i in range(t):
    n = int(input())
    lst = input().split()
    for j in range(n):
        lst[j] = int(lst[j])
    dic = {}
    def f(i, last):
        if(i>=len(lst)):
            if(last!=-1):
                return float("inf")
            else:
                return 0
        else:
            if((i, last) in dic):
                return dic[(i, last)]
            notblast = float("inf")
            blastleft = float("inf")
            blastright = float("inf")
            if(last!=-1):
                if(i-lst[i]+1<=last):
                    blastleft = 1 + f(i+1, -1)
                flag = False
                for j in range(i, min(i+lst[i]+1, len(lst))):
                    if(j-lst[j]+1<=last):
                        flag = True
                        break
                if(flag):
                    blastright = 2 + f(i+lst[i], -1)
                notblast = f(i+1, last)
            else:
                blastright = 1+f(i+lst[i], -1)
                notblast= f(i+1, i)
                blastleft = 1+f(i+1, -1)
            dic[(i, last)] = min(notblast, min(blastleft, blastright))
            return dic[(i, last)]
    print("Ans", f(0, -1))

Any Ideas why this gives the output as 2 the correct output is 3 though

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);
}

I tried using binary search to find l, r for problem D.

Approach -> - storing start and end indices for all intervals for which values of array are equal. - then for each query using upper bound to check if given interval exists inside any interval with all equal values to return -1, -1 otherwise returning the appropriate indices.

Here is the code:-

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

pair<int, int> find_indices_pair(vector<int>& a, vector<int>& start_indices, vector<int>& end_indices, int n, int l, int r) {
    pair<int, int> target_indices_pair;
    if((start_indices.size() == 0) || (r <= start_indices[0]) || (l >= end_indices[end_indices.size() - 1])) {
        target_indices_pair.first = l;
        target_indices_pair.second = l + 1;
        return target_indices_pair;
    }

    auto itr = upper_bound(start_indices.begin(), start_indices.end(), l);
    itr--;

    int req_index = itr - start_indices.begin();

    if(l >= end_indices[req_index]) {
        target_indices_pair.first = l;
        target_indices_pair.second = l + 1;
        return target_indices_pair;
    } else if(end_indices[req_index] >= r) {
        target_indices_pair.first = -1;
        target_indices_pair.second = -1;
        return target_indices_pair;
    } else if(end_indices[req_index] < r) {
        target_indices_pair.first = end_indices[req_index];
        target_indices_pair.second = end_indices[req_index] + 1;
        return target_indices_pair;
    }

    target_indices_pair = {-1, -1};
    return target_indices_pair;
}

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

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

        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++) {
            cin >> a[i];
        }

        vector<int> start_indices, end_indices;
        
        int st = 1;
        while(st <= n) {
            int ed = st + 1;
            if(a[st] != a[ed]) {
                st++; continue;
            }
            while(ed <= n) {
                if(a[st] != a[ed]) {
                    start_indices.push_back(st);
                    end_indices.push_back(ed - 1);
                    st = ed;
                    break;
                }
                ed++;
                if(ed == (n + 1)) {
                    start_indices.push_back(st);
                    end_indices.push_back(n);
                    st = n + 1;
                    break;
                }
            }
        }

        int q;
        cin >> q;

        while(q--) {
            int l, r;
            cin >> l >> r;

            pair<int, int> res = find_indices_pair(a, start_indices, end_indices, n, l, r);
            cout << res.first << " " << res.second << "\n";
        }
        cout << "\n";
    }
    return 0;
}

To me issue seems to be where i am creating start_indices and end_indices vectors. If anyone can help it would be great. Thanks.

problem E different solution with explanation https://mirror.codeforces.com/contest/1927/submission/248029334

My Approach for problem D using the Binary Search and storing the diff points of array earlier in a separate vector , it might be a childish solution but I liked my approach because its easy to understand.

Code:Have a look

مش فاهم حاجه يا مايك منك لله

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