Codeforces Round #1002 Editorial

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 (89)

Show archived | Write comment?

yunetive29

15 months ago, hide # |

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

→ Reply

case3

← Rev. 2 →

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

15 months ago, hide # ^ |

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

-9

Skill Issue. I only solved AD lmao

Nyemot

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

+10

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.

.-__-.

+13

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

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?

+19

I used to cheat and I can't anymore

jobin491

as honest as bro could get

huge respect for honesty!

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_mishra

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?

Akarsh09

B doesn't require sorting. You have to find subarrays and sorting will ruin the work.

Ahh no my approach was kinda different. As you can see I have already sorted some of it if that were the case that should have WAed too

monaxia

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.

SIXIANG

Me too.QAQ. I take much more time than solving D to solve B QAQ.It's really tricky for me.

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?

Alliy666

Because both E1 and E2 are too difficult, D is *1847,E1 is *2565, and the difficulty span is too large. In a good div2, E is *2100, F is *2500 is more appropriate.

djm03178

+26

I tested this round a while ago and I am surprised that they went with the current score distribution. I told them that B was hard, D was super easy and E1 was too hard, and the number of solves exactly shows that too. I'm not sure if other testers thought the other way, but $$$2000 - 1500$$$ for D and E1 is quite unreasonable, even though for some reason people usually don't like to give enough score to a subtask.

Yes,you are right.

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

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

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

Check out Dominater069 , he also writes with minimal code.

ice_king

could you please explain your solution in more details?

Yifanz

8 months ago, hide # ^ |

There's this queue solution I've been looking for!

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.

14 months ago, hide # ^ |

Became an expert today. Thanks Drakkon Any suggestions to become CM.

Congratulations Bro !! What you need now is consistency in solving a,b,c fast and also solve d if it's not too hard. To do that you will need to solve alot of 1700-2000 problems + virtual contests in order to be faster.

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?

marseille

A much simpler implementation of E1 304178286

phreshboyswag

Would you mind explaining your solution?

Explain please

76harshit_codes81

can anyone explain the last sample testcase of E1.

stillgrowing

12 months ago, hide # ^ |

the sequence of steps required to change the array is mentioned in E2.

Mohamed_Saad62

can someone explain how the answer can be 3 for this test (for c problem):
4
4 2 2 17
1 9 3 1
5 5 5 11
1 2 1 1

3 -> 4 -> 2 -> 1

then x array we get would be [0, 2, 9, 12] and the mex should be 1 ...so what I am missing ?

NiGhT-h-MaRe

The array would look like [25, 1, 0,2] . I will stand on the queue for the 3rd then at last For 2nd at before last and for 2nd as you can sss

asns

I had the same question and thought about it for over 30 minutes, but the conclusion was absurd. Each hour is vertical, not horizontal. In other words, the set of people who come in the first time is not '4 2 2 17', which is the first horizontal line, but '4 1 5 1'. FYI, I didn't have enough time for this... :(

Yes I read the input in wrong way now it make sense

NotAnArtist

If we clear any queue at index i then the result for that queue would be sum from i+1 to n for that queue. Now find out the maximum you can obtain from each queue as by induction or simple observation you can see that if you can obtain say 4 from a queue then it can also be used to provide any value <4. Just push these values in a vector and sort them , if some element is missing and there is a number greater than that in the vector , it can be used to fill in the vacancy to increase the mex.

For you case , the breakdown is as follows: Queue 1 can contribute max 0. Queue 2 can contribute max 1. Queue 3 can contribute max 0. Queue 4 can contribute max 2. Hence the vector would be 0,0,1,2 , the mex for which is 3 If for eg Q2 could also contribute max 2 , then we could use it as a 1 to fill in the gap.

I think the confusion come from the way I read the input but thanks for your explaniation

LMAO

ylh_

I made the same mistake with the matrix direction. I spent an hour thinking, then came to the comment section for the answer.

vinayakverma290605

i was thinking of trying e1 before D because of the score distribution,, glad i looked at the number of submissions ,,

parth_sak12

In D. Graph and Graph
tutorial: "the number of edges in the new state graph will not exceed m1.m2"
I must be stupid, but please correct me.

The number of edges (E) in the new state graph will be of order 10^3(m1)*10^3(m2) i.e 10^6
The number of vertices (V) will be order n^2((10^3)^2) i.e 10^6.... though we may not visit all vertices here.

But the time complexity of Dijkstra with binary heap is
O(V*(Extract_Min) + E*Decrease_Key) = O(V logV + E log(V))
which here results to (10^6 * log2(10^6) + 10^6 * log2(10^6)) = 2*(10^6 * 20) = 4*10^7

Questions ?
- What am I missing here ?
- How many operations are allowed in 1sec ? if am not wrong is 10^6 simple operations(not %, /)
- How do we calculate time complexity here?
- How many operations are performed here ?

henryyyh

10^8 simple operations are allowed in 1sec.

steamyfish

for the first problem, a = [2,2,3] => set of a has {2,3}, size=2; b= [2,2,3] => set of b has {2,3}, size=2; so total size >=4. But the answer is 'NO' only 2+2,2+3 or 2+2, 3+3 are possible. Am I wrong or the solution is wrong

Pi213

premise is a & b are "good" arrays. your a and b arent "good". 3 must occur at least twice

jkulanko

Is there a name for the technique in D? I've never seen it before but it's very cool.

It's Dijkstra Algorithm

I know that, I meant the way that the states are tracked in the 2d array

akane646

I also wanted to know, the dijsktra on 2d states track also caught me off guard. (I will never thought of that on a whim)

If I was trying to crack D in live contest, I'd bet it on BFS 0/1 state with max steps = 2n.

DCSNMGPSSIK

In graph theory, when you define a graph, a "vertex" is just not a simple thing with 1 number. A "vertex" in graph can also be a state, such as if you playing chess, each vertex is a chess board and if you play a move, so the old chess board can connect to a new chess board, etc.

So in this problem, you should consider that a "vertex" is a pair of numbers <u1, u2>. If u1 is adjacent to v1, u2 is adjacent to v2, so "vertex" <u1, u2> is connect to <v1, v2> with cost |v1 — v2|

thehvd3

Can anyone help to give the countercase or find the testcase on which my submission for E1 is failing.

My-submission

whitedevil898

can anybody explain why i am getting a Tle for this submission of mine 304236998 for the problem D.

you need to flatten the 2d states into 1d states to optimize the heap complexity.

yeetholmes619

shfs hey I think my submission for E1 seems to work when B doesn't have distinct elements either.

304147683

I tried the following case

and it returns 5 as expected.

I would stress test to make sure I'm right but I'm not sure how would a brute force look like. can you share the brute force you used to test your solution in E1?

Im_Piyush

B is Constructive. It was not able to solve it but it was intresting idea when I saw the editoral

thejamba

For problem B, in the fourth example, the answer is 1

5 4 1 1 1000000000 2 2

I think this is wrong: 4 subarrays [1],[1],[1000000000], [2,2] b = [1, 2, 2, 0]

Why is the answer not 3?

Roll_no_68

Read the last line of question "Determine the minimum cost of the array b"

an1ket_62

Can anyone uphack my solution for B. https://mirror.codeforces.com/contest/2059/submission/304209911

TC :

1 2 2 2 2 3 3

kingpin911

kinda suprised D has a lot of solves. Is the idea obvious or pretty standard

mani100011

The multiplication graph is a well known idea. also, o3 mini can solve it easily

nguyenquocthao00

13 months ago, hide # |

E2 solution only using stack
https://mirror.codeforces.com/contest/2059/submission/310217564

TheArcticWolf

For D, I did something like :310452937

Each state in the PQ is (sum, s1, s2, zero_cnt), tracking the total cost, token positions in both graphs, and how many times we got consecutive zero-cost move. If zero_cnt == 2, we're done and print sum. Otherwise, keep expanding (u1, u2) pairs and push new states.

Also used visited maps, if it runs too long, i stop it and return -1.

Anyway, still not sure why no tle. Cool question though