Well, that was a blast, certainly. I hope that you... learned a lot from the contest. I wouldn't say "enjoy the contest", I know most of you hate geometry, I get you. But please do remember that, at least I did try my best to make every problem as high quality as possible. Like, if you don't get familiar with thinking about geometry now, you might never get familiar with it in the future. Though I apologize that E was quite hard, I suggest you to upsolve or read the editorials of the tasks you could not solve. I am telling you, it will be an experience that will make you improve much more from now.

Solution codes will be posted after the open hack phase. They are now added.

2074A - Draw a Square

for i in range(int(input())):
    l,r,d,u=map(int,input().split())
    if l==r==d==u:
        print("Yes")
    else:
        print("No")

2074B - The Third Side

t = int(input())
for _ in range(t):
    n = int(input())
    sm = sum(map(int, input().split()))
    print(sm - n + 1)

2074C - XOR and Triangle

t = int(input())
for _ in range(t):
    x = int(input())
    ans = -1
    for i in range(30):
        for j in range(30):
            y = (1 << i) | (1 << j)
            if y < x and x + y > (x ^ y) and y + (x ^ y) > x:
                ans = y
    print(ans)

2074D - Counting Points

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
int main()
{
    int t;cin>>t;
    for(int i=0;i<t;i++)
    {
        int n,m;cin>>n>>m;
        map<ll,ll>cnt;
        auto isqrt=[&](ll x)
        {
            ll val=sqrtl(x)+5;
            while(val*val>x)val--;
            return val;
        };
        vector<ll>a(n),r(n);
        for(ll&i:a)cin>>i;
        for(ll&i:r)cin>>i;
        for(int i=0;i<n;i++)
        {
            ll aa=a[i],rr=r[i];
            for(ll x=aa-rr;x<=aa+rr;x++)
            {
                cnt[x]=max(cnt[x],2*isqrt(rr*rr-(x-aa)*(x-aa))+1);
            }
        }
        ll ans=0;
        for(auto[x,c]:cnt)ans+=c;
        cout<<ans<<"\n";
    }
}

2074E - Empty Triangle

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    mt19937 mt(727);
    uniform_int_distribution uni(1,3);
    int tc;cin>>tc;
    while(tc--)
    {
        int n;cin>>n;
        if(n<0)return 0;
        vector<int>vec(n);
        for(int i=0;i<n;i++)vec[i]=i+1;
        shuffle(begin(vec),end(vec),mt);
        int ii=vec[0],jj=vec[1],kk=vec[2];
        cerr<<n<<endl;
        while(1)
        {
            cout<<"? "<<ii<<" "<<jj<<" "<<kk<<endl;
            int id;cin>>id;
            if(id<0)return 0;
            if(id==0)break;
            int sw=uni(mt);
            if(sw==1)ii=id;
            else if(sw==2)jj=id;
            else kk=id;
        }
        cout<<"! "<<ii<<" "<<jj<<" "<<kk<<endl;
    }
}

2074F - Counting Necessary Nodes

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
int main()
{
    int t;cin>>t;
    for(int i=0;i<t;i++)
    {
        int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;
        vector<pair<ll,ll>>it1,it2;
        auto rec=[&](auto rec,int L,int R,int l,int r,vector<pair<ll,ll>>&v)->void
        {
            if(r<=L||l>=R)return;
            if(l<=L&&R<=r)
            {
                v.emplace_back(L,R);
                return;
            }
            rec(rec,L,(L+R)/2,l,r,v);
            rec(rec,(L+R)/2,R,l,r,v);
        };
        rec(rec,0,1<<25,l1,r1,it1);
        rec(rec,0,1<<25,l2,r2,it2);
        ll ans=0;
        for(auto[al,ar]:it1)
        {
            for(auto[bl,br]:it2)
            {
                ll a=ar-al,b=br-bl;
                if(a<b)swap(a,b);
                ans+=a/b;
            }
        }
        cout<<ans<<"\n";
    }
}

2074G - Game With Triangles: Season 2

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
ll dp[505][505];
 
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t;cin>>t;
    for(int tc=0;tc<t;tc++)
    {
        ll n;cin>>n;
        vector<ll>vec(n);
        for(ll&i:vec)cin>>i;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)dp[i][j]=-1e18;
        }
        auto value=[&](ll i,ll j,ll k)
        {
            return i*j*k;
        };
        for(int len=1;len<=n;len++)
        {
            for(int L=0;L<n;L++)
            {
                ll ans=0;
                ll R=(L+len-1)%n;
                if(len<=2)
                {
                    dp[L][R]=0;
                    continue;
                }
                if(len==3)
                {
                    dp[L][R]=max(0LL,value(vec[L],vec[(L+1)%n],vec[R]));
                    continue;
                }
                for(int i=(L+1)%n;i!=R;i=(i+1)%n)
                {
                    ll val=value(vec[L],vec[i],vec[R]);
                    if(i!=(L+1)%n)val+=dp[(L+1)%n][(i+n-1)%n];
                    if(i!=(R+n-1)%n)val+=dp[(i+1)%n][(R+n-1)%n];
                    ans=max(ans,val);
                }
                for(int i=L;i!=R;i=(i+1)%n)
                {
                    ans=max(ans,dp[L][i]+dp[(i+1)%n][R]);
                }
                dp[L][R]=ans;
            }
        }
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            ans=max(ans,dp[i][(i+n-1)%n]);
        }
        cout<<ans<<"\n";
    }
}

Oh hello there. This is chromate00, just casually on the announcement of Codeforces Round 1009 (Div. 3). And now, you see a drawing.

$$$\square$$$ — $$$\triangle$$$ — $$$\triangle$$$ — ◯ — $$$\triangle$$$ — $$$\square$$$ — $$$\triangle$$$

And then, you think. You see a square, a triangle, and a circle. Also, a Korean problemsetter. You immediately imagine the certain survival game that popped up in your memory. And you may be right. Or you might be wrong. Whatever, what I can ensure you is that you will be absolutely stunned to see the problems. Or astonished. You might not believe what you see. This round might change everything.

Anyways, the preface was a bit too long. Starting from Mar/11/2025 17:35 (Moscow time), you will be given $$$\mathbf{7}$$$ problems to be solved in $$$\mathbf{2.5}$$$ hours. There is at least one interactive problem, so I strongly urge you to read the guide if you are unfamiliar with the format.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, all solutions will be judged on preliminary tests during the round, and after the round, there will be a 12-hour phase of open hacks. After the open hack phase, all accepted solutions will be rejudged on successful hacks. Also, note that there is no score distribution but the usual penalty of 10 minutes for each wrong submission, following the rules of educational rounds.

Remind yourself that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them)
• not have a rating of 1900 or higher at any moment in time.

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 (unless you register unrated).

Also, note the (relatively recent) rule restricting the use of AI. If you are caught while breaking this rule, you will be terminated.

This round is made possible by the help of the following people:

• cry and Vladosiya for coordinating the round (and translating the statements),
• Proof_by_QED for reviewing the tasks (and not so particularly testing them),
• Our army of (not so) pink soldiers: Intellegent, amoeba4, mathtsai, Error_Yuan, temporary1, Edeeva, yeetholmes619, hashman, larush, poi, (VIP) Dominater069, (VIP) LMeyling, (VIP-) macaquedev, antontrygubO_o, Mercuria, DivinePunishment, 0pt1mus23, pianapolataa, reirugan, efishel, (VIP) awesomeguy856, rewhile, __baozii__, yoru_sacri, -firefly-, sbreger60, monadtransformer, Rahuldeb5,
• The VVVIP, MikeMirzayanov, for great platforms Codeforces and Polygon.

I hope that you will also be in the spectacular moment.

UPD: Editorial has been posted.

UPD2: Congratulations to the top participants definitely except for the ones who cheated their way out!

All participants:

1. ksun48
2. arvindf232
3. StarSilk
4. maspy
5. risujiroh

Trusted (rated) participants:

1. sharvil_cpp
2. Xing_Kong_C......has been terminated
3. jxu
4. 1zaid1
5. eysikingE
6. I_am_the_Lowest
7. ConvexHulllllll

Hello Codeforces, and the legends of across $$$999$$$ and more rounds!

wuhudsm, Yugandhar_Master, and I are beyond excited to invite you to Codeforces Round 1000 (Div. 2) at Jan/22/2025 15:05 (Moscow time). Please note the unusual time of the round ($$$\color{red}{2.5}$$$ hours before the usual time)!

The contest contains $$$6$$$ carefully crafted tasks, one of them divided into two subtasks, to be solved in $$$2$$$ hours. You will solve tasks themed around Little John and his shenanigans aimed towards getting his own dream home (featuring, probably, galvanized square steel).

This round could not exist without the thankful help of these so many people:

• FairyWinx for rejecting more tasks than are used in the final problemset, coordinating the round and translating the problems;
• rewhile for some very important "technical assistance";
• the testers of Codeforces Round 960 (Div. 2), who had tested a non-empty subset of the problemset;
• antontrygubO_o for nutella testing;
• Dominater069, _istil, Error_Yuan, Monogon, awesomeguy856 for red testing;
• defnotmee, Proof_by_QED, -firefly-, Intellegent, efishel, priyanshu.p, amoeba4, evenvalue, cry, LMeyling, temporary1 for yellow testing;
• Wxssim, HusseinFarhat, Mukundan314, turska, rewhile, redheadphone for purple testing;
• Dragokj03, VladiG, b00s, SirPh, mathtsai, hashman, redpanda, larush, satyam343, antares2262, ismailfateen for blue testing;
• Valenz, shuniko for cyan testing;
• Dominater069 for identifying as green;
• tibinyte2006 for legendary-fake-lying-face grey testing;
• a few people who were invited to test but forgot/didn't have time for it;
• a few people who tested $$$\mathcal{O}(1)$$$ tasks individually but not the entire problemset;
• MikeMirzayanov for great platforms Codeforces and Polygon;
• and last but not least, You for participating! Thank you for writing legends in real-time for across $$$999$$$ and more rounds!

The score distribution is as follows.

Before finishing the announcement, I would like to spoil you a little of how the round's story ends.

Little John worked hard, honest and diligent for years, and finally got a home of his dream.

In that sense, I want You to be like Little John in this round.

Hard, honest and diligent will give you the rewards you deserve.

Anyways, that's all for the announcement; Good luck, and have fun!

UPD1: The score distribution has been announced.

UPD2: The editorial is posted here. Also we have good news that I will post as a separate report blog soon...

UPD3: Congratulations to the winners!

All participants:

1. sunjia (oops, the user is gone now)
2. Golovanov399
3. maspy
4. jiangbowen
5. A_G
6. fnoihzhyan

Rated only:

1. sunjia (oops, the user is gone now)
2. fnoihzhyan
3. RGB_ICPC9
4. wangzirui123
5. Network_Error
6. BSpioneer

UPD4: Anti-LLM Evaluation Report is published — the first of its kind for Div.2! Please kindly take a look if you have some free time or are just interested.

The editorial for each task is written by me, chromate00. I tried to explain each task with as much detail I could fit in. Brace yourselves, it is going to be LONG. Please don't try to open all spoilers at once, it lagged my browser. Also, I apologize for not telling you strongly enough to read every problem, almost every tester thought F1 is easy if you read it well...

Also, our fellow wuhudsm told me there will be another community contest in the Gym soon, details will be posted on https://codeforces.me/blog/entry/138706 shortly :catThink:

UPD: Added solution codes to all solutions.

2063A - Minimal Coprime

Author: chromate00

for i in range(int(input())):
    x,y=map(int,input().split())
    if x==y==1:
        print(1)
    else:
        print(y-x)

2063B - Subsequence Update

Author: Yugandhar_Master

import sys
input=lambda:sys.stdin.readline().rstrip()
 
for _ in range(int(input())):
    n,l,r=map(int,input().split());l-=1
    arr=[*map(int,input().split())]
    brr=arr[:l]+sorted(arr[l:])
    crr=sorted(arr[:r])[::-1]+arr[r:]
    print(min(sum(brr[l:r]),sum(crr[l:r])))

2063C - Remove Exactly Two

Author: chromate00

import sys
input=lambda:sys.stdin.readline().rstrip()
for i in range(int(input())):
    n=int(input())
    deg=[0]*n
    adj=[[] for i in range(n)]
    for i in range(n-1):
        u,v=map(int,input().split())
        u-=1;v-=1
        deg[u]+=1
        deg[v]+=1
        adj[u].append(v)
        adj[v].append(u)
    ans=1
    mans=0
    sdeg=sorted(deg)
    for i in range(n):
        ans=deg[i]
        ideg=[]
        for v in adj[i]:
            ideg.append(deg[v])
        ideg.append(deg[i])
        ideg.sort(reverse=True)
        rem=[]
        mx=-1
        for d in ideg:
            if sdeg[-1]==d:
                sdeg.pop()
                rem.append(d)
        rem.reverse()
        if sdeg:
            mx=max(mx,sdeg[-1])
        for v in adj[i]:
            mx=max(mx,deg[v]-1)
        for d in rem:
            sdeg.append(d)
        mans=max(ans+mx-1,mans)
    print(mans)

2063D - Game With Triangles

Author: wuhudsm (Original Idea) & chromate00 (Modified Idea)

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
int main()
{
  cin.tie(0)->sync_with_stdio(0);
  int t;cin>>t;
  while(t--)
  {
    int n,m;cin>>n>>m;
    vector<ll>arr(n),brr(m);
    for(ll&i:arr)cin>>i;
    for(ll&i:brr)cin>>i;
    sort(begin(arr),end(arr));
    sort(begin(brr),end(brr));
    vector<ll>asum(n+2),bsum(m+2);
    for(int i=1;i<=n;i++)asum[i]=asum[i-1]+(arr[n-i]-arr[i-1]);
    for(int i=1;i<=m;i++)bsum[i]=bsum[i-1]+(brr[m-i]-brr[i-1]);
    vector<ll>ans{0};
    // maximize asum[ka]+bsum[kb]
    // s.t. ka+kb = x
    //      ka*2+kb <= n -> ka*2+(x-ka) <= n -> ka+x <= n   -> ka <= n-x
    //      ka+kb*2 <= m -> ka+2*(x-ka) <= m -> 2*x-ka <= m -> ka >= 2*x-m
    //      ka >= 0, x-ka >= 0
    for(int x=1;2*x-m<=n-x;x++)
    {
      ll L=max(0,2*x-m),R=min(x,n-x);
      if(L>R)break;
      auto f=[&](int ka){return asum[ka]+bsum[x-ka];};
      while(R-L>3)
      {
        ll mL=(L*2+R)/3,mR=(L+R*2)/3;
        if(f(mL)>f(mR))R=mR;
        else L=mL;
      }
      ll mans=0;
      for(int i=L;i<=R;i++)
      {
        mans=max(mans,f(i));
      }
      ans.push_back(mans);
    }
    int kmax=(int)size(ans)-1;
    cout<<kmax<<"\n";
    for(int i=1;i<=kmax;i++)cout<<ans[i]<<" \n"[i==kmax];
  }
}

2063E - Triangle Tree

Author: Yugandhar_Master

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

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t;cin>>t;
    while(t--)
    {
        ll n;cin>>n;
        vector<ll>d(n,0),s(n),dc(n),dcs;
        vector<vector<ll>>adj(n);
        for(int i=1;i<n;i++)
        {
            int u,v;cin>>u>>v;
            u--;v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        auto dfs1=[&](auto dfs1,int v,int p=-1)->void
        {
            dc[d[v]]++;
            ll sz=1;
            for(int w:adj[v])if(w!=p)
            {
                d[w]=d[v]+1;
                dfs1(dfs1,w,v);
                sz+=s[w];
            }
            s[v]=sz;
        };
        dfs1(dfs1,0);
        dcs=dc;
        for(int i=n-2;i>=0;i--)dcs[i]+=dcs[i+1];
        ll ans=0,ans2=0;
        auto dfs2=[&](auto dfs2,int v,int p=-1)->void
        {
            // v is min
            ans+=2*d[v]*(dcs[d[v]]-s[v]);
            // v is lca
            ll subcnt=s[v]-1,lcnt=0;
            for(int w:adj[v])if(w!=p)
            {
                lcnt+=(subcnt-s[w])*s[w];
                dfs2(dfs2,w,v);
            }
            ans2+=(2*d[v]+1)*(lcnt/2);
        };
        dfs2(dfs2,0);
        for(int i=0;i<n;i++)
        {
            ans2+=i*dc[i]*(dc[i]-1);
        }
        cout<<ans-ans2<<"\n";
    }
}

2063F1 - Counting Is Not Fun (Easy Version)

Author: chromate00

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll md=998244353;
 
int main()
{
    int t;cin>>t;
    vector<ll>ctl(5050);
    ctl[0]=1;
    for(int n=1;n<5050;n++)
    {
        for(int i=1;i<=n;i++)
        {
            ctl[n]=(ctl[n]+ctl[i-1]*ctl[n-i]%md)%md;
        }
    }
    while(t--)
    {
        int n;cin>>n;
        ll ans=ctl[n];
        cout<<ans<<" ";
        string s(2*n+2,'.');
        s[0]='(';s[2*n+1]=')';
        for(int a=0;a<n;a++)
        {
            int i,j;cin>>i>>j;
            ans=1;
            s[i]='(';
            s[j]=')';
            string stk;
            for(char c:s)
            {
                if(c==')')
                {
                    int cnt=0;
                    while(stk.back()!='(')
                    {
                        cnt++;
                        stk.pop_back();
                    }
                    stk.pop_back();
                    ans=(ans*ctl[cnt/2])%md;
                }
                else stk+=c;
            }
            cout<<ans<<" \n"[a+1==n];
        }
    }
}

2063F2 - Counting Is Not Fun (Hard Version)

Author: chromate00

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll nil=-1;
const ll md=998244353;
 
ll pw(ll a,ll b)
{
    ll c=1;
    while(b>0)
    {
        if(b&1)c=c*a%md;
        a=a*a%md;
        b>>=1;
    }
    return c;
}
 
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    vector<ll>fac(1010101,1),ctl(505050);
    for(int i=1;i<1010101;i++)fac[i]=fac[i-1]*i%md;
    for(int i=0;i<505050;i++)
    {
        ctl[i]=fac[i*2]*pw(fac[i]*fac[i+1]%md,md-2)%md;
    }
    ll t;cin>>t;
    while(t--)
    {
        ll n;cin>>n;
        vector<ll>L(n*2,nil),R(n*2,nil),P(n*2,nil),S(n*2);
        auto update=[&](ll x)
        {
            S[x]=1;
            if(L[x]!=nil)S[x]+=S[L[x]];
            if(R[x]!=nil)S[x]+=S[R[x]];
        };
        auto rotate=[&](ll x)
        {
            ll dummy;
            ll p=P[x];
            ll b=nil;
            if(p==nil)return;
            if(x==L[p])
            {
                L[p]=b=R[x];
                R[x]=p;
            }
            else
            {
                R[p]=b=L[x];
                L[x]=p;
            }
            P[x]=P[p];P[p]=x;
            if(b!=nil)P[b]=p;
            (P[x]!=nil?p==L[P[x]]?L[P[x]]:R[P[x]]:dummy)=x;
            update(p);update(x);
        };
        auto splay=[&](ll x)
        {
            while(P[x]!=nil)
            {
                ll p=P[x];
                ll g=P[p];
                if(g!=nil)
                {
                    if((x==L[p])==(p==L[g]))rotate(p);
                    else rotate(x);
                }
                rotate(x);
            }
        };
        update(0);
        for(int i=1;i<n*2;i++)
        {
            L[i]=i-1;
            P[i-1]=i;
            update(i);
        }
        splay(0);
        ll ans=ctl[n];
        cout<<ans<<" ";
        for(int i=0;i<n;i++)
        {
            ll li,ri;cin>>li>>ri;
            //li=(li+ans%(2*n))%(2*n);
            //ri=(ri+ans%(2*n))%(2*n);
            li--;ri--;
            splay(li);
            ans=ans*pw(ctl[S[li]/2],md-2)%md;
            ll lli=L[li];
            if(L[li]!=nil)P[L[li]]=nil;
            if(R[li]!=nil)P[R[li]]=nil;
            L[li]=nil;
            R[li]=nil;
            update(li);
            // now L[li] separated from tree
            // should not be affected in splay ri
            splay(ri);
            ll lri=L[ri];
            ll rri=R[ri];
            if(L[ri]!=nil)P[L[ri]]=nil;
            if(R[ri]!=nil)P[R[ri]]=nil;
            L[ri]=nil;
            R[ri]=nil;
            update(ri);
            if(lri!=nil)
            {
                splay(lri);
                ans=ans*ctl[S[lri]/2]%md;
            }
            if(lli!=nil&&rri!=nil)
            {
                while(L[rri]!=nil)rri=L[rri];
                splay(lli);
                splay(rri);
                P[lli]=rri;
                L[rri]=lli;
                update(rri);
                ans=ans*ctl[S[rri]/2]%md;
            }
            else if(lli!=nil||rri!=nil)
            {
                if(lli!=nil)
                {
                    splay(lli);
                    ans=ans*ctl[S[lli]/2]%md;
                }
                else
                {
                    splay(rri);
                    ans=ans*ctl[S[rri]/2]%md;
                }
            }
            L[ri]=li;
            P[li]=ri;
            update(ri);
            // make dummy tree (for invariant maintaining)
            cout<<ans<<" \n"[i+1==n];
        }
    }
}

UPD: People pointed out that the intended solution in the tutorial is overkill. Yes, I acknowledge this. Please look into the newly added alternative solution if you want a more elegant idea.

#pragma GCC optimize("O3,unroll-loops")

#include <iostream>
#include <numeric>
#include <vector>

constexpr int MAX_N = 3e5;
constexpr long long MOD = 998244353;

struct _inv_small {
  long long data[MAX_N + 2] = {0};
  constexpr _inv_small() {
    data[1] = 1;
    for (int i = 2; i <= MAX_N; i += 2) {
      data[i] = MOD - (MOD / i) * data[MOD % i] % MOD;
      data[i + 1] = MOD - (MOD / (i + 1)) * data[MOD % (i + 1)] % MOD;
    }
  }
};

constexpr _inv_small __inv_small;
#define inv_small(x) __inv_small.data[x]

#define inv(x) (x < MAX_N ? inv_small(x) : data[(x) - MAX_N])
struct _inv {
  long long data[MAX_N + 3] = {0};
  constexpr _inv() {
    for (int i = 0; i <= MAX_N + 1; i += 2) {
      data[i] = MOD - (MOD / (i + MAX_N)) * inv(MOD % (i + MAX_N)) % MOD;
      data[i + 1] = MOD - (MOD / (i + MAX_N + 1)) * inv(MOD % (i + MAX_N + 1)) % MOD;
    }
  }
};
#undef inv

constexpr _inv __inv;
#define inv(x) (x < MAX_N ? inv_small(x) : __inv.data[(x) - MAX_N])

struct _catalan {
  long long data[MAX_N + 2] = {1};
  constexpr _catalan() {
    for (int i = 1; i <= MAX_N; i += 2) {
      data[i] = (4 * i - 2) * data[i - 1] % MOD * inv(i + 1) % MOD;
      data[i + 1] = (4 * i + 2) * data[i] % MOD * inv(i + 2) % MOD;
    }
  }
};

constexpr _catalan __catalan;
#define catalan(x) __catalan.data[x]

struct _catalan_inv {
  long long data[MAX_N + 2] = {1};
  constexpr _catalan_inv() {
    for (int i = 1; i <= MAX_N; i += 2) {
      data[i] = inv(2) * inv(2 * i - 1) % MOD * data[i - 1] % MOD * (i + 1) % MOD;
      data[i + 1] = inv(2) * inv(2 * i + 1) % MOD * data[i] % MOD * (i + 2) % MOD;
    }
  }
};

constexpr _catalan_inv __catalan_inv;
#define catalan_inv(x) __catalan_inv.data[x]

int main() {
  std::cin.tie(0)->sync_with_stdio(0);

  int t;
  std::cin >> t;

  for (int _ = 0; _ < t; ++_) {
    int n;
    std::cin >> n;

    std::vector<bool> used(2 * n + 2);

    std::vector<int> point(2 * n + 2);
    std::iota(point.begin(), point.end(), 1);

    std::vector<int> size(2 * n + 2);

    std::vector<int> parent = {0};
    std::vector<int> parent_idx(2 * n + 2);

    used[0] = true;
    point[0] = 2 * n + 2, point[2 * n + 1] = 2 * n + 1;
    size[0] = 2 * n;

    long long ans = catalan(n);

    std::cout << ans << " ";

    for (int i = 0, l, r; i < n; ++i) {
      std::cin >> l >> r;

      point[l] = r + 1, point[r] = r;
      used[l] = true;

      int p = parent[parent_idx[l]];

      int out_ptr = p + 1, ins_ptr = l + 1;
      int out_size = 0, ins_size = 0;

      while (point[out_ptr] != out_ptr && point[ins_ptr] != ins_ptr) {
        out_size += !used[out_ptr];
        ins_size += !used[ins_ptr];
        out_ptr = point[out_ptr];
        ins_ptr = point[ins_ptr];
      }

      ans = (ans * catalan_inv(size[p] / 2)) % MOD;

      int upd_ptr;
      if (point[out_ptr] == out_ptr) {
        upd_ptr = p + 1;
        parent.push_back(p);
        parent[parent_idx[l]] = l;

        ins_size = size[p] - 2 - out_size;
        size[p] = out_size, size[l] = ins_size;
      } else {
        upd_ptr = l + 1;
        parent.push_back(l);

        out_size = size[p] - 2 - ins_size;
        size[p] = out_size, size[l] = ins_size;
      }

      ans = (ans * catalan(size[p] / 2)) % MOD * catalan(size[l] / 2) % MOD;

      while (point[upd_ptr] != upd_ptr) {
        parent_idx[upd_ptr] = parent.size() - 1;
        upd_ptr = point[upd_ptr];
      }

      std::cout << ans << " ";
    }

    std::cout << '\n';
  }
}

As the main problemsetter of Codeforces Round 1000 (Div. 2), I know that a lot of you were somewhat disappointed to see that it was not a Div.1 contest. Though I am not the one who caused a lack of Div.1 contests, I understand your feeling. So I present to you the great surprise: The Anti-LLM Evaluation Report for Codeforces Round 1000 (Div. 2), the first of its kind on a Div.2! In this blog we discuss about how the round combats against LLMs (especially focusing on OpenAI o1, the greatest of its kind while we prepared and tested the problemset), by looking at the timeline of how the problemset changed.

So, let us begin with the initial problemset we had when the testing began. (The task names are anonymized, unless they are released to the public before or in the round)

In the beginning, we had a problemset that looks like this:

• A' — B — C0 — D' — E' — F0

(If you are confused with the meanings, (letter)' means it was not used in the final problemset but existed, while (letter)0 means that it appeared in the final problemset in a different form.)

So, you may see, at least half of the problemset has changed in the testing phase. How did o1 do against this revision of our problemset?

• A': Not Solved.
• B: Not Solved.
• C0: Solved.
• D': Not Solved.
• E': Not Solved.
• F0: Not Solved.

Okay, so it already was a bit strong against o1, but C0 being solved by LLMs while A' being not solved looked too odd to me. It felt like LLMs would get a too large unfair advantage if it was kept this way.

Now, the timeline of the problemset begins. (Note that the timeline is purely based on my memory and whatever information is left in the testing mashup)

• The first task to get swapped was A'. A lot of testers felt A' a bit too hard for its position, and we had to find a new one. Luckily, we found A'', and swapped A' with it. A'' was solved by o1. But we believed that would be fine if we could find a replacement to C0 that isn't solved by LLMs. Back on that later.

• The second task to get swapped was F0. F0 was a version of F that only asks for uniqueness. It was interactive, and we didn't really have a good way to force them to solve online. And there were unexpected solutions even in the online setting, so we made F that asks for counting, and split it to two subtasks. As you might expect, F was not solved by o1.

• The third task to get swapped was C0. We swapped it out for C' initially, but the testers did not like it (probably it was too hard for its position), and we swapped it back to C0. C' was not used afterwards, and it was not evaluated against LLMs either.

It was very hard to find a replacement for C0. Until...

• We found C. It was just a random idea I pulled while ranting about how hard it is to make tasks on the position. But somehow, very surprisingly, it was not solved by o1. I am still surprised about how o1 cannot solve it, don't ask us, go ask Sam Altman instead. Anyways, this replaced C0. Very lucky!

• At this point, most people struggled on E'. We decided that it is not a good fit for the position. As a replacement, we found E and replaced E' with it. Thankfully, the testers pointed out that it's just the fine difficulty for the position. And it's also not solved by o1. Another good one. Later, E' became COUNTGOOD on CodeChef Starters 167.

• Some time after that, some testers pointed out that D' is very similar to a task from GCJ. But worry not, we have discussed this out to balance the difficulty for a long time. Surprise: C0 became buffed to D. And it is now not solved by o1! Nice.

Around this time, I asked rewhile to test. He knew better about prompting LLMs, so I asked explicitly to test only using o1 (and he gladly accepted). Here was the result.

• A'': AC
• B: -11
• C: -4
• D: -2
• E: -1
• F (Easy): -2
• F (Hard): -1

So yes, I believed that o1 will die horribly if it's the same way.

• After this, I just changed A'' to A, which was much easier than A'' for humans. It is solved by o1, but it's fine now.

There are some omitted changes also (Such as a task proposed for Div2D but rejected immediately after I found that it's a Div2B), but these are all of the significant changes.

So the final result for o1 is as follows.

• Expected Score: $$$498$$$.
• Corresponding Rating: 911 (762 rating points less than the 1673, initially claimed by OpenAI)

The point we need to focus on is that, when these LLMs came out, people thought it's the end of the world for Div.2, but not yet! It might not be the end of the world! But it takes more effort to combat them. Here are some things I found, as a guidance for problemsetters who want to make your Div.2 contest strong against LLM.

• You might have noticed, the round has significantly different problem styles compared to the usual Div.2; that might have helped combat them.
• Maybe it could be time to change the meta again, after the last time it changed, which was probably when 1188B - Count Pairs appeared? I don't know. Up to the next Div.2 problemsetters to decide.
• In terms of problem style, problems that require multiple small observations will be generally more robust against LLMs than those that require one or two big observations. Stronger LLMs usually get one or two first observations correct. Making more small observations will make them also suffer from limit on number of tokens. For example, on problem C, o1 got the immediate first observation, but got WA by choosing the first $$$k=\mathcal{O}(\sqrt{n})$$$ and bruteforcing $$$k \choose 2$$$ pairs.
• It will require you significantly more effort to make easier tasks than to make hard tasks. Position C required us more effort than position F required us. For harder tasks you can care less if your task isn't extremely classic or already known, which I assume is usually not the case.

Maybe for a few things noted I might be not the closest to the ground truth. Tell me in comments if you need to point something out.

Also, for cheaters that tried to use o1:

I gave you a hint already. I hope you learn from negative delta, and become honest and diligent again. I hope you are a sane person. I, myself, truly improved only after moving on over bad behaviour. Yes, I had cheated back in the days, and now I became as honest as one could. I believe you can be better also.

Please take this opportunity as a lesson.

Thank you for reading.

Two days ago, the Div.3 (Codeforces Round 938 (Div. 3)) suffered from severe issues of hacks, because the problem G (1955G - GCD on a grid) did not have proper validation for the sum of $$$nm$$$ in hacks, which was specified as at most $$$2 \cdot 10^5$$$ in the statements. Sure, I won't ask about why that happened, that is not constructive discussion. Instead, I will discuss about something very interesting about the task.

During that incident, I was wondering. There has to be a way to solve this without the constraint on $$$n \cdot m$$$, right? Of course, $$$7\times 10^8$$$ bytes of input is impossible anyways, but if we ignore that, $$$10^8$$$ is not a very "dreaded" number under these ages of optimizations. There has to be a way to do this.

Then the idea came to me.

Before we cover the solution, we cover a few basic facts on number theory — it might not be necessary to know this to understand the solution, but it will be helpful. Basically, every integer is a point on the grid of infinite dimensions. Each dimension represents a prime factor, so if we restrict the domain to divisors of some integer, it becomes $$$O(\log x)$$$ dimensions because there are only $$$O(\log x)$$$ prime factors of an integer. $$$\gcd$$$ and $$$\text{lcm}$$$ becomes much more tractable to deal with on this grid, because they become simply $$$\min$$$ and $$$\max$$$ on each dimension. Same with divisibility, if each exponent on $$$a$$$ is no less than the corresponding exponent on $$$b$$$, then $$$a$$$ is divisible by $$$b$$$.

Now to the solution. The grid of divisors of $$$a_{1,1}$$$ has $$$O(\log a)$$$ dimensions and $$$d(a)$$$ points, so if we use the same idea on how one flattens a multidimensional array to one dimension, we can map each divisor (point) to their corresponding indices in one array. So, let us consider using a bitset of divisors, so each cell in the DP table can comfortably store the status of each divisor comfortably.

Let us make a bitmask for each divisor $$$mask_d$$$, defined as the union of all divisors of $$$d$$$. Let the multiplier on prime $$$p$$$ while flattening the multidimensional grid be $$$mult_p$$$ (From the facts above, one can see this is essentially the product of $$$\text{exponent}+1$$$ for all smaller primes). Then, $$$mask_1=\texttt{0000...0001}$$$, and $$$mask_d=mask_{(d/p)}|(mask_{(d/p)} \ll mult_p)$$$ if $$$d$$$ is divisible by some prime $$$p$$$. From preprocessing a sieve we have information on all such values of $$$p$$$, so this can be computed nicely as well.

Now we assume WLOG all values in $$$a$$$ are divisors of $$$a_{1,1}$$$ (if it isn't then we can take GCD to make it so). Let $$$b_{i,j}$$$ be the $$$mask$$$ corresponding to the value of $$$a_{i,j}$$$. Then the DP transition becomes as follows —

And of course, the base condition is $$$dp_{1,1}=b_{1,1}$$$.

After finding $$$dp_{n,m}$$$, we can see that if $$$mask_d$$$ for some $$$d$$$ is completely contained in $$$dp_{n,m}$$$, then there exists a path whose GCD is divisible by $$$d$$$. So we try that for each $$$d$$$, and take the maximum $$$d$$$ where the divisibility condition holds.

The time complexity analysis is simple. Because it takes $$$\mathcal{O}(\sqrt{a})$$$ time to enumerate divisors of $$$a_{1,1}$$$, and processing $$$mask$$$-s takes $$$\mathcal{O}(\frac{d(a)^2}{w})$$$ time, we must use $$$\mathcal{O}(\sqrt{a}+\frac{d(a)^2}{w})$$$ time per test case. Then, there are $$$\mathcal{O}(nm)$$$ transitions in the DP, each taking $$$\mathcal{O}(\frac{d(a)}{w})$$$ time. So the DP takes $$$\mathcal{O}(nm\frac{d(a)}{w})$$$ time. Also as we did $$$\gcd$$$ for each cell, the $$$\gcd$$$ must take $$$\mathcal{O}(nm\log(a))$$$ Finally, trying the divisibility for each $$$d$$$ takes $$$\mathcal{O}(\frac{d(a)^2}{w})$$$ again, but that is already counted in the time complexity per test case so we are fine. The final time complexity required is $$$\mathcal{O}(t(\sqrt{a}+\frac{d(a)^2}{w})+\sum{nm}({\log(a)+\frac{d(a)}{w}}))$$$. Because $$$\frac{d(a)}{w}$$$ is such a small constant (precisely $$$4$$$), it should scale well for much larger values of $$$nm$$$, and even possibly run even when there were no constraints on the sum of $$$nm$$$, that is $$$\sum{nm}=10^8$$$ in the worst situation.

255932465 is the accepted submission, and the benchmark is as follows. For all cases $$$a_{i,j}=720\,720$$$ was used for all cells because that is the worst case for $$$d(a)$$$ (though $$$\gcd$$$ might be worse for other values). Only informations of $$$n$$$ and $$$m$$$ were input for each test case, to minimize the effect from IO bound. All benchmark results are from custom invocations. The result was as follows.

^{$$$^\dagger$$$ The stack overflowed, so I had to move the array dp to static (global range).}

May you have any question, please ask in comments! Thank you for reading this far.

During testing of Codeforces Round 934, I found a very cursed (albeit unproven) solution to 1944B - Equal XOR and I thought it would be worth a separate blog, so here it is.

Before I explain the solution, I must give you a quick disclaimer; It is much harder than the intended solution and is very likely useless. If you would appreciate understanding it despite it being very useless, please do read further.

First, let us use an assumption which will be under the very basis of the solution. I will not prove it to you, but you will see that it is likely true.

• Let $$$X$$$ be an uniform random subsequence of $$$a$$$ with size $$$k$$$. Then, $$$X_1 \oplus X_2 \oplus \cdots \oplus X_k$$$ is almost uniformly distributed across all possible values.

If this assumption is true, then we can get to a solution with $$$\mathcal{O}(n \sqrt{n})$$$ expected time complexity and $$$\mathcal{O}(n \sqrt{n}/w)$$$ expected space complexity.

Let us sample one random subsequence of length $$$2k$$$ from $$$a_1,a_2,\cdots,a_n$$$, and one from $$$a_{n+1},a_{n+2},\cdots,a_{2n}$$$. I claim that the probability such that the XOR of these two subsequences coincide is on the order of $$$\Omega(1/n)$$$, under our assumption above. Then, if we sample $$$x$$$ subsequences from each side, what will be the probability that at least one pair will coincide?

Now, there are $$$x^2$$$ pairs between the $$$2x$$$ subsequences picked. Intuitively, we see that this situation is very close to the birthday problem where we need an expected number of $$$O(\sqrt{n})$$$ people to find a collision. Though the pigeonhole principle does not apply here, the probability still works very similarly. The probability that we will have a collision in $$$n$$$ pairs converges to a constant which is $$$e^{-1} \approx 0.367879$$$, and the probability that we get none in $$$x^2$$$ is essentially $$$e^{-x^2/n}$$$ when $$$x^2>n$$$. When $$$x=3\sqrt{n}$$$ this is already less than $$$0.02$$$ percent.

So, we will get at least one collition w.h.p under $$$\mathcal{O}(\sqrt{n})$$$ samples. Each round takes $$$\mathcal{O}(n)$$$ with a trivial process. Thus the time complexity is expected $$$\mathcal{O}(n\sqrt{n})$$$. The final issue is space complexity where $$$\mathcal{O}(n\sqrt{n})$$$ can be tight in $$$256$$$ megabytes, while bitset fixes this issue. The space complexity is reduced to $$$\mathcal{O}(n\sqrt{n}/w)$$$ using a bitset. The solution is complete. The AC submission is here.

Now here is the catch. I did not prove the assumptions along the proof. So I am asking, can anyone prove the assumptions and thus the solution, or disprove the solution (thus finding a hack)? Please let me know in the comments if anyone can either prove or disprove this.

Thank you everyone for participating in The 3rd Chromate Cup Algorithm Division! The full problemset can be accessed on (link) for upsolving. Also the profile badge/backgrounds are being a bit delayed, I am too busy ;-;

A. Strange Shuffle

B. Super Primes

C. Y

D. King of Data Structures

E. World Tour

F. Connected Dominating Set

G. Hard Number Guessing Game

H. Sequence and Not Difficult Queries

I. Cactus Folding

J. Mixed Integer Quadratic Programming

K. Cactus Folding Plus

Hello, This is chromate00 (a.k.a. hjroh0315 on BOJ). The 3rd Chromate Cup Algorithm Division will be held soon! All tasks are developed by me, and all tasks will have statements both Korean and English.

• Date: January 7th (Sun), 20:00 ~ 22:30 KST (2 hours, 30 mins)
• Tasks: 11 tasks. Each task has a score given, and the tasks are sorted increasingly in order of score. The score is proportional to the expected difficulty evaluated by the problemsetter and testers. Still, we suggest you to read each task at least once, the perceived difficulty may vary.
• Difficulty: Bronze ~ Ruby in solved.ac tier (*800 ~ *3000 expected in Codeforces rating)
• Penalty: Uses the same rule as AtCoder. Formally, the penalty is calculated by (Last AC time)+(Sum of tries before AC)*5 mins.
• Language bonus: Language bonus for TL/ML exists for specific languages. See (link; Korean text) for details.
• Standings Freeze: None.
• solved.ac Profile Badge & Background: Each is given to participants who scored at least 250/1500 correspondingly. Please understand that the production/distribution may take two weeks or more.
• Specs: There are at least one interactive task(s). We suggest that you read the guide (link) before participating in the contest.
• Do note that this contest is not held as solved.ac Arena.
• Score Distribution: $$$250-500-1000-1000-1250-1500-2000-2000-3000-4000-4000$$$.

This contest could be held thanks to the testers biximo dhyang24 Eggment_tree naeby Stygian_Nymph utilforever, and also to Startlink for great services Baekjoon Online Judge and BOJ Stack.

The contest's Overview tab also contains the same information as above. If the Overview tab and the announcement have different information, the Overview tab will be considered as more recent.

About the raffle:

A total of 13 people will get a Mom's Touch Thigh Burger voucher. The probability is proportional to the score squared. Please understand that only people who reside in Korea currently or can use the voucher are eligible for the raffle. If you cannot use the voucher please inform us in the raffle announcement after the contest ends.

For people new to Baekjoon Online Judge: You may refer to https://help.solved.ac/en/arena/getting-started/link-account (read until the second to last section) for creating a new account and linking the account to solved.ac.

Ever since Ex has not been in AtCoder Beginner Contest, it feels like every contest has changed too drastically compared to when Ex was in ABC. The difficulty gap between E-F-G has become much, much wider. Previously, we usually had a choice between whether to solve F or G, if we are stuck in either one of them in occasion. Now, we do not have that choice, as the tasks that used to be at Ex is now at G. I think this is a huge loss for people who could solve until F, because they often lose an entire task to solve. There are many other issues, though I will not enumerate every single one of them.

I understand the current situation, the lack of hard tasks and everything. I know how hard it is to hold a contest with a problemset of 8 tasks every week. However, couldn't we have found a better solution to this hard situation? Instead of removing Ex from the problemset, a Call for Tasks can be held, similarly to how it is done for AGC. If I am not mistaken, AGC Call for Tasks requires that a whole problemset is prepared (similarly to contest proposals on Codeforces). For ABC, if easier tasks are abundant and we are in a lack of harder tasks, a Call for Tasks on separate tasks aimed towards G/Ex can be held. This can effectively alleviate the hard situation we are currently in. And this will be effective as well for people who would be willing to set problems on ABCs, but could not because there was no opportunity.

I hope you could consider this suggestion quite seriously.

Sincerely, chromate00.

Disclaimer: If it was not clear to you already, this article is not about an algorithm which is practical on computare hardware. It is about a "natural" algorithm, working based on physical/real-life principles. It may give you some insights on algorithmic thinking, though. Either way, it's interesting to know this.

In this article, I will discuss about an interesting data structure that can deal with all of the following operations in $$$O(1)$$$ time and $$$O(V+EW)$$$ space complexity. The operations are:

• $$$link(u,v,w)$$$: Connect two vertices $$$u$$$ and $$$v$$$ with an edge of weight $$$w$$$.
• $$$cut(e)$$$: Cut the edge $$$e$$$.
• $$$mpath(u,v)$$$: Find a shortest path between two vertices $$$u$$$ and $$$v$$$, if one exists.
• $$$connected(u,v)$$$: Check if two vertices $$$u$$$ and $$$v$$$ are connected.

Here are how each operation works and are implemented.

"Base structure"

Each vertex is an object where you can tie a string on. A plastic ring should work fine. Each edge is a flexible (but not elastic!) string with a certain length. A (practically infinitely) long thread of string, and a pair of scissors is maintained for future use. This is the "base structure" of this data structure.

$$$link(u,v,w)$$$

Grab your pair of scissors, and cut out a string of length $$$w$$$, and connect vertex $$$u$$$ and $$$v$$$ with the string physically. This is practically $$$O(1)$$$ in time complexity, and contributes $$$O(W)$$$ to the space complexity.

$$$cut(e)$$$

Grab your pair of scissors, and cut the string corresponding to the edge $$$e$$$. This is $$$O(1)$$$ in time complexity, and garbage collection can work nicely as well. (Just throw away the string into the bin.)

$$$connected(u,v)$$$, $$$mpath(u,v)$$$

These two operations are basically one operation in reality. This operation can be interpreted as the following linear program.

Now, if you're accustomed to linear programming, you might realize that this is the LP formulation of shortest paths on an undirected graph. Now, what we did for each $$$link$$$ and $$$cut$$$ operation just translates to the constraints in this linear program. Because we connected $$$u_e$$$ and $$$v_e$$$ physically with a string of length $$$w_e$$$, the two vertices cannot have a distance farther than $$$w_e$$$. The only step left is to bind $$$X_u=0$$$ and maximize $$$X_v$$$.

Maximizing $$$X_v$$$ is not hard. You can just grab $$$u$$$ and pull $$$v$$$ forcefully towards some direction until you cannot pull further. Now that the linear program is complete physically, we have just found the result in $$$O(1)$$$ time. If you can pull infinitely, the linear program is unbounded, which means the two vertices are disconnected. If you cannot pull further than some distance, that distance is the shortest path, and the path connecting $$$u$$$ and $$$v$$$ in a straight line now is the shortest path.

Conclusion

With physical principles, we just found out that time complexities that seem impossible can in fact be possible in natural algorithms. How fascinating it is to know what physics can provide us in algorithms! I hope this article could give you some insights on algorithmic thinking, or at least keep you interested throughout the article.

This is a follow-up to this blog, as a self-editorial for the three practice tasks from Medium-Hard to Hard. As solving the task after proving is quite easy (you can just directly use the techniques in the blog), I will only prove why the task is a convex optimization task.

JAG Summer Camp 2019 — "All your base are belong to us"

2013 Japan Domestic Contest — "Anchored Balloon"

Asia Regional Contest 2007 in Tokyo — "Most Distant Point from the Sea"

Before we begin: This blog is my attempt to Codeforces Month of Blog Posts. Simple rule: Write an interesting CodeForces blog post until February 15th and win $300.

In this blog, I will be describing the concept of Convex Optimization, and techniques that can be used to solve Convex Optimization tasks. The blog will be divided into two parts — "What is Convex Optimization", and "How do we solve Convex Optimization tasks". This part of the blog is for "How do we solve Convex Optimization tasks". (Part 1 is here)

There are just too many ways to solve them

One thing is for sure — There are too many ways to solve convex optimization tasks. By "too many", I mean, at least a dozen. We can't cover all of them here! So, I will be covering the methods that can be used in a majority of convex optimization tasks in this blog. Those methods would be Gradient Descent (including the Subgradient method), Coordinate descent, and Ternary Search.

Gradient Descent

Gradient Descent is a technique where we repeatedly move closer to the optimal point. To do this, we must find the gradient of the objective function at the current point, and move based on the gradient. If we know the gradient, we know one direction on which a more optimal point exists, so we move based on the gradient. There are two major flaws of the usual Gradient Descent, though. One flaw is that if we start at a point where the gradient is too small, the convergence will be very slow. There are ways to solve this (Backtracking Line Search is an example), but we will not cover them too technically in this article. Just remember that the methods are done by tweaking the movements, and we would be good to go. The greater issue is that, our objective function may or may not have a gradient. Not always are the objective functions differentiable, so if the objective functions are not differentiable, we cannot use the traditional Gradient Descent.

Luckily, we can still use a similar way, called the Subgradient method. For every convex function at every point, a "subgradient" exists. If a gradient exists, the gradient is a subgradient. If it doesn't, we define any gradient-like vector, where the plane/line defined by the vector underestimates the function in any point, as the subgradient. We can use this subgradient just like the gradient in Gradient Descent. The only thing to remember is that we may not converge at all if the step size is fixed, so we must reduce the step size at every iteration. This method is very convenient if we have a way to easily determine a subgradient.

Coordinate Descent

Coordinate Descent is probably the simplest of the methods used for Convex Optimization. Not many tasks allow the usage of Coordinate Descent, but if we can use it, it makes solving the task much easier. Basically, we move along the axes on the euclidean plane. We define a variable "delta" initially, and in each step, we seek towards four directions (+x,-x,+y,-y) and see if moving towards any direction by delta reduces the value. If moving towards any direction reduces the value, we move towards that direction. If delta is constant, then we will clearly be stuck in one point at some point in time (likely the second step), so we decrease delta at every step. Coordinate Descent's flaw is that it can be stuck at situations where there are more than one direction having greatest reduction. Still, this flaw does not exist on one dimension, so you can simply treat it as a "Lazy man's Ternary Search" in one dimension.

Ternary Search

At this point you may say, "Wait, isn't ternary search limited to one dimension?" and you may be right. But think about it, $$$\mathbb{R}^2$$$ is just $$$\mathbb{R}$$$ in two axes. Instead of just one dimension, we can think of using the result from ternary search (the minimized/maximized value) as the function to minimize/maximize in another ternary search. This is one very simple way to solve convex optimization tasks, and is guaranteed to work very often. (If time complexity isn't an issue, that is!) Again, coordinate descent always works in one dimension, so you can replace one ternary search with coordinate descent if you want to.

Practice Tasks

Easy Difficulty

• Almost any ternary search task. Try to prove whether the objective function is convex before you solve it!

Medium Difficulty

• NCNA 2019 — "Weird Flecks, but OK": Usage of the Smallest Enclosing Circle task. (Kattis) (Baekjoon)
• Waterloo's local Programming Contests — "A Star not a Tree?": The Geometric Median task. (Baekjoon)

Medium-Hard Difficulty

• JAG Summer Camp 2019 — "All your base are belong to us": if K=1, this is the Smallest Enclosing Circle. if K=N, this is the Geometric Median. Is our objective function convex even for any arbitrary N? Time to find out. (Baekjoon)
• 2013 Japan Domestic Contest — "Anchored Balloon": Designing the objective function may be tricky for this task. Bruteforcing is one solution for the task, but using convex optimization techniques to solve it is a very good practice. (Baekjoon)

Hard Difficulty

• Asia Regional Contest 2007 in Tokyo — "Most Distant Point from the Sea": Some people reading the task may know this as a half-plane intersection task. And you're not wrong. Still, This task can be solved as a Convex Optimization task well enough in the TL! (Baekjoon)
• SWERC 2021-2022 "Pandemic Restrictions": The intended solution was based on convex optimization. For proof, please check the official editorial of the mirror contest. (CF Gym)

UPD: Solutions here!

Before we begin: This blog is my attempt to Codeforces Month of Blog Posts. Simple rule: Write an interesting CodeForces blog post until February 15th and win $300.

In this blog, I will be describing the concept of Convex Optimization, and techniques that can be used to solve Convex Optimization tasks. The blog will be divided into two parts — "What is Convex Optimization", and "How do we solve Convex Optimization tasks". This part of the blog is for "What is Convex Optimization". (Part 2 is here)

What is Convex Optimization?

"A convex optimization problem is an optimization problem in which the objective function is a convex function and the feasible set is a convex set." as Wikipedia says. This may be hard to understand for many people, so let's use the simpler case of a univariate function. Often the "convex function" is called "unimodal function" in CP, and the tasks that use Ternary Search is very often a Convex Optimization task. Let's understand why using ternary search is possible in an univariate convex optimization task.

In the definition above, it is said that "the feasible set is a convex set" in convex optimization. The feasible set is the set of points where the solution can exist. A convex set in one dimension is basically equivalent to an interval. For Ternary Search we define $$$L$$$ and $$$R$$$, the limits where the solution can exist. Here, the feasible set is $$$[L,R]$$$, and of course this set is an interval, so the feasible set is a convex set.

Also citing from the definition of "unimodality" in Wikipedia, "a function f(x) is a unimodal function if for some value m, it is monotonically increasing for x ≤ m and monotonically decreasing for x ≥ m". This is exactly true for "convex (univariate) functions" as well, so convex functions are unimodal, and basically we can solve convex optimization tasks with ternary search.

Similarly to that on one dimension, convex functions and convex sets can be very well defined in multiple dimensions, and so we can expand this idea to multiple dimensions as well. In this blog I will not explain things in standard form, instead I will explain everything verbally and with simple equations. This is because understanding the standard form can be difficult for many people (I don't understand it either).

Important aspects of Convex Functions

There are some important aspects of convex functions that can help in proving the convexity in other tasks. I will use some of these aspects to prove the convexity of some convex optimization tasks later on.

• The intersection of two or more convex functions (either minimum or maximum) is a convex function.

This can be understood intuitively; The intersection of two convex polygons is a convex polygon. The intersection of two intervals (convex sets on one dimension) is an interval, which is a convex set. The intersection of two convex function, is again a convex function. Do note though; the union of two convex function is not necessarily a convex function.

• The sum of two or more convex functions is a convex function.

This can be proven mathematically, but I will not prove this here. There are basically tons of proof out there if you google it, so google it if you want proof on it.

• If the objective function $$$f(x)$$$ is convex and is differentiable, then when $$$f'(x)=0$$$, $$$f(x)$$$ is either a maximum, a minimum, or a saddle point.

This is just basic math, but this serves as a basis of Newton's method in optimization. Not many convex optimization tasks have twice differentiable objective functions (as Newton's method in optimization requires), but it is worth knowing that this exists.

• The distance to a certain point is a convex function, and also is its square.

This is easy enough to understand, and this is the most basic convex function in geometry tasks requiring convex optimization.

• In convex functions, any local minima/maxima is the same as the global minima/maxima.

The exact essence of the reason why convex optimization can be solved easier than any other optimization tasks. I won't prove this formally, but thinking about why this works is a good practice.

Some famous convex optimization tasks, and their proof of convexity

Here are some famous convex optimization tasks as an example to understand convex optimization.

• Smallest Enclosing Circle

This is a convex optimization task asking for the smallest circle enclosing a set of points. (Sometimes it is discussed about a set of circles, but here, we only discuss about the case of a set of points.) In this task it may be thought that we should determine both the center and the radius, but basically we can just determine the center and then the radius is the distance to the farthest point. So, the objective function for a set of points $$$S$$$ is as follows.

The distance to each point is a convex function, and their intersection(max) is also a convex function. The feasible set is the set's convex hull, which is a convex set. Therefore, the Smallest Enclosing Circle is a convex optimization task. An $$$O(n)$$$ algorithm is known for this task (Megiddo or Welzl), but it can still be solved fast enough as a convex optimization task.

• Geometric Median

This is a convex optimization task asking for a point where the sum of distance to all points in a set is minimized. The objective function for this task is simple (as simple as this task's definition).

The distance to each point is a convex function, and their sum is also a convex function. The feasible set is, again, the set's convex hull. Therefore, the Geometric Median problem is a convex optimization task.

The article will continue with methods to solve convex optimization tasks in the next part. Stay tuned!

Let me state my opinions before we start the explaining the actual algorithm — I honestly prefer Monotone Chain over Graham Scan. Its simplicity in implementation is the most important reason, though I have other reasons such as the ability to find the upper hull and the lower hull separately. For people who are already accustomed to Rotating Calipers, you can do it the way you used to, and you will still find the same results. This algorithm is for the people who find the Rotating Calipers' concept hard to understand.

Just yesterday, I came up with a way to find the diameter of a polygon (the distance of the farthest pair) using Two pointers and Monotone Chain. I knew I could already do it using Rotating Calipers, but I found the concept quite hard to understand and implement. Therefore, I came up with a method myself. This method may be equivalent to Rotating Calipers in its result (I would be happy if I can extend it to other tasks), so remind me if it is.

First, we use the Monotone Chain algorithm to find the upper hull and the lower hull separately. Note that we are not looking for the entire hull in one array, we want the upper hull and the lower hull separately. This can be done using the usual Monotone Chain method, but instead of sweeping left->right->left, we sweep twice from left to right, once with $$$CCW \le 0$$$, and once with $$$CCW \ge 0$$$.

Now we prove the following theorem.

We will prove this by this idea: For every pair of points on the same side (upper/lower) of the hull, there exists a way to find a line containing the leftmost/rightmost point and one point from the original pair, with the length longer than the original. We have three cases based on the slope of the line segment (assuming upper hull): $$$a>0$$$, $$$a=0$$$, and $$$a<0$$$. For $$$a>0$$$, we can use the right side in the pair and the leftmost point. The distance in the x-axis and the y-axis will then both be farther than the original, resulting in a longer distance. For $$$a<0$$$ you can use the opposite, and for $$$a=0$$$ you can use either side. Same proof process for the lower hull. The following is a visualization of the proof process.

Green: The cases. Purple: The counterexamples.

Now we reverse the upper hull, and initialize $$$p_u$$$ and $$$p_l$$$ (stands for "upper pointer" and "lower pointer") both to $$$0$$$. So initially, $$$p_l$$$ points to the leftmost point, and $$$p_u$$$ points to the rightmost point. At each step, we update the maximum distance we've found so far, and check which pointer to advance. If $$$p_u$$$ is at the leftmost point, advance $$$p_l$$$. If $$$p_l$$$ is on the rightmost point, advance $$$p_u$$$. Otherwise, check $$$\text{dist}(p_u+1,p_l)$$$ and $$$\text{dist}(p_u,p_l+1)$$$. Advance to the side giving a greater value as a result. $$$\text{dist}(i,j)$$$ here denotes the distance (preferrably squared) between the $$$i$$$-th point on the upper hull (counting from the right) and the $$$j$$$-th point on the lower hull (counting from the left).

This algorithm will give a time complexity of $$$O(H)$$$, $$$H$$$ being the number of vertices on the hull. This algorithm has been tested on tasks which ask for this answer, including the famous "Robert Hood". I plan to release the code for it soon, after I finish some refactoring (the code is currently a bit ugly). Again, this algorithm may be simply equivalent to Rotating Calipers, so if you are already accustomed to it, please use what you are already convenient with. And if you could extend this idea to other Rotating Calipers tasks, let me know! I would be very interested.

For the few weeks so far, I have been practicing ruby on multiple platforms (Atcoder and BOJ, solved about ~150 in total?). Now I feel that I am fluent enough with the language, so I will be using Ruby, along with Python 3 and C++, on todays Round (the Div.3). After that, I would like to share my honest thoughts about using Ruby in CP with others as well. I am eager to see how well Ruby can perform on Codeforces today!

P.S. Yes, I am writing this blog also for the ignorant people who might argue about this saying that I am cheating again, why can't they understand that one person can understand more than 2~3 languages? (Yes, I could've used Ruby, Java, C++, Python, and JS all in the same contest. I simply don't because there's no merit for that.)

UPD: The round has concluded. I solved 4 tasks in total, 3 with Ruby and 1 with Python, and then tried 2 more tasks with C++. (Could not come up with the idea on E, could not come up with the edge cases on G. This is not to argue with the contest's difficulty; the tasks were good, I was just not good enough.)

My impression about this? It's quite amazing. I could do almost everything I can do with Python on Ruby, and the code was shorter most of the time. This gives me a great advantage — I can type less and think more. That's a great advantage. Task A and Ruby made a very funny result, coming up with the following solution.

gets.to_i.times do
    puts eval gets
end

Ruby and Python do share many characteristics — short code, arbitrary precision integers, etc. However, Ruby supports more out-of-the-box, like fractions and complex numbers without any "imports". (arbitrary precision decimal types are supported, but they are in a separate module in the standard library.) And Ruby supports even more with standard libraries, exceeding what you may have imagined a language would have as a built-in feature. Who would have imagined a language would have Tarjan's SCC algorithm built-in? Or multidimensional Newton's method? The language has been performing much better than I have initially imagined, and is constantly getting beyond my imagination. If someone would like to learn a new language for CP (anything other than C++), I would greatly recommend them to learn Ruby.

Ruby does have its flaws, though. Ruby has a very small call-stack size limit by default, for which I am asking for an improvement to Codeforces. The language is also slow, probably on par with Python. But even considering these flaws, Ruby seems to be very performant in the CP scene. (At least, it is better than Python IMO)

TL;DR: It's a great language for CP, and I am very surprised.

Well, it's my first time posting this type of blog on codeforces. Most of the time I could either find help elsewhere or find the answer myself, but this time it was different. I could not find any resource related to this problem, given that the discussion page for this Opencup contest is a blank russian blog from 2015 that I do not want to necropost on, and I do not know anyone who has solved this problem personally. The problem is here on Baekjoon OJ, and I would like to share my approach so far before asking the question, so that we can improve over the current approach.

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
using namespace std;
using ll=long long;

template<class T>
vector<vector<T>> decomp(vector<T>&vec)
{
	bool visit[size(vec)];
	for(bool&b:visit)b=0;
	function<void(vector<T>&,int)>
	dfs=[&](vector<T>&res,int idx)->void
	{
		if(visit[idx])return;
		res.push_back(vec[idx]);
		visit[idx]=1;
		dfs(res,vec[idx]);
	};
	
	for(T&i:vec)i--;
	
	vector<vector<T>> ans;
	for(int i=0;i<size(vec);i++)
	{
		vector<T>tmp;
		if(!visit[i])
		{
			dfs(tmp,i);
			for(int&i:tmp)i++;
			ans.push_back(tmp);
		}
	}
	return ans;
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int q;cin>>q;
	while(q--)
	{
		int n;cin>>n;
		vector<int>v(n);
		for(int&i:v)cin>>i;
		vector<vector<int>>ans;
		while(!is_sorted(begin(v),end(v)))
		{
			vector<int>conv(n),vcp=v;
			auto dc=decomp(v);
			for(auto&vv:dc)
			{
				int sz=size(vv);
				for(int i=0;i<sz-(sz&1);i++)
				{
					conv[vv[i]-1]=vv[i^1];
				}
				if(sz&1)conv[vv[sz-1]-1]=vv[sz-1];
			}
			for(int i=0;i<n;i++)
			v[i]=vcp[conv[i]-1];
			ans.emplace_back(conv);
		}
		
		reverse(begin(ans),end(ans));
		
		cout<<size(ans)<<"\n";
		for(auto&v:ans)
		{
			for(int&i:v)cout<<i<<" ";
			cout<<"\n";
		}
	}
}

Now here's the issue: I am still getting a WA verdict on the problem. This might mean that I need to prove a tighter bound possible, however I am unable to improve it further than the current status of the approach. Can anyone help me on this problem? Is there anyone here who have solved this problem personally and/or during the contest?

Before we get to the point, I kindly ask you to read the previous part of the blog if you haven't already. It contains a lot of the context we will be speaking of.

So, on the previous half of the blog, I explained the basics of named requirements, and promised to demonstrate implementing a working class based on the RandomNumberEngine requirement. It took some time (due to life & stuff), but here it is now. Here I explain the process of implementing Lehmer64, following the RandomNumberEngine requirement.

First, I read carefully the references for the RandomNumberEngine requirement. Reading these requirements carefully before implementing can prevent many mistakes, so you may as well read the requirements before reading the rest of the blog.

The concise description on the top of Requirements provides a very important information, not present in the table below. It is as follows.

A type E satisfying UniformRandomBitGenerator will additionally satisfy RandomNumberEngine if...

This means that, for a type to meet the requirements for RandomNumberEngine, it must meet UniformRandomBitGenerator first. Therefore, I implemented the requirementd for UniformRandomBitGenerator first. This adds 3 lines of code. (One requirement coincides with RandomNumberEngine)

using result_type=uint64_t;
constexpr static uint64_t min(){return 0ull;}
constexpr static uint64_t max(){return -1ull;}

Now that we have the three functions, we can implement the functions needed for RandomNumberEngine. First, I started off with the two constructors and seed functions, seed() and seed(s). The former is basically initializing the RNG with a default seed, the latter is about initializing the RNG with an arbitrary (user-given) seed. I defined the default seed as the maximum value for an unsigned 64-bit integer. However, one issue was that Lehmer64 uses a 128-bit state. Therefore, I had to change the seed to a 128-bit integer with splitmix64 and some bitmasks. Here are the members I added.

uint64_t sm64(uint64_t x,uint64_t n)
{
    x+=n*0x9e3779b97f4a7c15ull;
    x=(x^x>>30)*0xbf58476d1ce4e5b9ull;
    x=(x^x>>27)*0x94d049bb133111ebull;
    return x^x>>31;
}
const static uint64_t def=-1;
Lehmer64():state(state_t(sm64(def,1))<<64|sm64(def,2)){}
Lehmer64(uint64_t seed):state(state_t(sm64(seed,1))<<64|sm64(seed,2)){}
Lehmer64(const Lehmer64& a):state(a.state){}
void seed(){state=state_t(sm64(def,1))<<64|sm64(def,2);}
void seed(uint64_t seed){state=state_t(sm64(seed,1))<<64|sm64(seed,2);}

After this, we need to implement the seed(q) function and its corresponding constructor. The q in seed(q) is defined above, as "q, a lvalue of some type satisfying SeedSequence". SeedSequence here, is another requirement. The only member function of SeedSequence we need to know here, though, would be generate(rb,re). In the reference for SeedSequence, there is a description of this member function.

Fills [rb,re) with 32-bit quantities depending on the initial supplied values and potential previous calls to generate. If rb == re, it does nothing.

So, this is a simple function filling a range with psuedo-random 32-bit unsigned integers. Knowing this, I made an union type of four 32-bit unsigned integers and one 128-bit unsigned integer. This is a lazy way to convert the generated 32-bit integers to one 128-bit integer (in terms of raw bits). After that, I used that union type and wrote the function.

union lz{uint32_t st[4];state_t stt;};
template<class Sseq>
Lehmer64(Sseq& q){lz k;q.generate(k.st,k.st+4);state=k.stt;}
template<class Sseq>
void seed(Sseq& q){lz k;q.generate(k.st,k.st+4);state=k.stt;}

Now we finished 7 functions out of 13 already. For the rest, we can follow the detailed implementations of Lehmer64, or the description of the functions. Here are the other functions I added finally.

uint64_t operator()(){state*=mult;return state>>64;}
template<class T>
T pow(T a,uint64_t b){T z=1;do{if(b&1)z*=a;a*=a;}while(b/=2);return z;}
void discard(uint64_t d){state*=pow(mult,d);}
bool operator==(const Lehmer64& o){return state==o.state;}
bool operator!=(const Lehmer64& o){return state!=o.state;}

template<class os>
os& operator<<(os& ost,const Lehmer64& L){ost<<uint64_t(L.state>>64)<<" "<<uint64_t(L.state);return ost;}
template<class is>
is& operator>>(is& ist,Lehmer64& L){uint64_t a,b;ist>>a>>b;L.state=a;L.state<<=64;L.state|=b;return ist;}

(pow here exists just for binary exponentiation, needed for the discard function, as I did not want the discard function to be $$$O(n)$$$. Also note that the operator overloads for >> and << exist outside the class.)

Here is the final code after merging everything to a working class.

struct Lehmer64
{
    using state_t=__uint128_t;
    using result_type=uint64_t;
    state_t state;
    uint64_t sm64(uint64_t x,uint64_t n)
    {
        x+=n*0x9e3779b97f4a7c15ull;
        x=(x^x>>30)*0xbf58476d1ce4e5b9ull;
        x=(x^x>>27)*0x94d049bb133111ebull;
        return x^x>>31;
    }
    const static state_t mult=0xda942042e4dd58b5;
    const static uint64_t def=-1;
    Lehmer64():state(state_t(sm64(def,1))<<64|sm64(def,2)){}
    Lehmer64(uint64_t seed):state(state_t(sm64(seed,1))<<64|sm64(seed,2)){}
    Lehmer64(const Lehmer64& a):state(a.state){}
    union lz{uint32_t st[4];state_t stt;};
    template<class Sseq>
    Lehmer64(Sseq& q){lz k;q.generate(k.st,k.st+4);state=k.stt;}
    void seed(){state=state_t(sm64(def,1))<<64|sm64(def,2);}
    void seed(uint64_t seed){state=state_t(sm64(seed,1))<<64|sm64(seed,2);}
    template<class Sseq>
    void seed(Sseq& q){lz k;q.generate(k.st,k.st+4);state=k.stt;}
    uint64_t operator()(){state*=mult;return state>>64;}
    template<class T>
    T pow(T a,uint64_t b){T z=1;do{if(b&1)z*=a;a*=a;}while(b/=2);return z;}
    void discard(uint64_t d){state*=pow(mult,d);}
    bool operator==(const Lehmer64& o){return state==o.state;}
    bool operator!=(const Lehmer64& o){return state!=o.state;}
    constexpr static uint64_t min(){return 0ull;}
    constexpr static uint64_t max(){return -1ull;}
};

template<class os>
os& operator<<(os& ost,const Lehmer64& L){ost<<uint64_t(L.state>>64)<<" "<<uint64_t(L.state);return ost;}
template<class is>
is& operator>>(is& ist,Lehmer64& L){uint64_t a,b;ist>>a>>b;L.state=a;L.state<<=64;L.state|=b;return ist;}

Of course, it may take some time if you are not experienced in structured coding, to write code based on complex requirements. Still, understanding named requirements is very important, you will need them sometime in your CP experience as you advance further. I hope this helps in the process of understanding these named requirements. Please post your questions below if you need any resolutions on the explanation (or understanding any named requirement!)

Today I encountered a very strange behaviour. A comment of mine had its vote status changed, but I realized that the original post where it was had already been removed (or hidden, left as a draft) before the change. In this state, noone should be able to see the original post, or only the OP should be able to, if it were just changed back to a draft. Therefore, the vote status cannot possibly change multiple times, as the only one who can possibly access the post is the OP. So I came to think, is the system account manipulating the vote status? Of course, there are unknown parameters that affect the contribution score, and I don't really mind that. I don't really mind my contribution dropping either. (actually I would tolerate it dropping to somewhere near Sparky_Master_WCH1226's score even) Still, I think the contribution system, or at least the vote system, should be as transparent as possible, reflecting actual votes made by actual human beings.

Hence, the question. Is the vote system rigged?

Just today, I came up with this trick while solving a problem that (originally) required a merge-sort tree. While I knew that it could be solved by a merge-sort tree, I thought implementing it would be relatively tedious. This being said, I do not mean to say that I do not like the data structure, I think its concepts are very clever. However, I do like algorithms whose implementation is very elegant. For this reason, I prefer the fenwick tree over the segment tree on many problems. This was another case of me considering how a fenwick tree could replace the usual implementation. And just today the idea came to me, which turned into a method which could almost replace merge-sort trees. (Note that some people may have found this earlier than I did, and I think most people who did would have found this independently like I did too)

So, as a disclaimer before explaining the method, I should tell you that this method is not really better (time complexity-wise) than the merge-sort tree. However, in practice, many queries of the merge-sort tree requires an $$$O(\log^2 N)$$$ time complexity per query. So, if the situation of $$$N \gg Q$$$ (meaning that $$$N$$$ is much larger than $$$Q$$$, a situation which does not happen very often in the CP scene) does not happen, this method seems feasible enough.

This methodology consists of three steps, "add", "build", and "query". The "add" and "query" step's implementation is a modification to the fenwick tree, and the only added step is "build", which is not complex at all. (You could even one-line it!) I will explain them in order.

First Step: Add

This step consists of adding the element to the indices that needs to store this element. For example, if we need to add the element $$$2$$$ to index $$$1$$$, we add this to indices $$$[1,2,4,8,\cdots,2^{\lfloor \log N \rfloor -1}]$$$. This can be done by replacing the operation on the "add" step of the fenwick tree to a push_back operation. (assuming that bit is an array of vectors.) Code is as follows.

void add(int i,ll x)
{
	while(i<MAXN)
	{
		bit[i].push_back(x);
		i+=i&-i;
	}
}

The time complexity of this step is $$$O(\log N)$$$ per addition, as there are $$$\log N$$$ indices at maximum that we need to add the element, therefore $$$O(N \log N)$$$ in total.

Second Step: Build

Now after the "add" step, each index of the fenwick tree contains the elements of the indices it needs to manage. However, the vectors in the fenwick trees are not sorted yet. In this state, we cannot get an accurate answer from the queries. Therefore, we need to sort every vector in the fenwick tree. The code of this step is pretty straightforward. Code is as follows.

void build()
{
	for(int i=0;i<MAXN;i++)sort(begin(bit[i]),end(bit[i]));
}

Now for the time complexity. The time complexity of this step is not so trivial, but we can prove an upper bound for it. First we need to prove this.

This can be proven through the following.

Now given that we have at most $$$N \log N$$$ values in the entire fenwick tree, the time complexity will be at most:

Therefore this step's time complexity has an upper bound of $$$O(N \log^2 N)$$$. This bound is not very tight, and while I am convinced that a tighter upper bound can be proven, I was unable to do it myself. (Maybe I could prove $$$O(N \log N \log \log N)$$$?) Please help me find a tighter upper bound if you can.

UPD: If you sort the queries before you actually insert the elements, you can omit this step and get a more optimal time complexity, $$$O(N \log N)$$$, on building the fenwick tree. Credits go to darkkcyan for finding out this technique, you can read this blog post to learn more.

Third Step: Query

Now that all indices of the fenwick tree are sorted, we can answer the queries. This step bases on the usual implementation of fenwick trees, and therefore finds the answer for a prefix $$$[0,x]$$$. Therefore, we can find the answer of many types of queries on the merge sort tree with $$$[l,r]=[0,r] - [0,l-1]$$$. Note that there may be types of queries that cannot be done like this, so this method does not completely replace the merge-sort tree.

Now for the example. Say, the query we want to answer is as follows.

$$$l \, r \, x$$$: Find the number of elements greater than $$$x$$$ in the interval $$$[l,r]$$$.

We can answer this query on a prefix $$$[0,x]$$$ by adding up answers making up the prefix. Therefore, the time complexity for answering about this prefix is $$$O(\log^2 N)$$$ per query, as there are $$$O(\log N)$$$ intervals, and we need to binary search on each partial interval. We can answer any interval by subtracting the answer for $$$[0,l-1]$$$ from that of $$$[0,r]$$$. Code is as follows.

ll query(int i,ll x)
{
	ll ans=0;
	while(i)
	{
		ans+=end(bit[i])-upper_bound(begin(bit[i]),end(bit[i]),x);
		i-=i&-i;
	}
	return ans;
}

With this discovery, I have found that fenwick trees are much more powerful than I used to think. I think this usage of fenwick trees can replace merge-sort trees in many applications of it, and so I decided to give it a name: the Sort-Fenwick. The name comes almost from the merge-sort tree, but due the fact that there is no "merge" at all going on, I omitted "merge" from the name. I really like this methodology, as it is much, much more simple than implementing a merge-sort tree. Suggestions and questions are always appreciated, and thanks for reading!

On todays contest, at 1737B - Ela's Fitness and the Luxury Number, a lot of contestants were hacked or FSTed. This is due to the inaccurate nature of floating-point types. While I do think this happening on a B is not a good thing, but it happened anyways. So as we experienced a failure this time (myself a long time ago multiple times), we need to prepare for the next time it happens.

My solution to this was using Python's isqrt function. It receives a non-negative integer, and returns $$$\lfloor \sqrt{x} \rfloor$$$. It is guaranteed to return the accurate value, so this is the perfect tool for the job. I read this blog as well, and his points are valid. I still thought telling people about the isqrt function would be a great addition to the community as well. Shoutout to -is-this-fft- for writing that blog.

Including this time, there will be many situations where there is a better tool for the job. It is a good idea to actively look for them and use them to your advantage. This is the exact reason I am writing this blog, and other blogs such as the STL in CP series as well. I hope you try to do the same when learning and practicing CP as well.

p.s. I think there should be other languages with builtins serving the same functionality, or ways to do it in the language you use. Please suggest it in the comments section below! It would be a great addition to the topic.

UPD: I just found that this wikipedia page exists, please take a look if you're interested in other methods to do this!

Before reading this blog

https://codeforces.me/blog/entry/10355 — I hope you read this blog before reading this blog. Basically, the SGI STL implements the "rope" data structure, which is a tree-based data structure for doing operations in $$$O(\log N)$$$ time complexity. You can read ahead if you are already familiar with the data structure.

Before we start, Let me explain to you the context on how I thought about this "trick". The rope implementation in SGI STL (from which GNU G++ borrows many extensions) provides many operations given on strings. The most important out of them would arguably be substr (Splitting a substring into another rope) and + (Merging two ropes into one, effectively "concatenating" the strings). There are more functions too, but there is no function to reverse a substring.

Now back to my side of the context. I was thinking about a way to solve this problem.

Given a string and $$$Q$$$ queries of the following kind, output the resulting string after all $$$Q$$$ queries have finished.

l r: reverse the substring in the interval $$$[l,r]$$$.

(This problem appeared on the Croatian Programming Contest 2010, you can try to solve it here.)

Now some of you might know a clear solution already — to use a splay tree. While other BBSTs can work with this type of queries, the splay tree would be one of the most well known ones. However, I do not know how to implement splay trees, but I do know that the rope exists. After a few hours of thinking, I came up with this solution.

Let us manage a rope $$$R$$$ with the given string $$$S$$$ and the reversed string $$$S'$$$ concatenated. If we denote the original length of the string as $$$N$$$, the new length of the string in the rope would be $$$2N$$$.

For all closed intervals $$$[l,r]$$$ representing a substring $$$s$$$, given that $$$1 \leq l \leq r \leq N$$$, we can also find a interval $$$[l',r']$$$ representing the reversed substring $$$s'$$$ in the same rope. And as clearly you may see, this interval $$$[l',r']$$$ corresponds to $$$[2N+1-r,2N+1-l]$$$. Now we can split the rope into five intervals based on these intervals we have found.

These five intervals I am speaking of are the two intervals we have (one from the query, one mirrored from that) and the three other intervals making up the rope. So the whole rope, represented by the five intervals, would be $$$[1,l)+[l,r]+(r,2N+1-r)+[2N+1-r,2N+1-l]+(2N+1-l,2N]$$$. Now we can swap the interval from the query with the mirrored interval. This new rope would be represented as $$$[1,l)+[2N+1-r,2N+1-l]+(r,2N+1-r)+[l,r]+(2N+1-l,2N]$$$, and would contain the new string and its mirrored one, concatenated. The time complexity for doing this operation would be $$$O(\log N)$$$, the same with the rope's time complexity.

Now for the output, we can save the result in a string and discard the latter half, as we do not need the reversed string now. The problem is solved.

The implementation of this solution is very simple, we can already use the functions given by the rope implementation (stated as "the most important" ones above). In my opinion, it is much simpler and easier to understand than implementing a splay tree. Last but not least, it also supports other operations possible on a rope (you can just mirror it on the reversed half as well). Thank you for reading, and as always, suggestions and questions are welcome.

(This was previously a blog reflecting my changes, but I just decided to use it only as a QnA due to some suggestions in the comment. You can see what was written in the revision history)

Hi this is chromate00, and ask me anything. Literally, anything. Criticism included.

Named Requirements are a summary of what the STL expects for certain classes/types to be passed to functions as an argument. Understanding these are important for writing code that works well with other functions in the STL. There are many places you can read them on, but I personally prefer Cppreference. Let's take the following statement as an example.

Compare functions should return false when the two values are equal

This is explicitly stated on the named requirement named Compare, the parts that state this are as follows:

Given comp, an object of type T, For all a, comp(a,a)==false

From this we can see that objects of type T, when called as f(a,a), should return false. Obviously the two as are equal, and we can expect that the STL functions may (or in this case, will) spit unexpected errors if the requirement given in the statement is not satisfied.

The above was an example of named requirements, from a statement relatively well-known in CP. And in this example you can see that following the named requirements is very, very important.

Now we need to understand exactly how we should read the named requirements. There are many different named requirements, and not all named requirements' descriptions look the same. Noticing the difference before understanding them is helpful, so I shall explain what is different in these requirements.

• Some requirements have a very "short and concise" description.

The Predicate requirement is a good example of this. Let's see the description of the requirement, and try to understand it.

The Predicate requirements describe a callable that returns a value testable as a bool.

A good way to understand such descriptions is cutting them phrase by phrase. We can apply this method to this description like this.

"The Predicate requirements describe..."

• a callable means that this requirement includes the Callable requirement
• that returns a value means that the return type of the call is not void
• testable as a bool means that the returned type, either is bool, or can be contextually converted into a bool-type value. the types that fit this condition include int, long, and most importantly bool.

• Some requirements have an "organized table" in its description.

The UniformRandomBitGenerator requirement is a good example. In its description you can clearly see (with the table) what functions/expressions you need to implement for this requirement. The table provides information on what methods it requires, what return types they need to have, and extra requirements needed to fit the requirement.

(Red = The members you need to implement, Blue = Their return types, Green = Implementation details about the members. most other descriptions have a table with a similar format as well.)

• Some requirements have a "dependency" in its description.

The named requirements for iterators show this "dependency" well. Basically when we say

The type T satisfies A if ... the type T satisfies B, ...

Then the named requirement "A" has the named requirement "B" as a prerequisite. Therefore to implement a type satisfying A, it would be convenient to implement methods for B first.

These three are the ways how (at least I thought) named requirements are described. It would be good practice to try these methods on other named requirements, or come up with your own way to read them as well. This was the part 1 of "Understanding Named Requirements", and in part 2 I will demonstrate making an actual working class based on the RandomNumberEngine requirement as a practice for understanding the descriptions. Stay tuned!

Let's begin this story with what happened two days ago.

Well, this happened. Too bad. Maybe I'll just go back to life, I presumed. Until I noticed the line -

You should not publish comic content, especially if it is not interesting to a wide part of the audience, repeats the existing one, or has no connection with competitive programming.

And oh, that was the line I once did not know of. I thought some comedy was fine, still a big part of this community is made of comedy. And it wasn't. The thing is, while I sometimes feel like shitposting, I agree on that we need some part of the community which solely concentrates on learning, teaching, and experimenting. I considered problem solving a quite major part of my life, and for the very same reason I tend to use a lot of time on Codeforces. After all, my vision is to become an algorithm researcher, like people you all know, such as dijkstra, floyd, etc.

This was a lesson learned. and next time you see me in comments/blogs, you'll see me as trying to be as helpful as possible. I expect the next blog to be a continuation on the STL series (actually I've been working on it in a draft), and after that I will explain some useful things too. See you next time in another (helpful) comment/blog.