Codeforces Round #935 Editorial

1945A - Setting up Camp

Tutorial

Solution

#include <iostream>

using namespace std;
using ll = long long;

void solve() {
    ll single, poly, uni;
    cin >> single >> poly >> uni;
    ll needPoly = (3 - poly % 3) % 3;
    if (poly > 0 && needPoly > uni) {
        cout << "-1\n";
        return;
    }

    uni -= needPoly;
    poly += needPoly;

    ll mn = single + uni / 3 + (uni % 3 + 1) / 2 + poly / 3;
    cout << mn << '\n';
}

int32_t main() {
    ll T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

1945B - Fireworks

Idea: NToneE, Gadget

Tutorial

Solution

t = int(input())
for qi in range(t):
    a, b, m = [int(x) for x in  input().split()]
    ans = m // a + m // b + 2
    print(ans)

1945C - Left and Right Houses

Idea: Gadget, NToneE

Tutorial

Solution

for case in range(int(input())):
    n = int(input())
    a = input()
    suf_cnt = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suf_cnt[i] = suf_cnt[i + 1] + (a[i] == '1')
    pref_cnt = 0
     
    opt_ans = -1
    opt_dist = n * 2
    threshold = (n + 1) // 2
     
    for i in range(n + 1):
        if pref_cnt >= (i + 1) // 2 and suf_cnt[i] >= (n - i + 1) // 2 and abs(n - 2 * i) < opt_dist:
            opt_dist = abs(n - 2 * i)
            opt_ans = i
        if i != n:
            pref_cnt += (a[i] == '0')
     
    print(opt_ans)

1945D - Seraphim the Owl

Idea: Kirill_Maglysh

Tutorial

Solution

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

void solve() {
    ll n, k;
    cin >> n >> k;
    vector<ll> A(n);
    for (auto& item : A) {
        cin >> item;
    }
    reverse(A.begin(), A.end());

    vector<ll> B(n);
    for (auto& item : B) {
        cin >> item;
    }
    reverse(B.begin(), B.end());

    ll bSum = 0;
    ll pref = 0;
    for (ll i = 0; i < n - k; ++i) {
        if (A[i] < B[i]) {
            pref += bSum;
            pref += A[i];
            bSum = 0;
        } else {
            bSum += B[i];
        }
    }

    ll res = 1e18;
    for (ll i = n - k; i < n; ++i) {
        res = min(res, pref + bSum + A[i]);
        bSum += B[i];
    }

    cout << res << '\n';
}

int32_t main() {
    ll testN;
    cin >> testN;
    while (testN--) {
        solve();
    }
    return 0;
}

1945E - Binary Search

Idea: Kirill_Maglysh

Tutorial

Solution

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> src(n);
    int P = 0;
    for (int i = 0; i < n; ++i) {
        cin >> src[i];
        if (src[i] == x) {
            P = i;
        }
    }

    int l = 0;
    int r = n;
    while (r - l > 1) {
        int m = (l + r) / 2;

        if (src[m] <= x) {
            l = m;
        } else {
            r = m;
        }
    }

    cout << "1\n";
    cout << P + 1 << ' ' << l + 1 << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

1945F - Kirill and Mushrooms

Idea: Kirill_Maglysh

Tutorial

Solution

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
using ll = long long;

void solve() {
    ll n;
    cin >> n;
    vector<ll> src(n);
    vector<pair<ll, ll>> can(n);
    for (ll i = 0; i < n; ++i) {
        cin >> src[i];
        can[i] = {src[i], i};
    }

    vector<ll> ord(n);
    for (auto& item : ord) {
        cin >> item;
        --item;
    }

    sort(can.rbegin(), can.rend());
    ll best = can[0].first;
    ll take = 1;

    ll cur;
    ll P = 1;
    vector<bool> burn(n);
    vector<bool> used(n);
    used[can[0].second] = true;
    for (ll k = 0; k + 1 < n && P < n; ++k) {
        while (P < n && burn[can[P].second]) {
            ++P;
        }

        if (P == n) {
            break;
        }

        used[can[P].second] = true;
        cur = can[P].first;
        ++P;

        burn[ord[k]] = true;
        if (used[ord[k]]) {
            while (P < n && burn[can[P].second]) {
                ++P;
            }

            if (P == n) {
                break;
            }

            used[can[P].second] = true;
            cur = can[P].first;
            ++P;
        }

        if (best < cur * (k + 2)) {
            take = k + 2;
            best = cur * (k + 2);
        }
    }

    cout << best << ' ' << take << '\n';
}

int32_t main() {
    ll testN;
    cin >> testN;
    while (testN--) {
        solve();
    }
    return 0;
}

1945G - Cook and Porridge

Idea: Kirill_Maglysh

Tutorial

Solution

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
using ll = long long;

const int MAX_N = 2e5;
const int MAX_D = 3e5;

struct Student {
    int k;
    int s;
    int tin = 0;

    bool operator<(const Student& other) const {
        if (k == other.k) {
            if (tin == other.tin) {
                return s > other.s;
            }
            return tin > other.tin;
        }
        return k < other.k;
    }
};

int n, D, x;
Student qu1[MAX_N];
int sufMax[MAX_N];
vector<Student> eat[MAX_D];

int check() {
    int origPos = 0;
    priority_queue<Student> qu2;
    for (int i = 0; i < D && origPos < n; ++i) {
        if (qu2.empty() || qu2.top().k <= sufMax[origPos]) {
            ll nxtTime = ll(i) + ll(x) * ll(qu1[origPos].s);
            if (nxtTime < D) {
                eat[nxtTime].push_back(qu1[origPos]);
            }

            ++origPos;
            if (origPos == n) {
                for (int tm = 0; tm < D; ++tm) {
                    eat[tm].clear();
                }

                return i + 1;
            }
        } else {
            ll nxtTime = ll(i) + ll(x) * ll(qu2.top().s);
            if (nxtTime < D) {
                eat[nxtTime].push_back(qu2.top());
            }
            qu2.pop();
        }

        for (const auto& student : eat[i]) {
            qu2.push({student.k, student.s, i});
        }
    }

    for (int i = 0; i < D; ++i) {
        eat[i].clear();
    }

    return -1;
}

void solve() {
    cin >> n >> D;
    x = 1;
    for (int i = 0; i < n; ++i) {
        cin >> qu1[i].k >> qu1[i].s;
    }

    sufMax[n - 1] = qu1[n - 1].k;
    for (int i = n - 2; i >= 0; --i) {
        sufMax[i] = max(qu1[i].k, sufMax[i + 1]);
    }

    cout << check() << '\n';
}

int32_t main() {
    ll testN;
    cin >> testN;
    while (testN--) {
        solve();
    }
    return 0;
}

1945H - GCD is Greater

Idea: Kirill_Maglysh

Tutorial

Solution

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int BITS = 20;
const int MAX_N = 4e5 + 10;
int n;
int x;

int src[MAX_N];

void coutYES(int fId, int sId) {
    cout << "YES\n";
    cout << "2 " << src[fId] << ' ' << src[sId] << '\n';
    cout << n - 2 << ' ';
    for (int i = 0; i < n; i++) {
        if (i == fId || i == sId) {
            continue;
        }
        cout << src[i] << ' ';
    }
    cout << '\n';
}

void solve() {
    cin >> n >> x;
    vector<int> bitCnt[BITS];

    int maxA = 1;
    for (int i = 0; i < n; i++) {
        cin >> src[i];
        maxA = max(maxA, src[i] + 1);
        for (int bit = 0; bit < BITS; bit++) {
            if ((1 << bit) & src[i]) {
                continue;
            }

            bitCnt[bit].push_back(i);
        }
    }

    bool incr[n];
    int cnt[maxA];
    int divBy[maxA];
    for (int i = 0; i < maxA; ++i) {
        cnt[i] = 0;
        divBy[i] = 0;
    }

    int pref[n];
    int suf[n];
    for (int i = 0; i < n; i++) {
        incr[i] = false;
        pref[i] = src[i];
        if (i) {
            pref[i] = pref[i - 1] & src[i];
        }
    }

    for (int i = n - 2; i >= 0; i--) {
        suf[n - 1] = src[n - 1];
        if (i < n - 1) {
            suf[i] = suf[i + 1] & src[i];
        }
    }

    for (const auto& item : bitCnt) {
        if (item.size() <= 2) {
            for (const int& id : item) {
                incr[id] = true;
                int myAnd = -1;
                for (int j = id + 1; j < n; j++) {
                    int curAND = (1 << BITS) - 1;
                    if (j + 1 < n) curAND &= suf[j + 1];
                    if (id - 1 >= 0) curAND &= pref[id - 1];
                    if (myAnd != -1) curAND &= myAnd;

                    if (curAND + x < __gcd(src[id], src[j])) {
                        coutYES(id, j);
                        return;
                    }

                    if (myAnd == -1) {
                        myAnd = src[j];
                    } else {
                        myAnd &= src[j];
                    }
                }

                myAnd = -1;
                for (int j = id - 1; j >= 0; j--) {
                    int curAND = (1 << BITS) - 1;

                    if (j - 1 >= 0) curAND &= pref[j - 1];
                    if (id + 1 < n) curAND &= suf[id + 1];
                    if (myAnd != -1) curAND &= myAnd;

                    if (curAND + x < __gcd(src[id], src[j])) {
                        coutYES(id, j);
                        return;
                    }

                    if (myAnd == -1) {
                        myAnd = src[j];
                    } else {
                        myAnd &= src[j];
                    }
                }
            }
        }
    }

    int AND = (1 << BITS) - 1;
    for (int i = 0; i < BITS; i++) {
        if (!bitCnt[i].empty()) {
            AND ^= (1 << i);
        }
    }

    for (int i = 0; i < n; i++) {
        if (!incr[i]) {
            ++cnt[src[i]];
        }
    }

    for (int i = 1; i < maxA; i++) {
        for (int j = i; j < maxA; j += i) {
            divBy[i] += cnt[j];
        }
    }

    for (int g = maxA - 1; g > AND + x; g--) {
        if (divBy[g] < 2) {
            continue;
        }

        int fId = -1;
        int sId = -1;
        for (int i = 0; i < n; i++) {
            if (!incr[i]) {
                if (src[i] % g == 0) {
                    if (fId == -1) {
                        fId = i;
                    } else {
                        sId = i;
                    }
                }
            }
        }
        coutYES(fId, sId);
        return;
    }

    cout << "NO\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int testN;
    cin >> testN;
    while (testN--) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h> using namespace std ; #define ld long double #define ll long long int fact[400001] = {0}; vector<vector<int>> num(400001); vector fst(400001,vector<int>(20,0)); unordered_set<int> s; int mul = 1; void gen( vector<int> &num, int in = 0 ) { if( in == num.size() ) s.insert(mul); else { mul *= num[in]; gen(num,in+1); mul /= num[in]; gen(num,in+1); } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); fact[1] = 1; for( int i = 2; i <= 4e5; ++i ) if( fact[i] == 0 ) for( int j = i; j <= 4e5; j += i ) if( fact[j] == 0 ) fact[j] = i; int tt = 1; cin >> tt; while( tt-- ) { int n, k, flag = 0, x; cin >> n >> x; int miny = (1<<20), inx, iny; vector<int> a(n); int bit[20] = {0}; for( auto &i: a ) cin >> i; sort( a.begin(), a.end() ); for( int i = 1; i < n; ++i ) { if( (a[i-1] & a[i]) < miny ) { miny = a[i-1]&a[i]; inx = i-1; iny = i; } } set<int> o; for( auto &i: a ) { int j = i; vector<int> pf; while( j != 1 ) { pf.push_back(fact[j]); j /= fact[j]; } vector<int> stbit; for( int u = 0; u < 20; ++u ) if( ((i>>u)&1) ) ++bit[u], stbit.push_back(u); gen(pf); for( auto &u: s ) { o.insert(u); num[u].push_back(i); for( auto &h: stbit ) fst[u][h]++; } mul = 1; s.clear(); } for( auto k = o.rbegin(); k != o.rend() && flag == 0 ; ++k ) { int g = *k; if( num[g].size() < 2 ) continue; int sz2 = n - num[g].size(); int y = 0; for( int i = 0; i < 20; ++i ) if ( bit[i] - fst[g][i] == sz2 ) y += (1<<i); if( y + x < g && sz2 >= 2 && sz2 <= n-2 ) { flag = g; break; } for( int u = 19; u >= 0 && flag == 0 ; --u ) if( (y>>u)&1 ) { int d = -1; for( int i = 0; i < num[g].size(); ++i ) if( num[g][i] != -1 ) { if( d == -1 && ((num[g][i]>>u)&1) == 0 ) d = i; if( d != -1 && (y&num[g][i]) < (y&num[g][d]) ) d = i; } if( d != -1 ) { sz2++; y = y&num[g][d]; num[g][d] = -1; } if( y + x < g && sz2 >= 2 && sz2 <= n-2 ) { flag = g; break; } } if( sz2 == 0 ) { sz2 = 2; y = miny; num[g][inx] = num[g][iny] = -1; } else if( sz2 == 1 ) { sz2 = 2; int d = -1; for( int i = 0; i < num[g].size(); ++i ) { if( d == -1 ) d = i; if( d != -1 && (y&num[g][i]) < (y&num[g][d]) ) d = i; } y = y&num[g][d]; num[g][d] = -1; } if( y + x < g && sz2 >= 2 && sz2 <= n-2 ) { flag = g; break; } } if( flag != 0 ) { cout << "YES\n"; vector<int> v1, v2; for( auto &i: num[flag] ) if( i != -1 ) v1.push_back(i); int i = 0; for( auto &j: a ) if( i >= v1.size() || v1[i] != j ) v2.push_back(j); else ++i; cout << v1.size() << ' '; for( auto &i: v1 ) cout << i << ' '; cout << '\n' << v2.size() << ' '; for( auto &i: v2 ) cout << i << ' '; cout << '\n'; } else cout << "NO\n"; for( auto &i: o ) { num[i].clear(); fst[i] = vector<int>(20,0); } } }

Comments (18)

Show archived | Write comment?

theRealChainman

2 years ago, hide # |

+11

For problem G the editorial has the swapped inequality it should be suffixMax_p >= k(Q2_front), because that indicates there is a larger k in the suffix of Q1 that highest priority person in Q2 would be waiting behind.

→ Reply

bruce_x001

Problem E Video Editorial Audio : (Hindi)

YOUTUBE VIDEO LINK ---Click Here

Fuad

← Rev. 2 →

At problem B,

"At the moment x, there will be fireworks in the sky, released at moments [x, x+a, …, x+a⋅⌊m/a⌋]"

Please explain.

somanyducks

Problem F can be simulated with an ordered statistic tree :p

252626826

md_nihal

← Rev. 4 →

In C sample 1.

3
101
outut:2

"can't we insert at 0 the villagers to right side 2 of 3 are satisfied ?

If there are multiple suitable positions i with the minimum ∣n2−i∣, output the smaller one."

bhanu2306

2 years ago, hide # ^ |

+14

In that problem n/2 is not rounded to an integer, it may be a decimal value

_NonSense_

nvm, i got it lol good contest btw

darkkcyan

I think the problem G's statement is still not 100% clear. If 2 students with the same priority, finishing their dishes at the same time, who will go to the queue first?

I tried to solve this solve this by assuming the one who goes out eating first will come back first, but apparently this seems to not be the case. The comparator function in the solution prioritize the student with higher eating time first. This seems very unnatural to me.

Though the problem idea didn't change much if a more strictly description was added. This is still a cool problem. Though this bug me for hours, not know where I was wrong.

bushang2100bugaiming

Question does say

"If several schoolchildren return at the same time, they will return to the queue in ascending order of their si."

a-a-a

Can anyone explain E? Not able to get it from the tutorial.

ItsNotMeItsYou

We know this binary search gives a number which is always <=X. (If you are not sure about that, you can try some examples.)

Assume P is position of X.

If we change this result and P, we can find X. Because only once we asked to P. And smaller number will give same answer(make l = mid). So we will get same index before don't swapped P and result.

Got it, Thanks

employed

in problem H why if a bit is 0 in more than 2 numbers then its 0 in the AND ? i understand that if we have 3 or more numbers with bit x 0 in them then it'll always be zero in the finally AND but sometimes we can have only 1 number with bit x equal to 0 and still the finally AND will have that bit 0 if we dont consider it in the red numbers ? the middle paragraph is unclear hope somebody rewrites it in a more clear way , thanks

adaptatron

Your understanding is correct. Suppose we are dealing with $$$x^{th}$$$ bit. There are 3 cases:

None of the numbers contain a 0 at this position : The AND would contain 1.
There are $$$ \gt 2$$$ 0 at this position. The AND would contain 0.
There are 1 or 2 zero at this position. Then, we are not sure about the AND. But, let's pick one element with zero at this position, move it to the blue set, and then, let's try to pair it up with all possible elements. If no match could be found, then we know for sure that the element belongs to the red set, hence making the AND zero.

I've added more details here

Yea thanks I got it , it wasn't clear at the beginning I feel like it would've been more clear if they stated why we try all numbers where the bit is 0 in no more than 2 but now that I get it I feel like it's self explanatory

Sekai02

22 months ago, hide # |

Problem F. Kirill and Mushrooms can actually be solved using Fenwick Tree:

Let us fix the number of mushrooms for a potion. Let this number be $$$k \leq n$$$. Now we have to maximize the minimum value that we choose for this potion. This number is the $$$k-th$$$ maximum, lets call this number $$$mxmin$$$. And we update the answer with $$$ans=min(ans,mxmin*k)$$$.

Fenwick Tree allow us to find the $$$k-th$$$ maximum, wich is equivalent to findind the $$$(rem - k + 1)-minimum$$$ with BinaryLifting. Where $$$rem$$$ is the remaining number of mushrooms. You can find how to do this in this blog

When we go from $$$k$$$ mushrooms to $$$k+1$$$ mushrooms we have to update the FenwickTree by subracting the value of the $$$p[k]$$$ mushroom.

See the code for any other detail: My submission

AksLolCoding

For problem F you can just use order statistic tree and use find_by_order to solve in nlogn time.

edge_case

14 months ago, hide # |

this code for h but get wrong answer at testcase 3.Had tried stress test but not found any

kindly help me to debug this

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

#	User	Contrib.
1	Qingyu	157
2	adamant	153
3	Um_nik	147
3	Proof_by_QED	147
5	Dominater069	145
6	errorgorn	142
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Kirill_Maglysh's blog