include <bits/stdc++.h>

4 weeks ago, # |

Damn, I think I could have solved either F or G in time (and I was slow in beginning)... but considering that I did the contest while in a car lol ... not bad.

→ Reply

PetrShinomontazh

4 weeks ago, # |

speedforces A-D bincodeforcesearch

→ Reply

PetrShinomontazh

4 weeks ago, # ^ |

sorry was too lazy to solve E(and i wanna sleep, i slept only 2 hours this night. and i wanna eat). 3700 place, i think that very small, but positive delta.

→ Reply

4 weeks ago, # |

Did E require binary search?

I couldn't form the predicate function but will upsolve

→ Reply

4 weeks ago, # ^ |

Yeah, just sort and binary search on the left and right bounds for the interval to pair with the current element (when iterating through from left to right). be sure to pair with only elements that come after the current one.

→ Reply

jkulanko

4 weeks ago, # ^ |

You're thinking of D. He's asking about E which I also thought was binary/ternary search but couldn't figure out

→ Reply

4 weeks ago, # ^ |

Oh yeah, E was like interval processing. I didn't use binary search. Just maintain a map from (price) to (type of event), where each event is the start of an interval of the form (a_i, b_i] or the form (b_i, infinity). We basically iterate through these events in order and maintain the number of customers in the 0-a and a-b intervals, calculate the corresponding answer at interesting points, and only consider answers whenever the corresponding number of people in the a-b intervals is <= k.

→ Reply

4 weeks ago, # ^ |

could you share your solution?

from what I see it's a line sweep/greedy question

→ Reply

4 weeks ago, # ^ |

void solve() {
    int n, k;
    cin >> n >> k;
    
    vector<int> a(n), b(n);
    map<int, vector<pair<int, int>>> occ;
    set<int> eval;
    
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
 
    for (int i = 0; i < n; i++) {
        occ[a[i]+1ll].push_back({1ll, i});
        occ[b[i]+1ll].push_back({2ll, i});
 
        eval.insert(a[i]);
        eval.insert(a[i]+1ll);
        eval.insert(b[i]);
        eval.insert(b[i]+1ll);
    }
 
    int int1 = n;
    int int2 = 0;
    
    int ans = 0;
 
    for (auto i : eval) {
        for (auto j : occ[i]) {
            int tp = j.first;
            int ind = j.second;
            
            if (tp == 1) {
                int1--;
                int2++;
            } else {
                int2--;
            }
        }
 
        if (int2 <= k) {
            ans = max(ans, (int1+int2)*i);
        }
    }
 
    cout << ans << endl;
} 
 
signed main() {
    cin.tie(0)->sync_with_stdio(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        solve();
    }
}

→ Reply

4 weeks ago, # ^ |

nice thanks :)

→ Reply

4 weeks ago, # ^ |

← Rev. 3 →

I did E without any binary search. I used a priority queue to simulate the "events" than happen when reaching a number, and maintain 3 counts (Positives = 0, Negatives = 0, Unprocessed = n).

At a[i]: Positives++, Unprocessed--
At a[i] + 1: Positives--, Negatives++
At b[i]: Counts don't change, but this is where you can also take it as the cost of the tree to sell.
At b[i] + 1: Negatives--

After each "timestamp" is done, check if Negatives <= k then the current sum can be calculate as cost * (Positives + Negatives + Unprocessed) (The value at the moment can be taken as the cost).

→ Reply

4 weeks ago, # ^ |

why negatives-- ?

→ Reply

4 weeks ago, # ^ |

Oh there was a typo, what I meant was b[i] + 1, not b[i + 1]. Because at that point, the customer doesn't want to buy the tree anymore.

→ Reply

ishaanthenerd

4 weeks ago, # ^ |

I managed to upsolve E with your idea! Thank you!

→ Reply

Ndot

4 weeks ago, # ^ |

I did it abit differently. My idea was to use something like difference array Submission

→ Reply

Adityaxv

4 weeks ago, # |

+11

Great contest! Every division 3 should be like this. All the problems were nice and educational.

→ Reply

4 weeks ago, # |

Is problem E binary search?

→ Reply

4 weeks ago, # ^ |

Problem E: you can do it in 2 ways, 1st — Prove that the answer lies in the unique pairs of (ai, bi) always, can be proved using forming the loss function as we do in ternary search and observing that its convex, 2nd — use generic binary search with low =0, high = max(bi) and then check for each mid if we are well within the limits of <= k negative reviews if we are then find how many are willing to pay * mid, and find the max accordingly

→ Reply

4 weeks ago, # ^ |

I've failed to seek why my binary search solution is WA sadly.

Just now I read how others solve using intervals is very eyes-opening to me, learned and accepted with that method.

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

Ok so it took me 1 hour to realize the number of trees sold is not continuous by price (because the negative review condition break it), so binary search on it is wrong... sadly I got into wrong direction twice in this contest.

Outplayed, it took more to be an expert I guess :(

→ Reply

wingbuster

4 weeks ago, # ^ |

Could you kindly elaborate more on why you feel binary search won't work?

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

I explained the trivial binary search on best price or the trees sold won't work because the value function doesn't continuous.

Imagine a linear line function that is increasing/decreasing, but a few values got drop to 0 because of some condition. Then it's impossible to binary search the normal way because it will make your left/right decision being wrong. (when the mid value is pointing to that 0 value, your code bugs)

→ Reply

4 weeks ago, # ^ |

you might also keep the method binary search, but do it way more fancier. There's many submission out there to read how they works.

→ Reply

4 weeks ago, # ^ |

Its fine buddy, you learnt a lot, that's a plus ;)

→ Reply

wingbuster

4 weeks ago, # ^ |

I implemented what your 2nd solution is, but I am still getting a wrong answer: my submission

I think it has something to do with the "if(neg > k) high = mid — 1;" though I am not sure where I am going wrong.

→ Reply

4 weeks ago, # |

Is G about shortest hamilton path?

→ Reply

4 weeks ago, # ^ |

yes

→ Reply

akkafakka

4 weeks ago, # |

okay so 20 rounds of stress tests with $$$n$$$ being 2000 were not sufficient to debug my E. 297881571

→ Reply

dreameater69

4 weeks ago, # ^ |

That's the same test case where my code fails ..35th token from tc 2.. if u get where exactly your approach fails , pls post here

→ Reply

akkafakka

4 weeks ago, # ^ |

← Rev. 3 →

My flaw was while considering the price to be some $$$b[i]$$$, I need to have all the $$$a[i]$$$ corresponding to same $$$a[i]$$$ in my set. (I still don't know how so many stresses missed these TC).

→ Reply

dreameater69

4 weeks ago, # ^ |

my code had same issue even though I fixed this issue when considering a[i] as my price , idk why I missed this when considering b[i]s..

→ Reply

Ling_Chasha_Aifu

4 weeks ago, # |

← Rev. 2 →

check my solution why wrong on testcase 3rd?

#include <bits/stdc++.h>
using namespace std;
map<long long, long long> BIT;
const int inf = 1e9 + 7;
void update(long long i, long long x) {
    for (; i <= inf; i += i & -i) {
        BIT[i] += x;
    }
}

long long query(long long i) {
    long long res = 0;
    for (; i; i -= i & -i) {
        res += BIT[i];
    }
    return res;
}

void solve() {
    long long n, x, y;
    cin >> n >> x >> y;

    vector<long long> arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];

    long long t = accumulate(arr.begin(), arr.end(), 0LL); 
    long long ans = 0;

    BIT.clear();

    for (int i = 0; i < n; ++i) {
        long long lower_bound = max(0LL, t - arr[i] - y - 1); 
        long long upper_bound = max(0LL, t - arr[i] - x); 
        if (upper_bound) {
            ans += query(upper_bound);
        }
        if (lower_bound) {
            ans -= query(lower_bound);
        }
        update(arr[i], 1);
    }

    cout << ans << '\n';
}

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

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

    return 0;
}

→ Reply

PetrShinomontazh

4 weeks ago, # ^ |

shit, sorry bro, but i can't read it

→ Reply

om.nom

4 weeks ago, # |

E destroyed me inside out.

→ Reply

stils

4 weeks ago, # ^ |

Same.

→ Reply

Luca0506

4 weeks ago, # |

did anyone solved D by saving the frequency of each number occurs in a map? I got memory limited Exceeded, but i'm struggling to understand why i got that.

→ Reply

Acin03

4 weeks ago, # ^ |

yes, its because the hashmap would take up space of 10^9 ints in the worst case which is around 4gb of space whereas the memory limit is only 256MB.

→ Reply

felucia

4 weeks ago, # |

Why my E doesn't work: 297952582

→ Reply

case3

4 weeks ago, # ^ |

Refer to my code. Same logic and very readable.

→ Reply

case3

4 weeks ago, # |

Just got E accepted 7 minutes after round ended. Thinking of +20 laughs breaks into -20 tears. E was easy but just 1 line of continue;. Maybe +40 next game. Thank you for the contest, I enjoyed the problems. Very engaging.

→ Reply

AdityaTakkar

4 weeks ago, # |

Can somebody give some hints regarding Problem F and G? Thanks.

→ Reply

-ChunChunMaru-

4 weeks ago, # ^ |

I think G was pretty standard problem. If you precompute how much distance between 2 snake should be at the start, then you can just apply bitmask dp. Total complexity would be (n^2*q+2^n*n^2).

→ Reply

-ChunChunMaru-

4 weeks ago, # ^ |

On F, you can think where joker can be as intervals. Let's assume joker could have been at any position in interval [L,R]. If you remove one card from [1,L-1] and put it behind, then now joker can be at position [L-1,R]. And if you remove it and put at the front, then nothing changes. Now let's say there was query that asked to change a card that was joker, then new intervals will be added: [1,1] and [n,n]. And now you just have to track those intervals as well.

→ Reply

AdityaTakkar

4 weeks ago, # ^ |

Thanks

→ Reply

AdityaTakkar

4 weeks ago, # ^ |

← Rev. 2 →

Didn't get it yet.

→ Reply

Astroflexx

4 weeks ago, # |

Amazing contest! E was a cool line sweep problem! Thanks for the round Neon fcspartakm awoo adedalic BledDest and all testers!

→ Reply

KM_Parvez

4 weeks ago, # |

Problem E: why the output of last test case of problem E is not 18 but 15 ? I think price should be 9 and can buy 2 customers. what have I missed in the statement?

→ Reply

case3

4 weeks ago, # ^ |

The customer will buy its not your choice so if you keep it 9 then there are 2 penalties which is not allowed. Cost me 7 more minutes, resulted in only 4 problems solved :')

→ Reply

KM_Parvez

4 weeks ago, # ^ |

thanks got it.

→ Reply

lithiumpilled

4 weeks ago, # |

Can anyone help me why my logic for E is wrong? 297944262

→ Reply

olegmak

4 weeks ago, # ^ |

Your isValid() is not suitable for binary search because it produces "ok" values for small prices, then it may produce some -1 for larger prices, and then again "ok" for even larger prices.

→ Reply

4 weeks ago, # |

Usually I'm using C++, but for D, I turned to python for the convinience of SortedList to find how many numbers are smaller than a given number.

I'm wondering if there's an handy equivalent in C++?

→ Reply

spectrra

4 weeks ago, # ^ |

You can use the lower_bound.

→ Reply

_shikhr

4 weeks ago, # ^ |

We can't do that if we have to sort the array each time though?

→ Reply

4 weeks ago, # ^ |

We don't even have to sort the array each time lol. My solution just sorts once.

→ Reply

_shikhr

4 weeks ago, # ^ |

You can use pbds ordered_set data structure, but you have to manually import it though.

→ Reply

4 weeks ago, # ^ |

Thank you. I'll give it a try.

→ Reply

jai_hanuman_orz

4 weeks ago, # ^ |

We did mention this as being the overkill and defeating the purpose of the problem, but i don't think we could have had tests to distinguish between the intended solutions and one with pbds/sortedContainers.

→ Reply

itsraajjjuuuu

4 weeks ago, # ^ |

you meant lower_bound function on sorted array?

→ Reply

4 weeks ago, # ^ |

I mean if there is something similar to "multiset s" but I can do s.lower_bound(x) — s.begin() sort of things.

→ Reply

Astroflexx

4 weeks ago, # ^ |

Bro no disrespect or anything in any way but you're 1903 and never heard of ordered_set?

→ Reply

4 weeks ago, # ^ |

lol, you don't need ordered_set for anything to become red.

→ Reply

4 weeks ago, # ^ |

Probably heard of it. But never used before.

→ Reply

PrimeHunter

4 weeks ago, # |

why wasn't sweep line method working in E?

→ Reply

llc5pg

4 weeks ago, # ^ |

Try this input.

Spoiler

Your answer gives 100, but 100 should cause 2 negative reviews, which is not allowed.

→ Reply

llc5pg

4 weeks ago, # ^ |

The vector pair approach treats each event as independent, but in fact you should only update the answer after all xs which are the same have finished processing.

→ Reply

Aditya_Metkar

4 weeks ago, # |

In Problem D, 1 ≤ i < j ≤ n distracted me from even thinking about sorting.

Pretty devious problem statement lmao

→ Reply

Durgesh_A

4 weeks ago, # ^ |

yeah it was bugging me and my small capacity brain wanted to get rid of it, then i though if i select a pair from the array, its a given that one element's index will be lesser than the other's.

→ Reply

4 weeks ago, # |

← Rev. 2 →

A Different idea for Problem E:

Let the Earnings Function be :

Earnings(p)= p × (number of customers who buy at price p)

Since the function changes it's values only at (ai, bi). There is no need to consider prices outside the set of unique values from ai and bi, as the earnings function does not change between these points.

Hence we can store the unique pairs of (a,b), and then find the lower bound considering a and then using b.

Why this works?

→ Reply

ThinkDifferent

4 weeks ago, # |

My Code for E

I get totally blank as to how to think of test cases that break my code. Are there any tricks for it, experiences folks?

Additionally, can someone explain what am I missing that causes my code to fail!

Cheers, foster

→ Reply

Eyes_on_me

4 weeks ago, # |

isn't E ternary search(ish) ?

→ Reply

testingcpp

4 weeks ago, # |

Estimated rating for each problem?

→ Reply

-firefly-

4 weeks ago, # ^ |

You can refer to CLIST (which hasn't finished estimation yet). The official estimation will be days later.

→ Reply

skill_Issued

4 weeks ago, # |

← Rev. 4 →

Why does this binary search logic not work on E ?

As we keep increasing the price, there will be a price at which the number of negative reviews will be greater than K. Use binary search to find that price. Let that price be P.
Now, between 1 and P, we need to find the price at which the profit will be maximum. As we keep increasing the price, the number of customers who will buy will decrease. So, the graph of profit will look like a unimodal function (am I wrong to assume this ?), where the profit first increases then decreases. So, we can use ternary search.

Code

bool canTolerateNegativeReviews(ll price,vector<ll>&a,vector<ll>&b,ll n,ll k){
    ll count=0;
    for(ll i=1;i<=n;++i){
        count+=(price>a[i]&&price<=b[i]);
    }
    return count<=k;
}

void solve(bool printTestcase){
    ll n,k;
    cin>>n>>k;
    vector<ll>a(n+1),b(n+1);
    ll minPrice = LONG_LONG_MAX;
    ll maxPrice = LONG_LONG_MIN;
    for(ll i=1;i<=n;++i){
        cin>>a[i];
        minPrice = min(minPrice,a[i]);
    }
    ordered_set ost;
    ll timer=0;
    for(ll i=1;i<=n;++i){
        cin>>b[i];
        maxPrice = max(maxPrice,b[i]);
        ost.insert({b[i],++timer});
    }
    ll left=minPrice,right=maxPrice;
    ll maxPriceAttainable = 0;
    while(left<=right){
        ll mid = left+(right-left)/2;
        if(canTolerateNegativeReviews(mid,a,b,n,k)){
            left = mid+1;
            maxPriceAttainable = max(maxPriceAttainable,mid);
        }
        else{
            right = mid-1;
        }
    }
    ll ans = 0;
    left=0,right=maxPriceAttainable;
    while(left<=right){
        ll mid = left+(right-left)/2;
        // customers gonna buy when price is mid.
        ll cgb = n-(ost.order_of_key({mid,LONG_LONG_MIN}));
        // customers gonna buy when price is mid-1.
        ll cgb_prev = n-(ost.order_of_key({mid-1,LONG_LONG_MIN}));
        // customers gonna buy when price is mid+1.
        ll cgb_next = n-(ost.order_of_key({mid+1,LONG_LONG_MIN}));
        // profit when mid customers buy
        ll p_cgb = cgb*mid;
        // profit when mid-1 customers buy
        ll p_cgb_prev = cgb_prev*(mid-1);
        // profit when mid+1 customers buy
        ll p_cgb_next = mid!=maxPriceAttainable?cgb_next*(mid+1):LONG_LONG_MIN;
        ans = max(ans,p_cgb);
        ans = max(ans,p_cgb_prev);
        ans = max(ans,p_cgb_next);
        if(mid==maxPriceAttainable){
            right = mid-1;
        }
        else if(p_cgb<=p_cgb_next){
            left = mid+1;
        }
        else if(p_cgb_prev>=p_cgb){
            right = mid-1;
        }
        else{
            left = mid+1;
        }
    }
    ans = max(ans,0);
    cout<<ans<<endl;
}

→ Reply

4 weeks ago, # ^ |

It behaves like a piecewise constant function rather than unimodal, as the function only changes values at different values of (ai, bi). So the answer must lie in the different unique values of ai and bi, then you can use trivial binary search or do like I did, here

→ Reply

Kleaves

4 weeks ago, # ^ |

You can find that while the price is higher than the max price, there will be no customers buying, and at the same time,there will be no customers giving negative reviews. So your point 1 is wrong, because the number of negative reviews may decrease when you're higher the price.

→ Reply

https://codeforces.net/contest/2051/submission/297947353

4 weeks ago, # ^ |

← Rev. 2 →

there will be a price at which the number of negative reviews will be greater than K

This assumption is wrong, for a quick example.

3 2
1 3 5
2 4 6

→ Reply

sashshaikh12

4 weeks ago, # |

can anyone point out the reason for TLE here, is it with the manipulation of segment tree(for sums) i did or something else? ps. i know segment tree was overkill but back then during contest i was getting this approach

→ Reply

4 weeks ago, # |

-7

Multiple contestants with ChatGPT, they didn't try to hide it either, crazy: bdyby10001 NeVeDlE dikshit_barla Ak.24 donshaaab ynotme 028 budarin.028472

→ Reply

4 weeks ago, # ^ |

Update: even top 4 on the scoreboard (amhdaimm) was using it, but he participated unofficially

→ Reply

4 weeks ago, # ^ |

-24

If you got an approach, you can save the unnecessary plag attacks by using classes. Whats the big deal to cry here buddy. Listen dude, try to get the solutions from gpt for the problems. Seriously bro ? Dont blabber for no reason

→ Reply

4 weeks ago, # ^ |

-12

I guess you didn't get the meaning of competitive programming. It's all about the approach and not the syntax. If it is, we wouldn't even have stls for cpp. I hope you got it lol

→ Reply

4 weeks ago, # ^ |

my rating is several hundreds higher than yours, stop yapping bud

coding while commenting and doing it so fast? 297834073

Vladosiya please take a look and tell me if this guy is cheating or nah

→ Reply

4 weeks ago, # ^ |

-18

Coding and commenting and doing it so fast? As you can see I solved that problem which you mentioned was the first problem I solved. It took 18 minutes to solve that problem.Hahahahaha..! lol and you seriously think gpt gives typedef siu for long long. Okay try to write the same code I wrote, you will finish it in 10 minutes where I took 18 minutes.

→ Reply

4 weeks ago, # ^ |

I won't because I don't have ChatGPT coding for me

→ Reply

4 weeks ago, # ^ |

I said about typing the code.Anyways I didn’t mean to argue with you. There might be misunderstandings. Chill buddy…! I guess it’s not right to judge without knowing the behind story. So yeah have a great time, I really want to end this conversation with a good note..! Bye

→ Reply

4 weeks ago, # |

From what I see, n and m in all test cases of problem C are equal (Except for 1 case in the sample), is it intentionally weak like this?

→ Reply

Eyes_on_me

4 weeks ago, # |

← Rev. 2 →

codes of higher rated folks look similar for problem F. Is this a standard trick/idea or smth ?

→ Reply

4 weeks ago, # ^ |

which problems you mean?

→ Reply

Eyes_on_me

4 weeks ago, # ^ |

problem F

→ Reply

sho_eib_w_sho_msh_eib

4 weeks ago, # |

+15

→ Reply

tao_bo_tuc

4 weeks ago, # |

brute force and AC in F Can someone hack my code? code

→ Reply

ceciver

4 weeks ago, # ^ |

done

→ Reply

4 weeks ago, # |

If i set my price to p , all the buyers who have b>=p will buy , so regardless of how i set the price , all the people having a greater b[i] would but it. This inpires me to sort the people in non decreasing order of thier b. Consider this arrangement to be an array , now , for any price , only a suffix of the array would be buying trees. So,i will iterate on every possible suffix and see whats the best I can do. Consider the suffix i .... n-1,i aspire for all these people to buy trees I can set the price to be atmost b[i] , because more than that , the ith perosn won't be able to buy Also , i can set the price to be atmost the (k+1)th largest value in the suffix ai , ai+1 , ... an-1 , because keeping my price more than that would imply more than k bad reviews , if there are less than k+1 distinct elements in the suffix i of a , no added constraint , we can set the price to be b[I].So I set the price p to be min(b[I] , (k+1)th largest element of suffix a[I] , if any).Please note that i talk about a[i] and b[i] not in the priginal order , but in order sorted according to b in increasing order. Don't worry about the time complexity for now , just tell me is my approach optimal? I have implemented this using a fenwick tree in nlogn

Someone please point out a flaw in this approach

→ Reply

Chaeryeong

4 weeks ago, # ^ |

Your approach is correct. I didn't read the code that you submitted in contest, but I fixed the brute force implementation you submitted after. Your mistake was using std::set instead of std::multiset: https://codeforces.net/contest/2051/submission/297964342

→ Reply

https://codeforces.net/submissions/brao27

4 weeks ago, # ^ |

this was my implementation during contest,

My latest submission was just me confirming if my implantation of fenwick was not the problem and I used set instead of multisite in hurry.This is the nlogn solution , can you find the error in this?

→ Reply

https://codeforces.net/contest/2051/submission/297926479

4 weeks ago, # ^ |

this is the submission.The above link is wrong

→ Reply

Chaeryeong

4 weeks ago, # ^ |

There are a lot of details in this code that don't make sense to me. Maybe you should try rewriting it with a clear mind.

→ Reply

4 weeks ago, # ^ |

No worries, got it.

Thanks a ton.

→ Reply

christmas964

4 weeks ago, # |

Thank you very much for the round guys.

→ Reply

berojgar1905

4 weeks ago, # |

← Rev. 4 →

Can anyone find an error in the following logic for E.

First calculate the maximum price that is possible so that at most k negative reviews are received. This can be done by sorting all ai values and finding the k+1th value in the A array. Now check for all values of b which are smaller than the MAX_PRICE which we calculated earlier and then calculate the maximum revenue.

If this logic is right than why my code is not working 297928615

→ Reply

4 weeks ago, # ^ |

Since we can now see test cases, your code fails on this test

4 2
8 13 6 1
9 15 14 4

It should return 28, but returns 24.

One place your assumption is wrong is that it assumes forgets that if a customer doesn't buy a tree, they don't leave a bad review

Here's a simpler example of where your code goes wrong. The correct answer would be 1000, as the last customer would buy the tree and leave a bad review, and nobody else would buy it. However, your code returns 12, as 3 is the first value in which exceeding it would result in 2 negative reviews.

→ Reply

berojgar1905

4 weeks ago, # ^ |

Thanks for that insight

→ Reply

justsurfing

4 weeks ago, # |

Can anyone explain the logic for E in easiest way possible.

→ Reply

v-kaarti

4 weeks ago, # ^ |

← Rev. 5 →

Consider that the profit can only change at prices $$$a_i$$$ or $$$b_i$$$. You can visualize profit as a step function with steps at $$$a_i$$$ and $$$b_i$$$. Therefore we need only check these "boundary" prices. Moreover, we can efficiently calculate profit for a given price using binary search over sorted $$$a_i$$$ and $$$b_i$$$. The sorted $$$b_i$$$ will tell us the number of buyers for some price. The sorted $$$a_i$$$ will tell us the number of buyers leaving a positive review for some price. The difference between buyers and positive review buyers tells us the number of negative review buyers. We need only take the maximum profit over these boundary prices, discounting prices giving us excessive negative reviews. This results in $$$O(n*lg(n))$$$, which passes.

→ Reply

berojgar1905

4 weeks ago, # ^ |

The First idea is that the only values possible for the price of a tree are ai and bj for any i and j. The logic behind that is that if you choose any value that is neither an ai or bj then you can increase your value until your value already exists in A array or B array without getting an extra negative review or losing a customer entirely. If you understand this idea than rest is easy. For each ai and bi you can calculate the total revenue. lets set the price of a tree to be X then the number of negative reviews are the number of elements smaller than X in A array minus the number of elements that are smaller than X in B array .The customer not buying the tree will not leave a negative review. Now if for X the negative reviews are at most k than calculate the total number of people that can buy the tree * X .

CODE-297957125

→ Reply

sho_eib_w_sho_msh_eib

4 weeks ago, # |

Can we solve F using dsu?

→ Reply

https://codeforces.net/contest/2051/submission/297935184

4 weeks ago, # |

← Rev. 2 →

why below code got hacked? BledDest Mukundan314

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

It TLEs, my assumption would be that, since you convert a+b to a set first, the hack takes advantage of that and specifically chooses values of a_i and b_i such that insertion will take O(n) time (due to hash collisions), creating a total time complexity of O(n^2). There isn't really a need to convert it into a set here, while it does avoid duplicate calculations, the constraints allow for it

→ Reply

4 weeks ago, # ^ |

Thank you, so the reason is hash collision of same characters from a and b?

→ Reply

4 weeks ago, # ^ |

Same hashes, doesn't mean same values

→ Reply

4 weeks ago, # ^ |

so we python coders has to suffer like this forever? every div3 i attended atleast one solution gets hacked like this.

→ Reply

4 weeks ago, # ^ |

There are ways to get out of this (i'm ignoring the obvious "Switch to c++", which I would recommend). One way is to use a custom set implementation with guaranteed O(logN) complexity, c++ uses a red-black tree from the looks of it. Another possible solution would be to be hesitant on using it, e.g I didn't need to use it at all for A-E (though my initial thoughts for F did include using one), though this obviously isn't a great solution.

→ Reply

apex

4 weeks ago, # ^ |

Using Frequency Arrays instead of Dictionaries and Sets and Character Arrays instead of strings for PyPy is something I have learned after many Hacks and TLEs

→ Reply

4 weeks ago, # ^ |

i think its better to switch to cpp than remembering these small things while implementing

→ Reply

hiroi_kikuri

4 weeks ago, # ^ |

set(a+b)

set is $$$\mathcal{O}(n)$$$ at worse

→ Reply

4 weeks ago, # |

how to reach tourist?

→ Reply

SuperJimmy

4 weeks ago, # ^ |

You've already reached his rank :)!

→ Reply

4 weeks ago, # ^ |

I mean 4000. That rank is called tourist right?

→ Reply

_ryomen_sukuna_

4 weeks ago, # ^ |

← Rev. 2 →

It will take years of hardwork. Keep upsolving for years and hopefully u will become tourist someday.

→ Reply

bhivucoder

4 weeks ago, # |

Hey codeforces, Recently i participated in a codeforces round 995, in that contest, probably someone copied my code and hence our code matched, and that probably resulted in me being shadow banned, my rating didnt change, and others cant see my profile, kindly consider it, and remove the ban

→ Reply

4 weeks ago, # ^ |

Don't worry, your rating only changes after the hacking period is over (12 hours after the contest ends). Additionally, if someone copies your code, you will receive a notification that they found code similarity, but you will not be penalized (and I can verify that you haven't been penalized as your submissions have not been skipped)

→ Reply

i_shivammishra

4 weeks ago, # |

I participated as rated but why did I get under the unrated category please tell me.

→ Reply

apex

4 weeks ago, # ^ |

Wait for the ratings to get updated.

→ Reply

gianjuti.csecu

4 weeks ago, # |

what about penalty? = "The penalty for a wrong submission is equal to 10 minutes"

→ Reply

octopus

4 weeks ago, # |

Only real men solve E using Fenwick tree

→ Reply

bansalarpan4

4 weeks ago, # |

can someone suggest a counter test case for this sub for problem E submission — 297935805 also better if you can explain whats wrong with this implementation logic

→ Reply

AU25_AdiPassover

4 weeks ago, # |

It says:

"Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you."

However for some reason, the round wasn't rated for me. Any idea what I did wrong? I've registered a few hours before.

→ Reply

itsraajjjuuuu

4 weeks ago, # ^ |

rating will be updated in few hours

→ Reply

bhivucoder

4 weeks ago, # |

my rating is still not updated after the contest is there any kind of problem to worry or is this a bugg . if many of u are facing then let me know .

→ Reply

4 weeks ago, # |

My solution didn't pass system testing again. I'm so tired of it! You having no brain and not being able to create proper tests shouldn't be my problem!

→ Reply

4 weeks ago, # ^ |

Bruh, imagine not writing the proper code, and then blame authors for not writing proper tests. I mean sure, the tests are weak, but that doesn't change the fact that your code is wrong in the first place.

→ Reply

4 weeks ago, # ^ |

How am I supposed ro know if my code is wrong or not if it doesnt tell me properly?

→ Reply

4 weeks ago, # ^ |

The whole concept of the hacking phase is for people to hack solutions that are "slightly" wrong, or take too much time on some test cases, etc.

In the recent years, pre-tests tend to be stronger, but that doesn't mean you shouldn't verify your own logic before submitting (Or even after submitting, then you need to submit again to make sure it is accepted).

→ Reply

4 weeks ago, # ^ |

Ok then can you please tell me whats wrong with my code on C ~~~~~

include <bits/stdc++.h>

using namespace std; typedef long long ll; typedef long double ld; typedef __int128_t vl;

define pb push_back

const ll mod = 1e9 + 7; ll fpow(ll a, ll b) { if (b == 0) { return 1; } if (b == 1) { return a % mod; } if (b % 2 == 0) { return fpow((a * a) % mod, b / 2); } else { return (fpow((a * a) % mod, b / 2) * a) % mod; } } void solve() { ll n, m, k; cin >> n >> m >> k; vector q(k); vector a(m); for (int i = 0; i < m; ++i) { cin >> a[i]; } vector kn(n + 1, 0); for (int i = 0; i < k; ++i) { cin >> q[i]; kn[q[i]] = 1; } ll cz = 0; for (ll i : kn) { if (!i) { cz++; } } cz--; if (cz == 0) { for (int i = 0; i < m; ++i) { cout << 1; } } else if (cz >= 2) { for (int i = 0; i < m; ++i) { cout << 0; } } else { for (int i = 1; i <= m; ++i) { if (kn[i] == 0) { cout << 1; } else { cout << 0; } } } cout << endl; } int main() { cin.tie(nullptr), cout.tie(nullptr); ios_base::sync_with_stdio(false); ll tt = 1; cin >> tt; while (tt--) { solve(); } return 0; } ~~~~~

→ Reply

4 weeks ago, # ^ |

Pretty sure that last for loop should be this:

for (int i = 0; i < m; ++i) {
    if (kn[a[i]] == 0) {
        cout << 1;
    } else {
        cout << 0;
    }
}

→ Reply

4 weeks ago, # ^ |

I wanna jump out the window rn

→ Reply

MaxwellEqs

4 weeks ago, # |

why hasn't the rating increased ?

→ Reply

tanvir_islam

4 weeks ago, # |

This round helps to boost confidence for the beginner/intermediate level competitive programmers. Thanks authors and testers for such an exciting round.

→ Reply

4 weeks ago, # |

← Rev. 3 →

WTF about todays C , it got accepted during contest in PyPy3 and now it is Runtime error on Test 8. Even i had wrote O(1) solution. Here's my submission 297844756

→ Reply

4 weeks ago, # ^ |

k can be greater than m

→ Reply

4 weeks ago, # ^ |

So what it's nothing to do with m, but with value of n-k-1.

→ Reply

4 weeks ago, # ^ |

lol you could try some cases on your own but okay, here is the test:

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

No its nothing to do with this,this test case will pass with my code. But now i understood , i have made a terrible mistake i thought that if a[i]<a[i+1] then there must always be continuous values in array a like 1,2,3,4,... but it can be like 3,4,5,6 , which i had not considered , now i fixed it and got AC

→ Reply

4 weeks ago, # ^ |

In the test above your code literally accesses index greater than m, isn’t that a problem on python?

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

Yes there is... and that is bcz of my above explaination

→ Reply

vizuoid

4 weeks ago, # |

Where are ratings?

→ Reply

dipaR

4 weeks ago, # |

Would someone care to take a look at my submission for problem C and explain why my code outputs a non-alphanumeric character? (If it wasn't for that, I would have got it AC, as per pre-contest test cases. After the system testing, my solution somehow fails.)

→ Reply

Always_WA14

4 weeks ago, # ^ |

While taking input your array is declared as size m and you take m elements as input. But when you are printing the array, you are printing n characters, and if n>m, it will cause unexpected behaviour, i think that is why that is happening.

→ Reply

dipaR

4 weeks ago, # ^ |

Ah, of course I got hit with the classic m-n typo. Thanks for pointing that out!

→ Reply

PrimeHunter

4 weeks ago, # |

← Rev. 3 →

→ Reply

BayernForce

4 weeks ago, # |

BledDest Why the hell are the pretests so weak ? I confused m with n in Problem C(a very dumb, but a very big error nonetheless) and my wrong code passed all pretests and failed on system testing ? Kicking myself so hard now :(.

→ Reply

4 weeks ago, # ^ |

Yes, how it can so silly that even C problem of DIV.3 have such weak pretest.Even it is not failed for TLE but for wrong answer means creators did not even considered that simple test case during setting.

→ Reply

royal_div

4 weeks ago, # |

have everyone got ratings of this contest?

→ Reply

tushu06

4 weeks ago, # ^ |

not yet

→ Reply

matchaonmuffins

4 weeks ago, # ^ |

not yet

→ Reply

harsh1t_t1war1

4 weeks ago, # |

Why rating changes are taking so much time?

→ Reply

LonggVuz

4 weeks ago, # |

Optimistically I think BledDest is preparing a gift for everyone's ratings :)

→ Reply

Equation_Tracker

4 weeks ago, # |

Look how Magic made a newbie straight LGM

→ Reply

jacobinhk

4 weeks ago, # |

That was a very good contest! Really good questions. Time to upsolve!

→ Reply

4 weeks ago, # |

298058215

Can anyone tell me why my code is failing?

→ Reply

olegmak

4 weeks ago, # ^ |

Your accumulate produces int, not long long, use 0ll as initial value

→ Reply