Codeforces Round 950 (Div. 3) Editorial

#	User	Rating
1	Benq	3857
2	jiangly	3810
3	maroonrk	3534
4	tourist	3528
5	Kevin114514	3510
6	turmax	3411
7	Um_nik	3387
8	Radewoosh	3367
9	heuristica	3322
10	strapple	3317

#	User	Contrib.
1	Qingyu	157
2	maspy	150
3	Um_nik	145
4	Errichto	139
5	adamant	136
6	maroonrk	134
7	nik_exists	133
7	DNR	133
9	AmShZ	130
10	Dominater069	129

1980A - Problem Generator

Tutorial

Solution

def solve():
    n, m = map(int, input().split())
    a = input()
    ans = 0
    for ch in range(ord('A'), ord('H')):
        ans += max(0, m - a.count(chr(ch)))
    print(ans)
    
    
for _ in range(int(input())):
    solve()

1980B - Choosing Cubes

Idea: ibraevdmitriy Prepared by: ibraevdmitriy

Tutorial

Solution

def solve():
    n, f, k = map(int, input().split())
    f -= 1
    k -= 1
    a = list(map(int, input().split()))
    x = a[f]
    a.sort(reverse=True)
    if a[k] > x:
        print("NO")
    elif a[k] < x:
        print("YES")
    else:
        print("YES" if k == n - 1 or a[k + 1] < x else "MAYBE")
 
t = int(input())
for _ in range(t):
    solve()

1980C - Sofia and the Lost Operations

Idea: ibraevdmitriy Prepared by: Gornak40

Tutorial

Solution

#include <stdio.h>
#include <stdbool.h>
 
#define MAXN 200200
#define MAXM 200200
 
int n, m, k;
int arr[MAXN], brr[MAXN], drr[MAXM], buf[MAXN];
 
int cmp_i32(const void* pa, const void* pb) {
    return *(const int*)pa - *(const int*)pb;
}
 
void build() {
    k = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] != brr[i])
            buf[k++] = brr[i];
    }
    qsort(buf, k, sizeof(*buf), cmp_i32);
}
 
bool check() {
    for (int i = 0; i < n; ++i)
        if (brr[i] == drr[m - 1])
            return true;
    return false;
}
 
bool solve() {
    if (!check()) return false;
    qsort(drr, m, sizeof(*drr), cmp_i32);
    int ib = 0, id = 0;
    while (ib < k && id < m) {
        if (buf[ib] == drr[id])
            ++ib, ++id;
        else if (buf[ib] < drr[id])
            return false;
        else ++id;
    }
    return ib == k;
}
 
int main() {
    int t; scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            scanf("%d", arr + i);
        for (int i = 0; i < n; ++i)
            scanf("%d", brr + i);
        scanf("%d", &m);
        for (int j = 0; j < m; ++j)
            scanf("%d", drr + j);
        build();
        if (solve()) printf("YES\n");
        else printf("NO\n");
    }
}

1980D - GCD-sequence

Idea: myav Prepared by: myav

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
 
bool good(vector<int>&b){
    int g = __gcd(b[0], b[1]);
    for(int i = 1; i < int(b.size()) - 1; i++){
        int cur_gcd = __gcd(b[i], b[i + 1]);
        if(g > cur_gcd) return false;
        g = cur_gcd;
    }
    return true;
}
 
bool solve(){
    int n;
    cin >> n;
    vector<int>a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
 
    int g = -1;
    int to_del = -1;
    for(int i = 0; i < n - 1; i++){
        int cur_gcd = __gcd(a[i], a[i + 1]);
        if(cur_gcd < g){
            to_del = i;
            break;
        }
        g = cur_gcd;
    }
    if(to_del == -1) return true;
    vector<int>b0 = a, b1 = a, b2 = a;
    if(to_del > 0) b0.erase(b0.begin() + to_del - 1);
    b1.erase(b1.begin() + to_del);
    if(to_del < n - 1) b2.erase(b2.begin() + to_del + 1);
    return good(b0) || good(b1) || good(b2);
}
 
int main(){
    int t;
    cin >> t;
    while(t--){
        cout << (solve() ? "YES" : "NO") << "\n";
    }
}

1980E - Permutation of Rows and Columns

Idea: ibraevdmitriy Prepared by: ibraevdmitriy

Tutorial

Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
 
vi read_ints(int n) {
    vi res(n);
    for (int i = 0; i < n; ++i) {
        cin >> res[i];
    }
    return res;
}
 
vvi read_matrix(int n, int m) {
    vvi res(n);
    for (int i = 0; i < n; ++i) {
        res[i] = read_ints(m);
    }
    return res;
}
 
void solve() {
    int n, m;
    cin >> n >> m;
    vvi a = read_matrix(n, m), b = read_matrix(n, m);
    int nm = n * m;
    vi pos1i(nm), pos2i(nm), pos1j(nm), pos2j(nm);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int x = a[i][j] - 1;
            int y = b[i][j] - 1;
            pos1i[x] = pos2i[y] = i;
            pos1j[x] = pos2j[y] = j;
        }
    }
    vector<set<int>> pi(nm), pj(nm);
    for (int x = 0; x < nm; ++x) {
        int i1 = pos1i[x], i2 = pos2i[x];
        int j1 = pos1j[x], j2 = pos2j[x];
        pi[i1].insert(i2);
        pj[j1].insert(j2);
    }
    for (int x = 0; x < nm; ++x) {
        if (pi[x].size() > 1 || pj[x].size() > 1) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}
 
int main() {
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        solve();
    }
    return 0;
}

1980F1 - Field Division (easy version)

Idea: MikeMirzayanov Prepared by: Vladosiya

Tutorial

Solution

#include <bits/stdc++.h>
 
#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
typedef long double ld;
typedef long long ll;
 
using namespace std;
 
mt19937 rnd(time(nullptr));
 
const ll inf = 1e9 + 1;
const ll M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
 
bool cmp(pair<int, int> &a, pair<int, int> &b){
    if(a.x != b.x) return a.x > b.x;
    return a.y < b.y;
}
 
void solve(int tc){
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int, int>> a(k);
    map<pair<int, int>, int> idx;
    for(int i = 0; i < k; ++i){
        cin >> a[i].x >> a[i].y;
        idx[a[i]] = i;
    }
    sort(all(a), cmp);
    vector<int> ans(k);
    int total = 0;
    int cur = m + 1;
    int last = n;
    for(auto e: a){
        if(cur > e.y) {
            ans[idx[e]] = 1;
            total += (cur - 1) * (last - e.x);
            cur = e.y;
            last = e.x;
        }
    }
    total += (cur - 1) * last;
    cout << total << "\n";
    for(int e: ans) cout << e << " ";
}
 
bool multi = true;
 
signed main() {
    int t = 1;
    if (multi)cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
        cout << "\n";
    }
    return 0;
}

1980F2 - Field Division (hard version)

Idea: MikeMirzayanov Prepared by: Vladosiya

Tutorial

Solution

#include <bits/stdc++.h>
 
#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
typedef long double ld;
typedef long long ll;
 
using namespace std;
 
mt19937 rnd(time(nullptr));
 
const ll inf = 1e9 + 1;
const ll M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
 
bool cmp(pair<int, int> &a, pair<int, int> &b){
    if(a.x != b.x) return a.x > b.x;
    return a.y < b.y;
}
 
void solve(int tc){
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int, int>> a(k);
    map<pair<int, int>, int> idx;
    for(int i = 0; i < k; ++i){
        cin >> a[i].x >> a[i].y;
        idx[a[i]] = i;
    }
    idx[{0, 0}] = k++;
    a.emplace_back(0, 0);
    sort(all(a), cmp);
    vector<int> ans(k);
    vector<int> total(k + 1), cur(k + 1, m + 1), last(k + 1, n);
    for(int i = 1; i <= k; ++i){
        auto e = a[i - 1];
        total[i] = total[i - 1];
        cur[i] = cur[i - 1];
        last[i] = last[i - 1];
        if(cur[i] > e.y) {
            ans[idx[e]] = 1;
            total[i] += (cur[i] - 1) * (last[i] - e.x);
            cur[i] = e.y;
            last[i] = e.x;
        }
    }
    cout << total[k] << "\n";
    for(int i = 1; i <= k; ++i){
        auto e = a[i - 1];
        if(ans[idx[e]] == 0)continue;
        int tot = total[i - 1];
        int cr = cur[i - 1];
        int lst = last[i - 1];
        for(int j = i + 1; j <= k; ++j){
            auto ee = a[j - 1];
            if(cr > ee.y){
                tot += (cr - 1) * (lst - ee.x);
                cr = ee.y;
                lst = ee.x;
            }
            if(ans[idx[ee]] == 1){
                ans[idx[e]] = tot - total[j];
                break;
            }
        }
    }
    ans.pop_back();
    for(int e: ans) cout << e << " ";
}
 
bool multi = true;
 
signed main() {
    int t = 1;
    if (multi)cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
        cout << "\n";
    }
    return 0;
}

1980G - Yasya and the Mysterious Tree

Idea: Gornak40 Prepared by: Gornak40

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
 
struct trie {
    int l, c;
    vector<array<int, 2>> node;
    vector<int> cnt;
    trie(int l, int max_members) : l(l), c(0), node((l + 2) * max_members + 3), cnt((l + 2) * max_members + 3) {}
    void add(int x) {
        int cur = 0;
        for (int i = l; i >= 0; --i) {
            bool has_bit = (1 << i) & x;
            if (!node[cur][has_bit]) {
                node[cur][has_bit] = ++c;
            }
            cur = node[cur][has_bit];
            ++cnt[cur];
        }
    }
    void remove(int x) {
        int cur = 0;
        for (int i = l; i >= 0; --i) {
            bool has_bit = (1 << i) & x;
            if (!node[cur][has_bit]) {
                node[cur][has_bit] = ++c;
            }
            cur = node[cur][has_bit];
            --cnt[cur];
        }
    }
    int find_max(int x) {
        int cur = 0, ans = 0;
        for (int i = l; i >= 0; --i) {
            bool has_bit = (1 << i) & x;
            if (node[cur][!has_bit] && cnt[node[cur][!has_bit]]) {
                ans += 1 << i;
                cur = node[cur][!has_bit];
            }
            else {
                cur = node[cur][has_bit];
            }
        }
        return ans;
    }
};
 
const int N = 2e5 + 2;
int x[N];
bitset<N> dp;
vector<array<int, 2>> e[N];
 
void dfs(int c, int p) {
    for (auto [i, w] : e[c]) {
        if (i == p) {
            continue;
        }
        dp[i] = !dp[c];
        x[i] = x[c] ^ w;
        dfs(i, c);
    }
}
 
void solve() {
    int n, m, gx = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        e[i].clear();
    }
    for (int i = 1, u, v, w; i < n; ++i) {
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    dfs(1, 0);
    vector<trie> t(2, trie(30, n));
    for (int i = 1; i <= n; ++i) {
        t[dp[i]].add(x[i]);
    }
    while (m--) {
        char c;
        cin >> c;
        if (c == '^') {
            int y;
            cin >> y;
            gx ^= y;
        }
        else {
            int a, b;
            cin >> a >> b;
            t[dp[a]].remove(x[a]);
            int same_group = t[dp[a]].find_max(x[a] ^ b);
            int diff_group = t[1 - dp[a]].find_max(x[a] ^ b ^ gx);
            t[dp[a]].add(x[a]);
            cout << max(same_group, diff_group) << "\n";
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

int n; cin>>n; int a[n],b[n]; read(a,n); read(b,n); int m; cin>>m; int d[m]; read(d,m); if(count(b,b+n,d[m-1])==0) no; map<int,int> diff; for(int i=0;i<m;i++) diff[d[i]]++; for(int i=0;i<n;i++) { if(a[i]!=b[i]) { if(diff[b[i]]==0) no; diff[b[i]]--; } } yes;

for(int i = 1; i <= k; ++i){ auto e = a[i - 1]; if(ans[idx[e]] == 0)continue; int tot = total[i - 1]; int cr = cur[i - 1]; int lst = last[i - 1]; for(int j = i + 1; j <= k; ++j){ auto ee = a[j - 1]; if(cr > ee.y){ tot += (cr - 1) * (lst - ee.x); cr = ee.y; lst = ee.x; } if(ans[idx[ee]] == 1){ ans[idx[e]] = tot - total[j]; break; } } }

Comments (67)

Show archived | Write comment?

Naman1213

2 years ago, hide # |

Why is system testing so slow these days?

→ Reply

ice3y

2 years ago, hide # ^ |

Because there are so many people participating in contests

anamnesis

← Rev. 2 →

I guess it's due to the horrible 150+ tests of problem C... Most solutions took ~500ms on each test, which means that everyone who passed problem C(a large amount!) will take ~75 seconds to be judged

Sometimes I wonder if it would be better to include anti-unordered data in the pretests. This might help avoid the pointless but time-consuming hack judging?

paramveer5404

-8

I guess they shouldn't add all the the hacks to the main test cases. The C problem has 150 test cases but most of them are for Unordered Map. They can try ignoring similar purposed hacks by categorizing them or something.

sumanth_Bobby

← Rev. 4 →

Unordered map is constant time right, why is that giving TLE

Is it because the constant is higher for the test case. Clarify if you can why this code gave TLE 263947136

Yeah so the average case of an unordered map is O(1) for accessing data, but due to collisions the worst case for accessing data is O(N), so the solution becomes O(N^2) instead of O(N). You can read this article- https://codeforces.me/blog/entry/62393

Thanks

b22aide058

How does one get to know that a test is for unordered map?

Most of these hacks use a pretty standard generator, it is designed/works in a way that it hacks all the solutions using some form of a hash table, be it an unordered map ,unordered set or a python dictionary.

Itssme_Ayush

C took 100 lines of code for me :(

Mukul9571

It could be done in 20 lines ig

_Runtime__Terror_

+12

Here is a much simpler solution for Problem C.

The last element of modification array has to be present in D. All the elements which are different in B from A have to be present in D as well to carry out the modification. Except for that any other element in D does not matter because you could be changing that element in A to an intermediate number but then you finally change it to what it is in B.

Sahil_hussain

E could be easily solved using set of sets: Solution Link

crescentp2003

bro we wrote literally the same code. :)

Ylandolsi

wait for the next div3 4 to participate again

← Rev. 3 →

-10

zenigata23

testcasesforces

Tom66

F is Mike's idea :O

But I think you can't avoid sort so the time complexity can't be $$$\mathcal O(n)$$$.

My sol for F:

Find all corners. Remove all corners and run the algorithm for a second time to get a second group of corners.

A fountain becomes a new corner (after one of the old corners is removed) if and only if:

it is among the second group of corners; and
it is covered by only one corner.

A corner $$$(u,v)$$$ covers the range {$$$(x,y)|x\in[1,u],y\in[v,m]$$$}.

A fountain becomes a new corner after removing the corner covers it.

It's easy to calculate change of area now.

264008397

(Why $$$\{$$$ -> $$${$$$)

rangerscowboys

Do you know why my code for F1 doesn't work?

264033779

You can't find corners correctly in this way.

Can you please elaborate on what you mean? Thanks!

Vladosiya

The most important thing was to explain that the part after sorting is linear. (and my memory so short that I forgot about sorting by the end of tutorial)

ali.h.deeb

Can any one help me to understand problem c.? And send solution easly

Aaryan1808

Our goal is to find whether, given a list of sequential operations, an array could be translated into other or not.

The only operations that matter here are when an element is changed between a[i] -> b[i]. We ensure all such operations (say, d_k) are actually present in d.

Since d is also sequential, for any successful transformation, all d_k must be present at the end of d. As for a simple solution, kindly refer one from _Runtime__Terror_ a bit above in this discussion.

Thanks.

Xiao_2710

dang,how much longerr would the system testing go.

ksauravyadav123

Can anyone tell me, in C, why dm must be present in b? I read the question 50 times, still didn't understood.

SpyrosAliv

since you have to apply all operations in the order they are given, then dm will always need to be applied last and there is no following operation that can replace it. Therefore it should appear in the final array

NotFound

YES NO forces

nassar

Can someone explain why my submission 263986368 on problem c got a tle but something like this 263962017 didn't?

sabharwaldevansh04

same, now i just read that unordered_map with weak hash fxns can cause collisions in testcases and end up in O(n^2), it was safe to use normal map in this problem

Both solutions which I've mentioned use Hashmap.

xfp_17

problem d, solution 1 — 263972949 failed system test (TLE), solution 2 — 264171599 passed all the tests, code — same in both letter by letter, only difference — solution 1 submitted on Python3 while solution 2 submitted on PyPy3, result — got a "-1" in place of a "+"

WaisKamal

Problem C solved in C, coincidence or intentional?

sobhit_raghav

Can someone explain why my submission 263980440 on problem C got TLE but this submission 264168646 didn't?

puspendra_09

count in multiset is briefly O(n)

The time complexity of the count() operation in a multiset in C++ is O(log(n) + k), where n is the size of the multiset and k is the number of occurrences of the element being counted. I think TLE occurs when there is a testcase where k is very large.

accord

Yes, so effectively it is O(n). Got hacked for the same reason T_T

expertaq

E can be done with Zobrist Hashing 264181127.

Demolisher_719

For problem E on the basis of the solution, at the end, after sorting both matrix A and B on the basis of rows as well as on the basis of columns, both should turn out to be equal then only our answer is YES. So to simplify my implementation i took the sum of each rows in A and in B in two vectors and finally after sorting checked if both come out to be same and i did same for the columns also, since the sum property should also satisfy since the numbers are unique but i am getting WA on test 2. Can anyone explain what's wrong with my given implementation. I am not able to think on which test case my implementation will fail. please help 264209981

unique numbers does not guarantee a unique sum. (1,4) snd (2,3) have the same sum value, it is bound to give you wrong answer.

Flyleap

When I submitted problem 3 in the contest it showed accepted but right now it is showing TLE on test 10. Can anyone please explain why does this happen ? It has happened with me once before. (I am new to codeforces, so i don't know about all the rules)

You got hacked. (your code failed system testing) This is probably because you used unordered_map or something in your code. See the note at the end on editorial for C

chief_27

Video Editorial for D

https://youtu.be/O2-wL5OXyYc

Behrad.

Resources to learn trie?

https://medium.com/basecs/trying-to-understand-tries-3ec6bede0014

This has a good explanation

Trie problems

thanks bro

Trustworthy

Can someone please tell me the mistakes in my solution to problem E (https://codeforces.me/contest/1980/submission/264239803)? I have used a simple sorting-based method.

kadamrohan0215

-9

In problem F2 why the following code isn't giving TLE? What is time complexity of the loop for given problem ?

The complexity is k^2 which obviously TLEs for k <= 2*10^5

That was accepted. But now I got it why. Because we are only checking points between corners the time complexity will be O(n).

xyw_6

Problem E is flexible and great mind!The Tuorial only introduce solved way.It's so upset>_<.Can Anyone explain that detailed the reason of way >_< ?

stoppppittttadiiii

you can check mine it is relatively easy i first checked row wise. there i made a map for every row after sorting it and then checked for every sorted row in b if it existed in the original map. If it doesnt exist then no() else we check further .similarly for columns https://codeforces.me/contest/1980/submission/264333535 .

DinhDucManhGoldIOI2021

Editorial code for C can also be hacked because qsort worst case is $$$O(n^2)$$$: https://codeforces.me/contest/1980/hacks/1033165

Code

// Hacking quicksort solutions during competitions
// Author: https://codeforces.me/profile/halyavin 

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

vector<int> anti_sort(size_t n) {
    vector<int> res(2 * n + 1);
    iota(res.begin(), res.end(), 0);
    for (size_t i = n; i-- > 0;) {
        swap(res[2 * i + 1], res[i + n]);
    }
    for (auto &x : res) x++;
    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    vector<int> gen = anti_sort(2e5 / 2 - 1);
    int n = gen.size();
    cout << "1\n" << n << '\n';
    for (int i = 0; i < n; i++) {
        cout << gen[i] << " \n"[i == n - 1];
    }
    for (int i = 0; i < n; i++) {
        cout << gen[i] << " \n"[i == n - 1];
    }
    cout << n << '\n';
    for (int i = 0; i < n; i++) {
        cout << gen[i] << " \n"[i == n - 1];
    }
}

Unexpected verdict means that one of the solutions marked on Polygon as Correct can't pass this test. Vladosiya Gornak40

khanhdungtrinh

I have no ideas why I got wrong answer on problem G: https://codeforces.me/contest/1980/submission/264341580. My solution is the same as editorial.

Sarthak3204

Can somebody explain why it doesn't give TLE? I tried fixing each using rowswap and colswap and checked in the end if both matrices are equal or not. Submission

forgot_past

I am calculating that same sum of row and columns present in the array B or not

https://codeforces.me/contest/1980/submission/264546235

I am unable to find where it is failing. Can you tell some test case where it fail.

I don't think sum is an ideal hashing method.

Read YES, expected NO.

Hope it helps:)

sangam2ishra

Can anyone help why my code for 1980G - Yasya and the Mysterious Tree is not working?

264619004

264609607

I am happy if any of the above two works.

yoshi_likes_e5

A O(nm) solution for E that uses xor hashes:

Submission

Son_of_Dijkstra

Did someone solve problem G using Centroid Decomposition?

dsogari

Editorial solution to problem F2 is $$$O(k \log k)$$$ in the general case, but degenerates to $$$O(k^2)$$$ in the worst case (i.e., when all fountains are corners). Here's a truly $$$O(k \log k)$$$ solution: https://codeforces.me/contest/1980/submission/267832408

__Waled

Editorial solution checks only the fountains between each two corners, and it never checks same fountain twice. In case of all fountains are corners then second loop immediately terminates (as the next fountain is corner). So, overall complexity is $$$O(K)$$$

That may be true, but we must not forget that the fountain locations are being sorted as a first step, and this takes at least $$$O(k \log k)$$$.

Oh yes, that's true. But I only mentioned the part which causes the complexity to be $$$O(K^2)$$$. But, The overall complexity of the whole code is obviously $$$O(K\log{K})$$$. And also small note, Sorting takes at most $$$O(K \log{K})$$$, not at least, as it indicates the worst complexity.

lequoctran181

22 months ago, hide # |

Well, problem C's hacks are extraordinary. Even the author's code gets Time Limit Exceeded on test 156.

KGB

20 months ago, hide # |

In problem C, will anyone explain why is it necessary to presence of dm in b? I mean if it is not present then we can assign it to some value which is already present then it will be overite?

indresh_0903

17 months ago, hide # |

Vladosiya's blog