Codeforces Round 995 (Div. 3) — Editorial

2051A - Preparing for the Olympiad

Tutorial

Solution (Neon)

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    int ans = a[n - 1];
    for (int i = 0; i < n - 1; ++i)
      ans += max(0, a[i] - b[i + 1]);
    cout << ans << '\n';
  }
}

2051B - Journey

Idea: fcspartakm

Tutorial

Solution (BledDest)

t = int(input())
for i in range(t):
    n, a, b, c = map(int, input().split())
    sum = a + b + c
    d = n // sum * 3
    if n % sum == 0:
        print(d)
    elif n % sum <= a:
        print(d + 1)
    elif n % sum <= a + b:
        print(d + 2)
    else:
        print(d + 3)

2051C - Preparing for the Exam

Idea: BledDest

Tutorial

Solution (BledDest)

for _ in range(int(input())):
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    q = list(map(int, input().split()))
    used = [False for i in range(n + 1)]
    for i in q:
        used[i] = True
    l = len(q)
    for i in range(m):
        if l == n or (l == n-1 and not used[a[i]]):
            print(1, end='')
        else:
            print(0, end='')
    print()

2051D - Counting Pairs

Idea: fcspartakm

Tutorial

Solution (BledDest)

def calcLessThanX(a, x):
    n = len(a)
    s = sum(a)
    j = 0
    ans = 0

    for i in range(n-1, -1, -1):
        while j < n and s - a[i] - a[j] >= x:
            j += 1
        ans += (n - j)

    for i in range(n):
        if s - a[i] - a[i] < x:
            ans -= 1
    
    return ans // 2

for _ in range(int(input())):
    n, x, y = map(int, input().split())
    a = list(map(int, input().split()))
    
    a = sorted(a)
    print(calcLessThanX(a, y+1) - calcLessThanX(a, x))

2051E - Best Price

Idea: BledDest

Tutorial

Solution (Neon)

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

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    vector<pair<int, int>> ev;
    for (int i = 0; i < n; ++i) {
      ev.emplace_back(a[i], 1);
      ev.emplace_back(b[i], 2);
    }
    sort(ev.begin(), ev.end());
    long long ans = 0;
    int cnt = n, bad = 0;
    for (int i = 0; i < 2 * n;) {
      auto [x, y] = ev[i];
      if (bad <= k) ans = max(ans, x * 1LL * cnt);
      while (i < 2 * n && ev[i].first == x) {
        bad += (ev[i].second == 1);
        bad -= (ev[i].second == 2);
        cnt -= (ev[i].second == 2);
        ++i;
      }
    }
    cout << ans << '\n';
  }
}

2051F - Joker

Idea: BledDest

Tutorial

Solution (Neon)

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> segs({{1, -q}, {m, m}, {n + q + 1, n}});
    while (q--) {
      int x;
      cin >> x;
      bool ins = false;
      for (auto& [l, r] : segs) {
        if (x < l) l = max(1, l - 1);
        else if (x > r) r = min(n, r + 1);
        else {
          ins = true;
          if (l == r) l = n + q, r = -q;
        }
      }
      if (ins) {
        segs[0] = {1, max(segs[0].second, 1)};
        segs[2] = {min(segs[2].first, n), n};
      }
      int lf = 0, rg = -1, ans = 0;
      for (auto [l, r] : segs) {
        if (l > r) continue;
        if (l > rg) {
          ans += max(0, rg - lf + 1);
          lf = l; rg = r;
        }
        rg = max(rg, r);
      }
      ans += max(0, rg - lf + 1);
      cout << ans << ' ';
     }
     cout << '\n';
  }
}

2051G - Snakes

Idea: BledDest

Tutorial

Solution (adedalic)

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

const int INF = int(1e9);

int n, q;
vector<int> id, ch;

bool read() {
    if (!(cin >> n >> q))
        return false;
    id.resize(q);
    ch.resize(q);
    fore (i, 0, q) {
        char c;
        cin >> id[i] >> c;
        id[i]--;
        ch[i] = c == '+' ? 1 : -1;
    }
    return true;
}

int getDist(int s, int t) {
    int pSum = 0, cMin = 0;
    fore (e, 0, q) {
        if (id[e] == t)
            pSum += ch[e] < 0;
        if (id[e] == s)
            pSum -= ch[e] > 0;
        cMin = min(cMin, pSum);
    }
    return -cMin + 1;
}

inline void solve() {
    vector<vector<int>> minDist(n, vector<int>(n, INF));

    fore (i, 0, n) fore (j, 0, n)
        minDist[i][j] = getDist(i, j);

    vector<int> len(n, 0);
    fore (e, 0, q)
        len[id[e]] += ch[e] > 0;
    
    vector< vector<int> > d(1 << n, vector<int>(n, INF));
    fore (i, 0, n)
        d[1 << i][i] = 1;
    
    fore (mask, 1, 1 << n) fore (lst, 0, n) {
        if (d[mask][lst] == INF)
            continue;
        fore (nxt, 0, n) {
            if ((mask >> nxt) & 1)
                continue;
            int nmask = mask | (1 << nxt);
            d[nmask][nxt] = min(d[nmask][nxt], d[mask][lst] + minDist[lst][nxt]);
        }
    }
    int ans = INF;
    fore (lst, 0, n)
        ans = min(ans, d[(1 << n) - 1][lst] + len[lst]);
    cout << ans << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);

    if(read()) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

// this is code temp.push_back(v[0]); for(int i = 1; i < n; i++) { int l = lower_bound(temp.begin(), temp.end(), left - v[i]) - temp.begin(); int r = upper_bound(temp.begin(), temp.end(), right - v[i]) - temp.begin(); ans += r - l; temp.push_back(v[i]); }

int countLessThan(const vector<int>& arr, int x) { int lo = 0, hi = arr.size(); while (lo < hi) { int mid = lo + (hi — lo) / 2; if (arr[mid] < x) lo = mid + 1; else hi = mid; } return lo; } int countGreaterEqual(const vector<int>& arr, int x) { int lo = 0, hi = arr.size(); while (lo < hi) { int mid = lo + (hi — lo) / 2; if (arr[mid] < x) lo = mid + 1; else hi = mid; } return arr.size() — lo; } void solve() { int n, k; cin >> n >> k; vector<int> a(n), b(n); for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 0; i < n; i++) cin >> b[i]; sort(a.begin(), a.end()); sort(b.begin(), b.end()); int res = 0; for(int i = 0; i < n; i++) { int c2 = countLessThan(a, a[i]); int c3 = countLessThan(b, a[i]); if(c2 - c3 <= k) { int cnt = countGreaterEqual(b, a[i]); res = max(res, cnt * a[i]); } } for(int i = 0; i < n; i++) { int cnt = countLessThan(a, b[i]); int c3 = countLessThan(b, b[i]); int c2 = countGreaterEqual(b, b[i]); if(cnt - c3 <= k || c2 <= k) { res = max(res, b[i] * c2); } } cout << res << endl; }

Comments (65)

Show archived | Write comment?

BledDest

16 months ago, hide # |

+12

If tutorials for some problems aren't loading, they should be up in about 3-4 minutes.

→ Reply

Eeezoe

16 months ago, hide # ^ |

The E problem is really well designed. Initially, my understanding of the scanline algorithm was focused on processing points within a two-dimensional range. Therefore, when analyzing the E problem, I enumerated all the values of $$$~a_i~$$$ and $$$~b_i~$$$ and treated them as prices, which we denote as val. At this point, the number of buyers among those who would not leave negative reviews is the count of $$$~a_i~$$$ that are greater than or equal to val. The number of buyers who would leave negative reviews is the count of $$$~b_i~$$$ that are greater than or equal to val, under the condition that $$$~a_i~$$$ for that $$$~b_i~$$$ is greater than val. Thus, I viewed this problem as counting points within a two-dimensional range, applying a scanline approach combined with offline processing using a Fenwick tree. However, the complexity of this approach prevented me from implementing it during the competition. After the contest, I was able to see a similar application of the scanline thinking, and the profound understanding of it truly opened my eyes. This also led me to reflect on the essence of the scanline preprocessing, which is to update all necessary states in a legal time complexity according to a certain order. It made me reconsider that in my code design, I should focus on specific implementation steps rather than just thinking about which algorithm to apply. This experience has been very educational and helpful for me! I really appreciate the design of the problems you created!

Trumpsunderwear

For problem D, I felt so pathetic, if I would have realised earlier that there is no distinction between index i and j. I have solved same kind of question earlier, I would have solved it in contest as well as:(

0x81

E, input:

3 1
2 9 5
12 14 9

Why the answer is not 18 (2 * 9)?

1st customer: 9 <= b (negative review), 2nd customer: 9 <= a (positive review).

Christopher_Rdz

The thrid customer will give a negative review as well (9 <= 9)

akkafakka

In E, a third method to optimize would be using PBDS, 297960644

Akil_Newaz_Chy

Is it possible to use PBDS to solve D?

Yes, I used it 297849167

Friedrich

← Rev. 4 →

Hi is there anyone able to solve G with python? My TSP seems too slow (currently at 7000ms). Also, it there any reason for the strict contraints, making it just a library check as even some C++ solutions are TLEing?

UPD: Got it AC

chiragxarora

E is simple binary search on answer right? Or am I missing something?

quater_nion

Binary search wont work because total earning w.r.t cost of the tree is not monotonus or unimodal.

gsscala

Why is it not unimodal?

Catenaccio

← Rev. 2 →

you can not be sure that if p is not a valid price then p+1 will also not be valid. Consider an example a = [6, 12, 12, 12] and b = [10, 20, 30, 40], and k = 0. Here the valid interval for a price could be [1, 6] but once the prices reaches 7, we will forced to buy the first tree, giving one negative review which is not allowed. The same will be the situation for 8, 9 and 10. But, once the price reaches 11 we can buy the remaining three trees with zero negative reviews. and beyond 12 we can again not buy anything. so the earnings increase in the interval [1, 6] then go to 0 in the range [7,10], peaking at 12 and again going to zero at beyond that. This behavior is not monotonic

saquib2508

7 months ago, hide # ^ |

Can you help me find the bug in my approach 340085771 ? I tried finding highest possible price within the negative review limit by binary search (don't care about the profit now). Once I have that (let's call it highest_possible_price, I tried finding profit in 2 ways.

trying all possible a[i] and b[i] prices that are less than highest_possible_price and take the highest profit
instead of going over these prices linearly, I tried a ternary search as well. But I commented it out later since it's failing even on linear search so something is probably wrong at finding highest_possible_price.

I'm really clueless even though I was pretty confident in my mind that it would work. Getting WA on 40th case of test 2 so can't check myself.

dhrxv._

Why are O(nlogn) solutions getting hacked in E ?

wiaderko69

← Rev. 3 →

Maybe they get TLE? My O(nlogn) c++ solution barely fits in TL. 297985458

try this

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

void solve() {
    int n, k;
    cin >> n >> k;
    map<int, int> positive_review, negative_review;
    priority_queue<int, vector<int>, greater<>> prices;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        positive_review[a]++;
        prices.emplace(a);
    }

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        negative_review[a]++;
        prices.emplace(a);
    }

    int best = 0;
    int negative = 0;
    int last = -1;
    while (!prices.empty()) {
        int price = prices.top();
        prices.pop();
        if (price == last)
            continue;
        last = price;
        int cur = n * price;
        if (negative <= k)
            best = max(best, n * price);
        negative += positive_review[price];
        negative -= negative_review[price];
        n -= negative_review[price];
    }

    cout << best << endl;
}

signed main() {
    #ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

shaaban_abdelrahim

why the testcases of the problems are opened?

0x3F

Problem D is same to LeetCode 2563. Count the Number of Fair Pairs

justplaygame

https://mirror.codeforces.com/contest/2051/submission/297939657

in e problem i have done binary search on binary search , can you tell me why this will not work , basically what i did is first i did bs on profit , now to check if we can get profit x or not i have done binary search on price that what price we can keep so that it can give desired profit ??

vstiff

For D: if two pointers do not solve problem, use 3 297969402.

YashShewale

Can Anyone give me hint for problem E? just hint for from where to start thinking process

garlic_bread_0204

It is optimal only to consider ai and bi as prices

Thank you Expert !

it's christmas offer .. I m just 1508 :(

ndstab

anyone got AC following the alternate approach in E? im following a very similar approach but it fails my approach please help me out

NotAnArtist

Maybe check my solution out
298020385

MAieshAdnan

Why my brute force solution doesn't work for D (I skipped C)? 297948999. It doesn't give TLE but it gives Wrong Answer on Test 3.

Senku

You wrote "ll totalSum = accumulate(a.begin(), a.end(), 0);" Instead you should write "ll totalSum = accumulate(a.begin(), a.end(), 0LL);" so the calculation takes place in long long type

What about my approach? Are there any flaws?

theflyingdutchman1

Time complexity is O(n^2)

Yeah, but what about cases after test 3? Would it get TLE or WA or AC? Currently, I can't submit because of system testing.

After you change (m — k == 0) to (n — k == 0) you will get TLE for your code

if you sort the array first, u can use binary search instead of using running nested for loops.

How I mean I looked at the editorial but I didn't make sense of it? We need to find the number of pairs 'i, j' such that if we remove i and j the sum of all elements is at least x or at most y. How can I use binary search? and thank you for helping me!

Text use temp vector to store the values already visited and find the range that would satisfy the req condition. ( here left = total — y, right = total — x).

Yes, just use lower_bound and upper_bound functions to find the range satisfying the given condition (either on the remaining part of the array or the completed part)

pushp-raj-mishra

297858654 Can anyone tell me why this solution of C got hacked.

in the else if you wrote m-k==0 instead of n-k==0

The judge gave an accepted verdict for my slightly wrong submission of Problem C during the contest, but in post-contest judgements I got WA on Test Case 10. :(

Idk if it was the issue with the judging software or the initial testcases were bad.

ibrm

I guess pretests contained only n = m cases, at least my solution that swaped n and m in some places passed the pretests.

Yess, so basically the initial testcases were poorly designed

copyPasteCoder

same issue with me 🥲

case3

Obviously the problem E is binary search. For anyone here is the solution pretty straight forward.

Solution

Observation only the cost values of ai and bi matters either take a penalty with maximum hit or don't. Any other values in between don't make any sense.
Binary search if the cost is C then how many people can buy it happily and how many can't buy at all.
Calcuate the penalty from these 2 values which is just total people — people who can buy happy — people who cannot buy at all and then see if penalty people are in our limit
If in our limit take the current cost and go on max of all such costs.

I was 7 minutes late in contest. Observation 3 got me. I thought its in my best interest if I want to sell or not but apparently I have to sell if the customer can afford because "the customer is always right".

PS: How to approach F in simple language?

omegaphi

If intially u have joker at 5th positon . if a0<5 it will occupy 4th and 5th position , if a0>5 it will occupy 5th and 6th position . so doing this u will get that joker will occupy from l to r . now if ai<l l--,else if ai>r r++ else the joker will also occupy 1st and nth position . now keep doing the same thing assuming u have 3 segments 1 to l1 , l to r and r2 to n

panwar123

Here is my solution to the Problem E which i find really interesting.

Firstly i hash all the values with the index of the vector then i count the values which might leave the negative review using a difference array which is values that are a[i]+1 to b[i] after that i iterate for the values and calculate the cost for which has k or less negative review.

Submission : 297938827

TheArcticWolf

this sir is exactly how i thought as well. anyway had a rough contest.

for reference , here's my submission: 298046917

TiwoeeM

F was smart

Defylogicguy

F is so hard. I can't imagine F being a question about segments.

tokaisu

Is the rating updated for you guys? This is taking a bit longer than usual.

JokerKing_forever

For F , how to get 5 in the first example?I only get [2 , 3 , 4 , 5]

olegmak

Just implement the required operations in a straightforward way to calculate all possible deck states, then count unique positions for joker.

uma15

This round really preserved the beauty of Educational Rounds as the authors are the same... sadly, I could not attend it live and had to participate virtually.

Astroflexx

What would be the difficulty rating of problem E and F? clist.by says 1980 for E and 2349 for F but I don't think it's that much, no?

rishitverma

E in my opinion should be between 1400 and 1600. Couldn't really solve F so can't give my opinion on it.

theriseofahero

My submission 298069513 for Problem E is giving wrong answer in testcase 2. Can anyone please help out why this is happening and at what testcase it fails? bcoz according to me my logic seems correct.

Thanks

Since nobody replied to my comment I figured it out myself.

The problem was in the case of duplicates in a and b arrays. This code didn't consider duplicates.

This is resolved in this solution 299196423

whiitex

Here a super-easy and clean implementation of problem E using upper_bound to find number of positive and negative reviews without creating new arrays (just sorting the original ones with negative values): 297888481

Furina_

8 months ago, hide # ^ |

Oh,my method is almost the same as yours.334535654

kingsmaker

Shouldn't the test case for D, 7 10 13 4 2 5 2 4 3 1

be giving 3 instead of 4. What am I missing here?

Pairs from your example are: (3 5) (4 4) (4 5) (4 5)

lcha

Could anyone explain why O(n^2*q + 2^n * n ^ 2) solution for problem G works for n <= 20 and q <= 2*10^5? I normally suppose that 10^8 operations will be run in 1 second, so this solution runtime should be more than 4s.

meta-circular

15 months ago, hide # |

I find my solution to D to be much simpler than the editorial's--the only downside is that it uses PBDS: https://mirror.codeforces.com/contest/2051/submission/299348552

I think the code is self-explanatory (ignoring the indentation and other weird quirks.)

souravsaran155

11 months ago, hide # |

can anyone tell me why my code is not passed 3rd test case for problem b https://mirror.codeforces.com/contest/2051/submission/319545029

heavenlybeast1122

8 months ago, hide # |

MY SOLUTION FOR E ->

int countLessThan(const vector<int>& arr, int x) {
    int lo = 0, hi = arr.size();
    while (lo < hi) {
        int mid = lo + (hi &mdash; lo) / 2;
        if (arr[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}


int countGreaterEqual(const vector<int>& arr, int x) {
    int lo = 0, hi = arr.size();
    while (lo < hi) {
        int mid = lo + (hi &mdash; lo) / 2;
        if (arr[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return arr.size() &mdash; lo;
}


void solve() {

    int n, k;
    cin >> n >> k;

    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int res = 0;


    for(int i = 0; i < n; i++) {
        int c2 = countLessThan(a, a[i]);
        int c3 = countLessThan(b, a[i]);
        if(c2 - c3 <= k) {
            int cnt = countGreaterEqual(b, a[i]);
            res = max(res, cnt * a[i]);
        }
    }


    for(int i = 0; i < n; i++) {
        int cnt = countLessThan(a, b[i]);
        int c3 = countLessThan(b, b[i]);
        int c2 = countGreaterEqual(b, b[i]);
        if(cnt - c3 <= k || c2 <= k) {
            res = max(res, b[i] * c2);
        }
    }

    cout << res << endl;

}

#	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

BledDest's blog