Codeforces Round #935 Разбор

№	Пользователь	Рейтинг
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3390
6	Um_nik	3387
7	tourist	3384
8	heuristica	3322
9	turmax	3319
10	jiangbowen	3291

№	Пользователь	Вклад
1	Qingyu	155
2	nik_exists	150
2	maspy	150
4	Um_nik	144
5	Errichto	139
6	adamant	137
7	AmShZ	136
8	BledDest	132
8	maroonrk	132
10	qwexd	129

1945A - Setting up Camp

Разбор

Решение

#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

Идея: NToneE, Gadget

Разбор

Решение

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

Идея: Gadget, NToneE

Разбор

Решение

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

Идея: Kirill_Maglysh

Разбор

Решение

#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

Идея: Kirill_Maglysh

Разбор

Решение

#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

Идея: Kirill_Maglysh

Разбор

Решение

#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

Идея: Kirill_Maglysh

Разбор

Решение

#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

Идея: Kirill_Maglysh

Разбор

Решение

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

Комментарии (22)

Показать архивные | Написать комментарий?

theRealChainman

3 года назад, скрыть # |

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

→ Ответить

TalkySafe143

For problem D we can consider a dp approach: let $$$dp_i$$$ the minimum ammount of coins for reach the position $$$i$$$, thus:

$$$ dp_i= \begin{cases} a_n & \text{if } i = n \\ \min\{a_i+dp_{i+1}, a_i+dp_{i+1}-a_{i+1}+b_{i+1}\} & \text{otherwise} \end{cases}$$$

We can calculate solutions from $$$dp_1$$$ and choose $$$\min\limits_{1 \le i \le m}{dp_i}$$$. The basic idea is to choose between pay $$$b_i$$$ or $$$a_i$$$ for all $$$i$$$.

AJ7787_

2 года назад, скрыть # ^ |

CAN you please explain how did this expression for the dp come? what i mean is that what is the logic behind this expression

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

3 года назад, скрыть # ^ |

+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

H's tutorial is no unclear i'd love if somebody explains what the tutorial wants us to do i only understand why its always beneficial to take 2 numbers as the red and that the AND cant be less than the AND of the entire array , i dont get the rest ( the middle paragraph ) such as

we if a cet certain bit y is equal to zero in more than two numbers

Why more than 2 numbers ? if we have the bit x 0 in a certain number then it'll be 0 in the AND unless we take that number as red ?? so many questions

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

2 года назад, скрыть # |

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

20 месяцев назад, скрыть # |

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

mjm_hu

7 часов назад, скрыть # |

E is interesting , I see

Блог пользователя Kirill_Maglysh