Next week's starters will be rated for Div2 as well :D

My simplest guess would be that Codechef has to pay their testers while Codeforces doesn't. Also in my experience, in addition to the tester, the contest admin usually tries a few solutions for the tougher problems and sometimes the setters try to submit bad heuristics as well so most of the time the most common incorrect solutions are covered during testing.

In my opinion the biggest problem with having only one tester is that they must be skilled enough to solve the medium / medium-hard (maybe with some hints). So the easier problems (or easier subtasks) are often trivial for them. This usually makes it difficult to construct natural incorrect heuristics when the first thing that comes to your head is the correct approach. Also with the number of problems and subtasks I suspect quite often the easiest subtasks not even tested by anyone except the problem setter beyond asserting constraints.

The same problem often arises with the problem setters who are familiar with the incorrect ideas they might have tried at first, but might miss some other extremely obvious incorrect solutions.

However one more thing to be noted is that on Codechef you're often limited to an extremely small number of test cases, so its tough to cut off a lot of incorrect solutions.

[more testers] would definitely increase the chances of fixing that I believe.

Not necessarily. When there are so many testers, none of them feels pressure to find various issues. Each of them does a worse job than if he was the only one.

More testers are good for finding multiple solutions and noticing that a problem already appeared somewhere.

Tentatively, in a couple of weeks after plag checks as per this post.

By the way, how do I receive the money using my account? I didn't make it to top-10 this month, but I still haven't received anything from the July edition.

It might be because the interactor is getting TLEd, or waiting for input for a long time.

LeetCode didn't invent this either, if you have ever heard the phrase "there are infinities of different sizes" then you have seen this construction ;)

Spot the difference between these two Chef and Closure and Beautiful Arrays xD. The same code works just changed 1 to yes 0 to no.

just binary search , feeling really amazed and enjoyed solving this problem

You can binary search. Keep a maximal set of unique indices (1.. i) such that no two indices have A[i] = A[j] , when trying for i+1 if answer is 2, binary search for the index it is equal to, otherwise add it to the set.

keep a track of indices of unique elements already found so far
whenever u reach a new index, check if its value is already present in the set of unique elements
if there isn't, we have another unique element
otherwise we will binary search on the current set and see for which value freq is 2 ie
mid=(l+r)/2
if(query_for_subset(mid,cur)==2) {ans=mid; l=mid+1}
else r=mid-1
now finally we have the index with which current value matches

This was my solution, but I suspect there was an easier way.

• Find all pairs of best / second best for each subarray (each second best can only have two possibly bests, the first larger (or equal) element in either direction, so precalc these in $$$O(n)$$$ using a stack, see this for more detail)

• Now for each pair, we fix these as the elements chef will take (lets call them $$$l_{take}$$$ and $$$r_{take}$$$), now find the max we can extend outwards from these two without changing the best or second best ($$$l'$$$ and $$$r'$$$, where $$$l' \leq l_{take} \leq r_{take} \leq r'$$$, and all elements in the range $$$[l', l_{take})$$$ and $$$(r_{take}, r']$$$ are $$$\leq min(a_{l_{take}}, a_{r_{take}})$$$. This can be found using binary search + range max query using something like sparse table).

• Then find best l where $$$l' \leq l \leq l_{take}$$$ which maximizes sum of elements in $$$[a_{l}, a_{l_{take}})$$$ using prefix sum + range max query. Do the same for the right hand side. The optimal segment for this pair is now $$$[l, r]$$$.

• This takes $$$O(log n)$$$ per pair and checks all candidate answers in a total of $$$O(n logn)$$$.

RMQ + Binary Search + Stack idea seems a bit convoluted for the solve count, is there an easier way?

#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;

const int maxn = 1e5 + 5, maxlogn = 18;

int t, n, a[maxn], lpref[maxn], rpref[maxn], lge[maxn], rge[maxn], logval[maxn], st[3][maxn][maxlogn];    
// lge / rge -> next greater than or eq element to the left (l) or right (r)

void build()
{
    logval[1] = 0;
    for(int i = 2; i <= n; i++)
        logval[i] = logval[i / 2] + 1;
    for(int i = 1; i <= n; i++)
    {
        st[0][i][0] = a[i];
        st[1][i][0] = lpref[i];
        st[2][i][0] = rpref[i];
    }
    for(int j = 1; j <= logval[n]; j++)
        for(int i = 1; i + (1 << j) <= n + 1; i++)
            for(int type = 0; type < 3; type++)
                st[type][i][j] = max(st[type][i][j - 1], st[type][i + (1ll << (j - 1))][j - 1]);
}
 
int query(int type, int l, int r)
{
    assert(l >= 1 && r <= n);
    int j = logval[r - l + 1];
    return max(st[type][l][j], st[type][r - (1ll << j) + 1][j]);
}

int get_best_sum(int l, int r, int limit)
{
    int req = lpref[r] - lpref[l - 1];
    int overcount = a[l] + a[r];
    int lans = 0, rans = 0;
    int lo = r + 1, hi = n, mid;
    while(lo < hi)
    {
        mid = (lo + hi + 1) / 2;
        if(query(0, r + 1, mid) <= limit)
            lo = mid;
        else 
            hi = mid - 1;
    }
    if(lo == hi && query(0, r + 1, lo) <= limit)
        rans = query(1, r, lo) - lpref[r];
    lo = 1, hi = l - 1, mid;
    while(lo < hi)
    {
        mid = (lo + hi) / 2;
        if(query(0, mid, l - 1) <= limit)
            hi = mid;
        else 
            lo = mid + 1;
    }
    if(lo == hi && query(0, lo, l - 1) <= limit)
        lans = query(2, lo, l) - rpref[l];
    assert(lans >= 0 && rans >= 0);
    return req + lans + rans - overcount;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    for(int cases = 0; cases < t; cases++)
    {
        cin >> n;
        for(int i = 0; i <= n + 1; i++)
        {
            lge[i] = rge[i] = -1;
            lpref[i] = rpref[i] = 0;
        }
        for(int i = 1; i <= n; i++)
            cin >> a[i];
        for(int i = 1; i <= n; i++)
            lpref[i] = lpref[i - 1] + a[i];
        for(int i = n; i >= 1; i--)
            rpref[i] = rpref[i + 1] + a[i];
        build();
        stack<pair<int, int>> geq;
        for(int i = 1; i <= n; i++)
        {
            while(!geq.empty() && geq.top().first < a[i])
                geq.pop();
            if(!geq.empty())
                lge[i] = geq.top().second;
            while(!geq.empty() && geq.top().first <= a[i])
                geq.pop();
            geq.push({a[i], i});
        }
        while(!geq.empty())
            geq.pop();
        for(int i = n; i >= 1; i--)
        {
            while(!geq.empty() && geq.top().first < a[i])
                geq.pop();
            if(!geq.empty())
                rge[i] = geq.top().second;
            while(!geq.empty() && geq.top().first <= a[i])
                geq.pop();
            geq.push({a[i], i});
        }
        int ans = -2e18;
        for(int i = 1; i <= n; i++)
        {
            if(lge[i] != -1)
                ans = max(ans, get_best_sum(lge[i], i, a[i]));
            if(rge[i] != -1)
                ans = max(ans, get_best_sum(i, rge[i], a[i]));
        }
        cout << ans << "\n";
    }
    return 0;
}

Top 100 Indian participants excluding top 10 Indian participants. (Div1)

I think you also didn't understood the problem statement. It was confusing for me. They have written "left most" and "right most"(which generally we consider as beginning or end of the array) but since they are telling left most for any index $$$l$$$ and right most for any index $$$r$$$ problem becomes the easiest one. just sort it and pick pair wise from the end satisfying the condition.

By the way can we solve it in $$$O(NlogN)$$$ or in linear if we say we have to pick from the beginning or from the end only? (like Edit distance?) This version I was trying to solve during whole contest :/

Hmm..can you elaborate? My solution was with Grey's code.

Hahaha yes! This problem was my motivation behind C2C. But it's way toned down like you also can easily exploit the range of array elements in the CF problem.

mine method : you can use max and min product of subset and then compare both max and min element of array example : int m = max product of subset , int mn = min product of subset

this concept...

then simple use:

sort(arr,arr+n);
  int  x=arr[n-1];
  int  y=arr[0];
  if(m<y || mn>x){
      cout<<0<<endl;
  }else{
      cout<<1<<endl;
  }

Thanks for the feedback! Btw, I think your opinion on C2C might be coloured by your solution — the editorials are out, and the editorial solution is clean enough to be implemented in a few minutes (in my opinion)

Thanks for the feedback! We are working on improving all parts of making contests, not everything is there yet, but we are getting better.