Please fix the code for problem G.

Similar stuff in video format :

video solutions

Really sorry the editorial took longer than usual. I'll try to post it sooner next time!

Regarding E2:- I have faced similar kind of concept in many problems "finding elements smaller or larger than current element occurring before it"... someone please tell me a source to learn __gnu_pbds::tree (or) balanced binary search tree (or) any best way to solve this.

in problem A how can it handle "BABA" case its answer should NO but according to above solution its give YES

There is a nice way to implement G with bitset. Let's do a binary search on answer. DP for checking if we can stay inside the segment of fixed length $$$m$$$ looks like this:

bitset<3000> d;
forn(i,0,m+1) d.set(i);
auto cut = d;
for(auto x : a) d = ((d>>x)|(d<<x))&cut;

Basically bit $$$i$$$ in $$$d$$$ being equal to 1 after processing some numbers from $$$a$$$ means that we could be on position $$$l+i$$$ of some segment $$$[l, r]$$$ without going out of its borders until this point. If at least one bit is 1 after this cycle then the answer is $$$>=m$$$, otherwise it's $$$<m$$$. Complexity is $$$O(n\cdot \frac{l_{max}}{64} \cdot \log(l_{max}))$$$ which is pretty much the same.

https://codeforces.net/contest/1579/submission/130289614 pls tell me why this soln for D gets WA if u have time. PS : ignore it, i got it why im getting it rong..

i wonder why this solution: https://codeforces.net/contest/1579/submission/130179380 got WA but same logic just few changes got AC:https://codeforces.net/contest/1579/submission/130194128

and above first solution is more optimized!! can someone give a TC where is fails?

I reflected a LOT on problem G and i observed the dp solution, but didnt come up with the idea that answer never exceeds 2.lmax :( beautiful problem over all.

Can you tell me how mysolution is getting a wrong answer even though I did it exactly how the editorial says . https://codeforces.net/contest/1579/submission/130186425

Alternative solution for 1579D - Productive Meeting. Think of following question: what arrays $$$a$$$ you can turn into 0? Suppose sum of $$$\sum\limits_{i=1}^n a_i = S$$$ (same as in editorial). If $$$S$$$ is odd — obviously we can't. Also, by simplest pigeonhole principle we know if there is $$$a_i > S/2$$$, then we can't reduce all $$$a_i$$$ to zero. But, if there is $$$a_i > S/2$$$ it's easy to see that it's maximum of array, and it's unique.

So idea to decrease corresponding $$$a_i$$$ in a way to make it possible to turn them into zero. To do that, calculate $$$S$$$. Find $$$a_i > S/2$$$ if it exists. And, decrease it by one while $$$a_i > S/2$$$ still holds (decrease $$$S$$$ correspondingly). Because this maximum was unique, no need to search anything else. Now $$$S$$$ can be odd, but we'll handle it later. Now, we'll make list of all participants with their repetition. So, in case $$$a$$$ = [1,2,3] we will get $$$p$$$ = [1,2,2,3,3,3]. Its length is $$$S$$$, and if it's odd, remove last one element. Now, I claim answer is pairs of $$$(p_i, p_{i + len(p)/2})$$$. The only thing to prove that is left is: $$$p_i \neq p_{i + len(p)/2}$$$, but this follows from $$$a_i \leq S/2$$$. Time complexity is $$$O(S)$$$. 130295963

When up-solving, I tried to solve Question E2. I have been getting TLE on test case 3.

Any help regarding where I went wrong would be greatly appreciated. My submission.

I was going to answer a comment with a different proof of D (always take the two largest elements) that I came up with, but it got so long that I figured it would look better here with spoilers and math mode. This is mostly a result of bashing out a ton of different cases that could happen. Feel free to point out any mistakes (which can include forgetting to format somewhere).

There are two cases (as the editorial mentions):

In problem G, Can someone explain why we are taking 0 as the leftmost boundary and never crossing that? I am stuck with this idea for two days.

Hey guys, in problem E2, I use discretion and Binary Indexed Tree to count numbers and it lead to TLE, but this solution complexity should be $$$O(nlogn)$$$, I do not know why this solution cannot ac, this is my code link

Any similar problems like problem G? I really liked the idea.

Hey guys, I've got TLE in E2, but I used multiset with lower/upper_bound which works with $$$\ O(logN) $$$ complexity. So, I guess that my submission should work with $$$\ O(NlogN) $$$ time. Here my submission 130358299, can you tell where I'm wrong.

If it does not bother you, can someone please tell me why this submission : https://codeforces.net/contest/1579/submission/130371833 gets TLE, I thought its complexity was O(n log n) as expected by the correct answer.

For Problem D, will choosing the min and max element at each turn, work similar ?

Problem $$$F$$$ can be solved using $$$Binary\ Lifting$$$ although it is not optimal.

About the problem E2, I see someone write the solution like this:

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n,a[N],b[N];
long long c[N];
long long ans=0;
int lowbit(int x){return x&-x;}
void add(int x){
    while(x<=n){
        c[x]++;x+=lowbit(x);			
    }
}
long long query(int x){
    long long ans=0;
    while(x){
        ans+=c[x];x-=lowbit(x);
    }
    return ans;
}
int main(){
	
    cin>>t;
    while(t--){
        cin>>n;ans=0;
        for(int i=1;i<=n;i++)	cin>>a[i],c[i]=0,b[i]=a[i];
        sort(b+1,b+1+n);
        int len=unique(b+1,b+1+n)-b-1;
        for(int i=1;i<=n;i++)	a[i]=lower_bound(b+1,b+1+len,a[i])-b;
		
        for(int i=1;i<=n;i++){
            long long cur=min(query(a[i]-1),query(n)-query(a[i]));
            ans+=cur;
            add(a[i]);
        }	
        cout<<ans<<"\n";
    }
	
	
	
    return 0;
}

I guess the query() and add() operation is to calculate some like partial sum or adjacent difference, but I don't understand how and why, can someone explain that? Thank you!

Can anyone help me find why my code for D is failing? Any edge cases I need to check for? It always fails on tc 69.Anyone knows what that tc is :( ? https://codeforces.net/problemset/submission/1579/130623552 I did as said in editorial. Used a pq for choosing two persons with max sociability.

for D, will the following algorithm work? : " Choosing two people i and j such that ith person has maximum remaining sociability and j can be any other person with non zero sociability and stop this process when less than 2 people are left with non zero sociability "

if ai≥S−ai, the answer cannot be more than (S−ai)+∑j≠iaj=2⋅(S−ai).

In first point of Problem-D editorial, How is this true?

Graphical Solution for problem F is

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " " << x << endl;
#else
#define debug(x);
#endif

#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define sortall(x) sort(all(x))



using ll = long long;
const int MOD = 1e9 + 7, INF = 1e9;

/*---------------------------------------------------------------------------------------------------------------------------*/
ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
ll mod_add(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_div(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
/*--------------------------------------------------------------------------------------------------------------------------*/


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while(tt --)
    {
        int n, d;
        cin >> n >> d;
        vector<int>v(n);
        for(int i = 0 ;  i < n; i++) cin >> v[i];
        vector<int>v1;
        set<int>st;
        for(int i = 0; i < n; i++)
        {
            if(v[i] == 0)
            {
                v1.push_back(i);
            }
            else st.insert(i);
        }
        int ans = -1;
        for(auto it : v1)
        {
            int k = 1;
            while(st.find((it + k * d) % n) != st.end())
            {
                st.erase(st.find((it + k * d) % n));
                k++;
            }
            ans = max(ans, k - 1);
        }
        if(st.empty()) cout << ans << endl;
        else cout << -1 << endl;
    }
}