Codeforces Round 995 (Div. 3) — Editorial

#	User	Rating
1	jiangly	4039
2	tourist	3841
3	jqdai0815	3682
4	ksun48	3590
5	ecnerwala	3542
6	Benq	3535
7	orzdevinwang	3526
8	gamegame	3477
9	heuristica	3357
10	Radewoosh	3355

#	User	Contrib.
1	cry	168
2	-is-this-fft-	165
3	atcoder_official	160
3	Um_nik	160
5	djm03178	157
6	Dominater069	156
7	adamant	153
8	luogu_official	152
9	awoo	151
10	TheScrasse	147

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

def findMissingNum(q,k,n): sum_arr= 0 for ind in range(k): sum_arr+=q[ind] total = (n*(n+1))//2 return (total - sum_arr) def resultDeterminer(n: int,m: int,k: int,a: list,q: list): if k < (n-1): return "0"*m elif k == n: return "1"*m else: ans = "" missing_num = findMissingNum(q,k,n) for ind in range(m): if a[ind]!=missing_num: ans+="0" else: ans+="1" return ans if __name__ == "__main__": t = int(input()) while(t): n,m,k = map(int, input().split()) a = list(map(int, input().split())) q = list(map(int, input().split())) print(resultDeterminer(n,m,k,a,q)) t-=1

Comments (97)

Write comment?

BledDest

4 weeks ago, # |

+12

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

→ Reply

Eeezoe

4 weeks ago, # ^ |

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!

Jonhyer

I think E problem has some ambiguity because if the price advances bi ，that someone may dont buy it and also dont leave a negative review

all right, i am wrong sorry

Roxy__

It seems to be just a translation problem. There is ambiguity. It means neither buying nor leaving negative comments.

Thanks bro.

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:(

alpamis

Does that mean they are always consecutive?

Nao233

3 days ago, # ^ |

$$$i < j$$$ essentially just means that they are different and that you should divide the result you get by not enforcing $$$i < j$$$ by $$$2$$$.

JackOfMostTrades

Bro I'm in your exact same position, I solved a similar problem before where we calculated for each index, we subtract 1 for the index itself if counted, and then we finally divide our answer by 2, I solved a problem that looks exactly like this. I felt sorrow when I realized it.

Also add to that problem E, it was easy to solve if you knew that the price would not be anything outside of arrays A and B, but genius me was trying to do binary search on the price :)

gsscala

During contest I also didn't realize it, so this was my submission. 297901632

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)

Naveen14

3rd customer (ai=5) gives negativer review right . so neg_rev=2 not possible one

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

pain.limit.exceeded

← Rev. 2 →

Is it possible to solve E by using BS on answer on the price which we should set for tree and then calculate the earning ... Nvm i got it

mastersaksham12345

3 weeks ago, # ^ |

what did you get? is it possible or not?

No it won't be possible as it is not unimodal

LMeyling

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

Why is it not unimodal?

om.nom

Earning = cost of tree * no. of customer who buys.

pranjalchabra1908

it will increase till next person starts not buy tree and then suddenly again decrease

lets say a starts to not buy it at 10 then from one to 9 your earning will inc. but suddenly your earning will decrease at 11 because 1 person but it may also depend on people who buying it if they can compensate it .....

chineseremaindertheoram

Instead of prices, i kept track of negative reviews, if negative reviews is more than k, i changed my high to mid-1 else low = mid+1, whats wrong with this approach.298136423

harilakshman24

For doing binary search you need to have the negative rev array as follows for prices first k , but this is not how neg rev look for the prices , try with some test cases may be with the second pretest 1 test case where you never reach cost of 12 if you do as you mentioned

there is nothing wrong but it is incomplete you can say....

you will reach a price where you will get k negative reviews at best but have you considered how people will buy trees

every price less then low will be valid price but how much will you will depend on how many people will buy you trees may be at some price less people buy your product but cost is high enough that you earn more or at some price less price more people buy tress that you earn more

you can iterate over all the price less than your final low ....

or you can check for all the prices given in question which is less than equal to your final low

Nesta

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

dhrxv._

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

EndMyMisery

← 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;
}

sho_eib_w_sho_msh_eib

why the testcases of the problems are opened?

0x3F

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

nayeem525

yeah the idea is similar , there are multiple problems that follows the inequality pattern.

justplaygame

https://codeforces.net/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 ??

I don't think you can do BS on price as it would not follow regular structure. Consider price x and y | x < y, if y is valid then x may or may not be valid because it may happen that x is in > k customer range. Correct me if I am wrong.

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 :(

Ohhh, my bad! Specialist

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

_Artist__

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

Yeah, my bad and thanks for pointing that out.

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)

Oh, thank you for helping me this far. I didn't think of binary search because I just brute forced the solution.

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

Ahh. My bad. Thanks for pointing it out. I had written m-k>=2 too but changed it before submission for the if() part. I forgot to change the else part.

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.

not yet

TalkySafe143

Hi, for problem E, can someone explain me why this submission 297935421 in contest got AC but for later tests got TLE? The total complexity isn't $$$O(n \log n)$$$?

I other problem before, I used the same technique and got TLE too.

Thanks!

EDIT: TLE was for setting a bad comparator to sort() function. 298263208

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.

Sorry ，I read the question wrong, and I get AC now.

pc19937

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

Adii

if someone solved d using binary search pls share your solution

HarshitKumarGupta

Yes, I was able to implement it for search within a range. Check this Python 3 solution: https://codeforces.net/contest/2051/submission/297906734

Try to read through the implementation, instead of conventional check on a value, it checks for the value being $$$<$$$ lower bound ( = $$$\Sigma - a[i] - y$$$ given max. sum ), $$$>$$$ upper bound ( = $$$\Sigma - a[i] - x$$$ given min. sum ), or being in the range with >= lower bound and <= upper bound.

In case you wonder about the bounds, $$$\Sigma - a[i] - a[j] < x \implies \Sigma - a[i] - x < a[j]$$$ holds as long as the values are non-negative.

Thank You !!

Serioton_codes

Ok if you want to understand Problem E...

watch this super easy code.... https://codeforces.net/contest/2051/submission/298088585

What i did was to use sweep line algorithm to find efficiently the number of negative reviews for a given price (which will be someone among a's or b's) and uses binary search to find the customers who can afford the tree and if negative reviews are below the constraint(k) booommm we got a possible answer and i update my final answer.

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

For Problem E, simply use line sweep:

keep track of total a[i] and b[i] at each point. Then line sweep them.

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)

apexcoder007

Did anyone solve E using ternary search? Also I would love to know whether or not it can actually be solved using ternary search on price p of trees.

ckxian

E was nice sweepline, 298190107

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.

Aayush_Rana_

For E i am getting tle in sweep line solution can anyone help

chauhankanishk77

My submssion for problem C is giving TLE for test case 3. I don't know why. Can someone tell me why ? It seems efficient. Below is my solution:

gabrielfaure

3 weeks ago, # |

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

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

BledDest's blog