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

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

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

ty for great contest!

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

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

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

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

why the testcases of the problems are opened?

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

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 ??

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

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

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

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.

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

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.

Did anyone else have a solution in C that gets WA on testcase 8 (although mine previously passed) because of a non-alphanumeric character showing? If yes, was this a bug on my side or a bug on Codeforces?

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

Solution

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

2. Binary search if the cost is C then how many people can buy it happily and how many can't buy at all.

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

4. 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?

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

F was smart

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

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

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

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.

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?

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

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

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?

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.

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

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

my solution for E — > ~~~~~ int countLessThan(vector& 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(vector& 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;

} ~~~~~

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;

}