Codeforces Round #1002 Editorial

#	User	Rating
1	jiangly	3898
2	tourist	3840
3	orzdevinwang	3706
4	ksun48	3691
5	jqdai0815	3682
6	ecnerwala	3525
7	gamegame	3477
8	Benq	3468
9	Ormlis	3381
10	maroonrk	3379

#	User	Contrib.
1	cry	167
2	-is-this-fft-	165
3	Dominater069	161
4	atcoder_official	160
5	Um_nik	159
6	djm03178	156
7	adamant	153
8	luogu_official	151
9	awoo	149
10	TheScrasse	146

Thank you for participating! We hope you enjoyed our problems

Author and developer is yunetive29

2059A - Milya and Two Arrays

Solution

Implementation

#include <bits/stdc++.h>
using namespace std;
 
int a[55],b[55];
 
void solve(){
    int n;cin>>n;
    set<int> sa,sb;
    for(int i=1;i<=n;i++)cin>>a[i],sa.insert(a[i]);
    for(int i=1;i<=n;i++)cin>>b[i],sb.insert(b[i]);
    if(sa.size()+sb.size()<4){
        cout<<"NO\n";
    }else{
        cout<<"YES\n";
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;cin>>t;
    while(t--){
        solve();
    }
 
    return 0;
}

2059B - Cost of the Array

Author and developer is yunetive29

Solution

Implementation

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n, k;
    cin >> n >> k;
    k /= 2;
    vector<int> a(n);
    for (auto &it: a) cin >> it;
    if (2 * k == n) {
        for (int i = 1; i < n; i += 2) {
            if (a[i] != (i + 1) / 2) {
                cout << (i + 1) / 2 << '\n';
                return;
            }
        }
        cout << k + 1 << '\n';
    } else {
        for (int i = 1; i <= n - 2 * k + 1; i++) {
            if (a[i] != 1) {
                cout << "1\n";
                return;
            }
        }
        cout << "2\n";
    }
}
 
int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

2059C - Customer Service

Author and developer is yunetive29

Solution

Implementation

#include <bits/stdc++.h>
using namespace std;
 
const int N=305;
 
int a[N][N],suff[N];
 
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        suff[i]=0;
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=n;j>=1;j--){
            if(a[i][j]!=1)break;
            suff[i]++;
        }
    }
    multiset<int> s;
    for(int i=1;i<=n;i++){
        s.insert(suff[i]);
    }
    int ans=1;
    while(!s.empty()){
        int cur=*s.begin();
        if(cur>=ans){
            ans++;
        }
        s.extract(cur);
    }
    cout<<min(ans,n)<<'\n';
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;cin>>t;
    while(t--){
        solve();
    }
 
    return 0;
}

2059D - Graph and Graph

Author and developer is yunetive29

Solution

Implementation

#include "bits/stdc++.h"
using namespace std;
 
#define int long long
#define eb emplace_back
 
const int INF = 1e18;
 
void solve() {
    int n, s1, s2;
    cin >> n >> s1 >> s2;
    s1--, s2--;
    vector<vector<int>> g1(n), g2(n);
    vector<bool> good(n);
    set<pair<int, int>> edges;
    int m1;
    cin >> m1;
    for (int i = 0; i < m1; i++) {
        int v, u;
        cin >> v >> u;
        v--, u--;
        if (v > u)
            swap(v, u);
        edges.insert({v, u});
        g1[v].eb(u);
        g1[u].eb(v);
    }
    int m2;
    cin >> m2;
    for (int i = 0; i < m2; i++) {
        int v, u;
        cin >> v >> u;
        v--, u--;
        if (v > u)
            swap(v, u);
        if (edges.find({v, u}) != edges.end())
            good[v] = true, good[u] = true;
        g2[v].eb(u);
        g2[u].eb(v);
    }
    vector<vector<int>> d(n, vector<int> (n, INF));
    d[s1][s2] = 0;
    set<pair<int, pair<int, int>>> st;
    st.insert({0, {s1, s2}});
    while (!st.empty()) {
        auto [v, u] = st.begin()->second;
        st.erase(st.begin());
        for (auto to1 : g1[v]) {
            for (auto to2 : g2[u]) {
                int w = abs(to1 - to2);
                if (d[to1][to2] > d[v][u] + w) {
                    st.erase({d[to1][to2], {to1, to2}});
                    d[to1][to2] = d[v][u] + w;
                    st.insert({d[to1][to2], {to1, to2}});
                }
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < n; i++) {
        if (!good[i])
            continue;
        ans = min(ans, d[i][i]);
    }
    if (ans == INF)
        ans = -1;
    cout << ans << '\n';
}
 
signed main() {
    //cout << fixed << setprecision(5);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    //cin >> G;
    while (T--)
        solve();
    return 0;
}

2059E1 - Stop Gaming (Easy Version)

Author shfs and developer is yunetive29

Hint 1

Hint 2

Hint 3

Solution

Implementation

#include "bits/stdc++.h"
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n * m + 1), b(n * m + 1);
    vector<deque<int>> mat(n + 1, deque<int> (m));
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            int ind = j + 1 + (i - 1) * m;
            mat[i][j] = ind;
            cin >> a[ind];
        }
    }
    for (int i = 1; i <= n * m; i++)
        cin >> b[i];
    map<int, int> mp;
    for (int i = 1; i <= n * m; i++)
        mp[b[i]] = i;
    vector<int> s(n * m + 1), pos(n * m + 1, -1);
    for (int i = 1; i <= n * m; i++) {
        if (mp.find(a[i]) != mp.end())
            pos[i] = mp[a[i]];
        else
            break;
    }
    pos[0] = 0;
    int skipped = 0, pref = 0;
    bool prev = true;
    for (int i = 1; i <= n * m; i++) {
        if (pos[i - 1] > pos[i])
            break;
        int d = pos[i] - pos[i - 1] - 1;
        if (prev)
            skipped += d;
        else if (d > 0)
            break;
        if (skipped >= m - 1)
            prev = true;
        else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0)
            prev = true;
        else
            prev = false;
        if (prev)
            pref = i;
    }
    cout << n * m - pref << '\n';
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

2059E2 - Stop Gaming (Hard Version)

Author shfs and developer is yunetive29

Solution

Implementation

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

#define eb emplace_back
#define int long long
#define all(x) x.begin(), x.end()
#define fi first
#define se second

const int INF = 1e9 + 1000;
 
struct segtree {
    vector<pair<int, int>> tree;
    vector<int> ass;
    int size = 1;
 
    void init(vector<int> &a) {
        while (a.size() >= size) {
            size <<= 1;
        }
        tree.assign(2 * size, {});
        ass.assign(2 * size, 0);
        build(0, 0, size, a);
    }
 
    void build(int x, int lx, int rx, vector<int> &a) {
        if (rx - lx == 1) {
            tree[x].se = lx;
            if (lx < a.size()) {
                tree[x].fi = a[lx];
            } else {
                tree[x].fi = INF;
            }
            return;
        }
        int m = (lx + rx) / 2;
        build(2 * x + 1, lx, m, a);
        build(2 * x + 2, m, rx, a);
        tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
    }
 
    void push(int x, int lx, int rx) {
        tree[x].fi += ass[x];
        if (rx - lx == 1) {
            ass[x] = 0;
            return;
        }
        ass[2 * x + 1] += ass[x];
        ass[2 * x + 2] += ass[x];
        ass[x] = 0;
    }
 
    void update(int l, int r, int val, int x, int lx, int rx) {
        push(x, lx,  rx);
        if (l <= lx && rx <= r) {
            ass[x] += val;
            push(x, lx, rx);
            return;
        }
        if (rx <= l || r <= lx) {
            return;
        }
        int m = (lx + rx) / 2;
        update(l, r, val, 2 * x + 1, lx, m);
        update(l, r, val, 2 * x + 2, m, rx);
        tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
    }
 
    void update(int l, int r, int val) {
        update(l, r + 1, val, 0, 0, size);
    }
 
    int req(int x, int lx, int rx) {
        push(x, lx, rx);
        if (rx - lx == 1) {
            return tree[x].se;
        }
        int m = (lx + rx) / 2;
        push(2 * x + 1, lx, m);
        push(2 * x + 2, m, rx);
        if (tree[2 * x + 2].fi == 0) {
            return req(2 * x + 2, m, rx);
        } else {
            return req(2 * x + 1, lx, m);
        }
    }
 
    int req() {
        return req(0, 0, size);
    }
};
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n * m + 1), b(n * m + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            int ind = j + 1 + (i - 1) * m;
            cin >> a[ind];
        }
    }
    for (int i = 1; i <= n * m; i++)
        cin >> b[i];
    map<int, int> mp;
    for (int i = 1; i <= n * m; i++)
        mp[b[i]] = i;
    vector<int> s(n * m + 1), pos(n * m + 1, -1);
    for (int i = 1; i <= n * m; i++) {
        if (mp.find(a[i]) != mp.end())
            pos[i] = mp[a[i]];
        else
            break;
    }
    pos[0] = 0;
    int skipped = 0, pref = 0;
    bool prev = true;
    for (int i = 1; i <= n * m; i++) {
        if (pos[i - 1] > pos[i])
            break;
        int d = pos[i] - pos[i - 1] - 1;
        if (prev)
            skipped += d;
        else if (d > 0)
            break;
        if (skipped >= m - 1)
            prev = true;
        else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0)
            prev = true;
        else
            prev = false;
        if (prev)
            pref = i;
    }
    for (int i = 1; i <= pref; i++) {
        s[i - 1] = pos[i] - pos[i - 1] - 1;
    }
    s[pref] = n * m - pos[pref];
 
    vector<pair<int, int>> ans;
 
    int res = 0;
    for (int i = 0; i <= n * m; i++) {
        res += s[i];
    }
    vector<int> ost(pref + 1);
    for (int i = 1; i <= pref; i++) {
        ost[i] = (m - i % m) % m;
    }
    for (int i = 0; i <= pref; i++) {
        if (s[i] == 0) {
            ost[i] = INF;
        }
    }
    vector<int> gol(pref + 1);
    gol[0] = 1;
    for (int i = 1; i <= pref; i++) {
        gol[i] = (i + m - 1) / m + 1;
    }
 
    segtree tree;
 
    tree.init(ost);
 
    for (int step = 0; step < res; step++) {
        int chel = tree.req();
        ans.eb(gol[chel], b[pos[chel] + s[chel]]);
        tree.update(chel + 1, pref, -1);
        s[chel]--;
        if (s[chel] == 0) {
            tree.update(chel, chel, INF);
        }
    }
 
    cout << ans.size() << '\n';
    for (auto [i, col] : ans) {
        cout << i << " " << col << '\n';
    }
}
 
signed main() {
    //cout << fixed << setprecision(5);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    //cin >> G;
    while (T--)
        solve();
    return 0;
}

Comments (48)

Write comment?

yunetive29

5 hours ago, # |

Auto comment: topic has been updated by yunetive29 (previous revision, new revision, compare).

→ Reply

case3

← Rev. 2 →

-7

Wait your released the editorial with code 30 minutes before round ended? That's absurd!?

EDIT: My apologies. I had a gap in my knowledge.

DenimFlame12

5 hours ago, # ^ |

No, that was the time when he started drafting or copy pasted the draft into CF blog.

mariza_CY

That's the time the post was created, not posted

Abito

-6

Skill Issue. I only solved AD lmao

Nyemot

4 hours ago, # ^ |

creative issue? Codeforces usually have some creative problem.

First time i joined Codeforces also struggled with these "creative problem"s

If you mean that I'm creative to solve AD then no because D is standard asf

I mean B,C require some creativity or just familiarity with codeforces problem.

Yeah D is standard, just scary at first read.

stakudog

Hey can you tell me how is it standard?

Are there any similar problems or blogs on this approach?

Cause it uses djikstra algorithm as the main solution.

.-__-.

Just because a solution uses an algorithm doesn't mean the problem is standard. With that said problem D is pretty standard.

3 hours ago, # ^ |

My argument would be djikstra appear frequently in many contests.
I'll also add the solution only differs a little bit from a well known algorithm. bonus points if it doesn't require modification.

I am not sure but I mean it's just a no brainer I guess I can't use the right words

I guess I got it, it's easy.

the Djikstra with a 2D state was just a bit confusing to visualize to me.

Surge226

Any suggestions on how to solve or atleast approach those creative problems?

Try solving easier cases first, usually starts with n=1 after you're comfortable then generalize the solution. If you check my submission you can see how i worked from easier case, though it's not a beautiful submission. 304090629
Try learning some quirks of certain problem, like "n is even", bitwise XOR/AND/OR, MEX. They usually share some similarity in approach.
Practice alot of codeforces problem, if you plan to stay.

Thanks for your suggestions. I cannot understand your quirks point. Do you mean to say that if "n is even", then we can use bitwise XOR/AND/OR, MEX somehow or anything else?

no, many of the creative problem usually have some constraint that may contain hint to solving it.

if n is even:

usually i try to divide the array into 2 parts

or maybe in different question, divide the array into n/2 2-sized sub-array

FZANOTFOUND

Spend 1 hours to find a case of ans 3 in B :(

Seriously_Its_Sameer

how did you manage to go from 2100 to 1600! concerning.. any advice?

I used to cheat and I can't anymore

jobin491

2 hours ago, # ^ |

as honest as bro could get

GoogleMilegiKyaIsse

I personally felt problem B and C were nice! (even though problem B ruined my contest lol) Simple ideas, yet tricky!

Zhangyl

← Rev. 3 →

304115975，304141983，304098763 Can someone hack them

naivedyam

I am quite shocked how my B passed the system tests. I was checking for min max in a range but forgot to sort the vector d. I realised this mid contest and was pretty sure it would fail the system tests because I myself can think of countless test cases to hack it. Or is it because of some mathematical property I am missing? Could someone explain?

monaxia

4 hours ago, # |

Is it just me or B is unexpectedly hard today?

Baby_Bird

I found it very tricky to find an error in my solution. The problem isn't hard, but you need to carefully check your output.

Top12

good contest , bad contest

Why do people think it was a bad contest? Because D was GPT-able? That is not the problemsetters' fault...

antiMathforces

Why do you think it was a good contest? because you performed well?

I didn't perform well. A was acceptable, B was also acceptable, C was good, and D was a bit standard but I enjoyed arriving at the conclusion. E1 was solved by a hundred people and E2 was unsolvable for Div. 2. What exactly is bad about this round?

I think it's because b is harder than c to many people.

And also too few question? (makes my hand sweaty)

adiroy2

Was stuck in reading B for a long time, Couldnt understand what

""such that each element of the array a belongs to exactly one subarray.""

meant Back to Pupil :(

Rushdi

my E1 Solution is much simpler than Tutorial : 304156702

just track the numbers you must push in next array by using queue

I like your template.

Unlike some other template that has 1000 lines just for unused code.

Also smart solution.

esh_war2

34 minutes ago, # ^ |

Check out Dominater069 , he also writes with minimal code.

For B, I spent 1hour to find a case of which the ans is 3 to hack my wa submisson then I reallized it's impossible :( (I have no enough time to finish C)

shorya1835

Just found out my mistake in E1 :(

theriseofahero

I wanna become an expert. I have come close quite a few times but missed the mark by inches. Please suggest some resources so that I'll be able to do Codeforces Div 2 Problem D in upcoming contests.

Thanks in advance!!

Drakkon

Solve a lot of 1700-2000 problems, it's the only way. Use the filter in codeforces.

saiful_islam_bk

3 hours ago, # |

Everyone enjoyed the contest, but i am not. My contest was very bad. I have been feeling very bad for two days. :((

gabriel88766

When I saw D and thought about Dijkstra with $$$V = E = 1000000$$$, I thought about doing some kind of "BFS0/1" instead. Then I guessed the distance couldn't be greater than $$$n\times n$$$ (guessed any reachable vertex can be reached in less than n steps, now I think it's actually 2n steps.) and did a BFS with $$$(n+1)\times (n+1) + 1$$$ queues. Hack here if it's wrong -> 304106582

Anyway, $$$O(n\ log\ n)$$$ for $$$n = 1000000$$$ and TL = 2s is the new standard?