It's a good thing that you remember to share the Editorial!

Thanks! The tasks were really interesting!

Nice~~~

Can anyone share the approach to problem C's solution using suffix array? Btw, thanks for the editorial, really helpful!

No rating rollback? There are clear cheaters in top 100

Here is a clean implementation of task C, if anyone is interested in taking a look.

void solve() {
    ll n, m; cin >> n >> m;
    vector<ll> a(m);

    for(auto &x : a) cin >> x;

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

    ll ans = 0;
    for(ll i = 1; i < n; i++) {
        ll val1 = m - (lower_bound(a.begin(), a.end(), i) - a.begin());
        ll val2 = m - (lower_bound(a.begin(), a.end(), n - i) - a.begin());
        ll val3 = m - (lower_bound(a.begin(), a.end(), max(i, n - i)) - a.begin());
        ans += (val1 * val2);
        ans -= val3;
    }

    cout << ans << "\n";
}

For problem C, there is also an $$$O(m \log m)$$$ solution (example: 311315934) which is what I did during the contest, arguably overengineering the solution.

The essential idea is that if you have two paints with indices $$$i$$$ and $$$j$$$, then you can use them to paint the fence only if $$$a_i + a_j ≥ n$$$, and if you clip the values of $$$a$$$ to $$$n - 1$$$ (because you can never paint more than $$$n - 1$$$ boards with a single color) then the number of ways to paint the fence with these two colors is $$$a_i + a_j - n + 1$$$.

That gives a trivial $$$O(m^2)$$$ solution where we consider all possible pairs of $$$i$$$ and $$$j$$$, but of course that is too slow. But we can improve this by first sorting the array $$$a$$$, then for each index $$$j$$$ you can calculate the first index $$$i \lt j$$$ such that $$$a_i + a_j ≥ n$$$, and the number of ways to paint the fence such that the right half is painted with index $$$j$$$ is $$$\sum_{k=i}^j a_k + a_j - n + 1$$$ (in my code, the result of this sum is stored in acc).

As $$$j$$$ increases, $$$i$$$ decreases. We can update the sum (acc) as we increment j and add new values of $$$i$$$ as they become available. Since in this we assume $$$k \lt j$$$ we are only counting half of the solutions, so we need to multiply the result by $$$2$$$ to obtain the final answer.

The main algorithm runs in $$$O(m)$$$ time, but since this requires sorting the array $$$a$$$ first, it's technically $$$O(m \log m)$$$ or $$$O(m + n)$$$ if you do a counting sort.

D actually doesn't require DP, and can be solved if x,y are given as binary strings of length <= 2e5.

Say we have to remove last p bits of x and last q bits of y.

For now suppose p,q are atleast 3, let r be the smallest number such that r(r+1)/2 >= p+q.

I claim the optimal way to select the numbers for the operations are 1,....r and remove r(r+1)/2-(p+q) incase p+q != r(r+1)/2.

This is clearly the minimum as we'd like to minimize the maximum number we take which will be r, and further we'd like to remove the largest possible number, if we take all numbers from 1 to r.

I didn't explicitly prove we can split them to obtain (p,q) , but it can probably proved by induction, however it fails if min(p,q) is 1 or 2 so we have to add some extra checks when min(p,q) is 0,1 or 2.

You can refer to https://mirror.codeforces.com/contest/2075/submission/311165732 for those edge cases.

Alternate solution for E: everything before $$$a_1 \oplus a_2 = b_1 \oplus b_2$$$ is the same. Now, let $$$g(n, m)$$$ denote the number of pairs $$$(i, j)$$$ such that $$$0 \le i \lt j \le n$$$ and $$$i \oplus j = m$$$.

First, I claim that $$$g(n, m) = g(n, 2^k)$$$ where $$$k$$$ is largest integer with $$$2^k \le m$$$. This is because $$$j \oplus 2^k \lt j \iff j \oplus m \lt j$$$, i.e. any number $$$j$$$ that can be xorred with $$$2^k$$$ can be xorred with $$$m$$$ and vice versa.

This already means that the number of quadruplets $$$(a_1, a_2, b_1, b_2)$$$ is $$$\sum_{k=0}^{\log \max} 2^k g(A, 2^k) g(B, 2^k)$$$, where a factor of $$$2^k$$$ comes from the fact that there are $$$2^k$$$ values of $$$m$$$ with this $$$k$$$.

All that remains is quickly evaluating $$$g(n, 2^k)$$$. This is simply the count of integers from $$$0$$$ to $$$n$$$ with $$$k$$$-th bit set because any number with the $$$k$$$-th bit on has a pair, and every pair contains exactly one number with the $$$k$$$-th bit on.

For C, can someone confirm that the following is an O(n+m) solution -- Suppose I create an array $$$cnt[]$$$ such that $$$cnt[j]$$$ denotes the number of paints that can paint at least $$$j$$$ fences (this can be done in O(n) time). Now I create another array sol[] such that

then sol[i] denotes the number of solutions to the equation

where

This can also be done in O(n) time. Then, the answer is just the sum

subtracting (2*a[i]-n+1) whenever 2*a[i]>=n (to account for x_1 and x_2 representing the same colour).

Could anyone please explain why this solution doesn't work for problem C? TIA

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lld;

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

    ll t;
    cin>>t;
    //t=1;
    while(t--){
        ll n,m;
        cin>>n>>m;
        ll num[m];
        ll pre[m]={0};
        ll ans=0;
        for(ll i=0;i<m;i++)cin>>num[i];
        sort(num,num+m);
        pre[0]=num[0];
        for(ll i=1;i<m;i++){
            pre[i]=pre[i-1]+num[i];
        }
        for(ll i=0;i<m;i++){
            ll pos=lower_bound(num+i+1,num+m,n-num[i])-num;
            ans+=(m-pos)*(num[i]+1-n)+pre[m-1]-pre[pos-1];
            //cout<<ans<<" ";
        }
        cout<<ans*2;

        cout<<"\n";

    }
    return 0;
}

GTNH is very fun, it makes my brain spin.

E can be solved using DNC too, see 311198305.

B and C were super interesting (B was particularly cheeky with the constraints). D was great as well, however I could not get it during the contest.

For C, my idea was same as the editorial, i just implemented a 2 pointer thing instead:

void twocolors(int n, int m)
{
    vector<int> a(m);
    for (int &ai : a) cin>>ai;
    sort(a.begin(), a.end());

    long long ans = 0;
    for (int i = 0, li = 0, ri = m - 1; i <= n - 2; i++)
    { // l: [0, i] (i + 1), r = [i + 1, n - 1] (n - 1 - i) 
        while (ri >= 0 && a[ri] >= n - 1 - i) ri--;
        while (li <= m - 1 && a[li] < i + 1) li++;

        long long l = m - li, r = m - ri - 1;
        ans += (l * r) - min(l, r);    
    }

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

D,E are quality problems.

The solution of F is very similar to joi2013ho5 Bubble Sort.

The ways of solving them are almost the same.

problem b could be done in O(n) using std::nth_element

code:

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int>a(n+10);
    for(int i=1;i<=n;++i)
        cin>>a[i];
    if(k==1)
    {
        int ans=a[1]+a[n];
        for(int i=2;i<n;++i)
            ans=max(ans,a[i]+max(a[1],a[n]));
        cout<<ans<<endl;
    }
    else
    {
        nth_element(a.begin()+1,a.begin()+k+2,a.end(),greater<int>());
        cout<<accumulate(a.begin()+1,a.begin()+k+2,0LL)<<endl;
    }
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

Text-

WHY IS THIS CODE GIVING TIME LIMIT EXCEEDED ERROR? WILL D NOT WORK FOR RECURSIVE SOLUTION. IF NOT WHY???

This is code- ~~~~~~~~~~~~~~~~~ long long recursion(int pw, int i, int j, vector<vector<vector>>& dp) { if (pw > 20) return 1e17; if (i == 0 && j == 0) return 0;
if (i < 0 || j < 0) return 1e17;

if (dp[pw][i][j] != -1) return dp[pw][i][j];

long long notTake = recursion(pw + 1, i, j, dp);
long long Take1 = (i >= pw) ? recursion(pw + 1, i - pw, j, dp) : 1e17;
long long Take2 = (j >= pw) ? recursion(pw + 1, i, j - pw, dp) : 1e17;

return dp[pw][i][j] = min(notTake, (1LL << pw) + min(Take1, Take2));

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

if (x == y) {
    cout << 0 << '\n';
    return;
}

if (x == 0) {
    cout << (1LL << (int(log2(y)) + 1)) << '\n';
    return;
}

if (y == 0) {
    cout << (1LL << (int(log2(x)) + 1)) << '\n';
    return;
}

vector<int> a_x, a_y;

// Convert x and y to binary representations
while (x) {
    a_x.push_back(x & 1);
    x >>= 1;
}

while (y) {
    a_y.push_back(y & 1);
    y >>= 1;
}

reverse(a_x.begin(), a_x.end());
reverse(a_y.begin(), a_y.end());

int n = a_x.size();
int m = a_y.size();
int i = 0;

// Find the first differing bit
while (i < n && i < m && a_x[i] == a_y[i]) {
    i++;
}

long long num1 = (n - i);
long long num2 = (m - i);
vector<vector<vector<long long>>> dp(20, vector<vector<long long>>(num1 + 1, vector<long long>(num2 + 1, -1)));
cout << recursion(0, num1, num2, dp) << '\n';

}

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

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

}

~~~~~~~~~~~~~~~~~~~~~

In Problem E:

Let's then count not the quadruples (a1,a2,b1,b2) , but the triples (a1,b1,x) such that 0≤a1⊕x<a1≤A and 0≤b1⊕x<b1≤B .

Reason behind that?

Can someone explain this case for B?

10 5

9 8 7 6 5 2 3 4 1 0

So, according to the tutorial, the answer would be 39, but I don't get how we would get that answer

I have a better solution of Div2 C (works in O(n+m)) 322866873

is there anyone who implemented problem D with topdown dp?