I can confirm that 317319998 is the same as 317323988, 317314863 is the same as 317316740 and they all solve 2C/2E/2F in this round, and 314138417 313800858 are CRAZY.

NOW I KNOW zhoujiarun0216 IS WHOSE ALT!!!

upd: This is what makes this matter more suspicious:

• They come from the same school
• They have all completed ABCEF
• luuia 's code is heavily confused

At least I can confirm that luuia used LLM during the contest.

upd2: More evidence

https://atcoder.jp/contests/abc403/submissions/65273343 https://atcoder.jp/contests/abc403/submissions/65280364 https://atcoder.jp/contests/abc403/submissions/65274846

upd3: Mark luuia here

upd4: Mark zhouj1arun here

Let's welcome zhoujiarun0216 with the warmest applause for solving 5 problems with LLM! U will became $$$\color{blue}{\texttt{Expert}}$$$ soon! I believe you can use the same method to solve 6 problems in the Edu round the day after tomorrow and become $$$\color{orange}{\texttt{Master}}$$$!

Wow! Today speciallists and pupils are stronger than LGM, and newbies are stronger than GM. CodeForces has a promising future ahead!!!

I have mentioned this before, but it was overlooked

This is the discussion forum for CodeForces today.

gatrmani zhoujiarun0216 RPdreamer sunsetinParis

These scoundrels disrupt the CodeForces community environment by maliciously posting dog poop content, it's time to ban them to gain a better community.

Now, let's take a look at what they have all published:

I am very angry about them now, this is not funny. MikeMirzayanov plz ban them. I hope this is the last post to report them

Ciallo codeforces! In today's div3 I was not able to solve G :( So now I am writing a solution for people who don't know how to solve G.

Let's consider the nature of the problem:

If the subarray $$$a_{[l,r]}$$$ is beautiful, then both $$$a_{[l-1,r]}$$$ and $$$a_{[l,r+1]}$$$ are also beautiful.

If the subarray $$$a_{[l,r]}$$$ is not beautiful, then both $$$a_{[l+1,r]}$$$ and $$$a_{[l,r-1]}$$$ are also not beautiful.

This insight suggests using the two-pointer technique to maintain the answer. The problem then reduces to determining whether, within the interval $$$[l, r]$$$, there exists a pair of indices $$$l \le i \le j \le r$$$ such that $$$a_i \oplus a_j \ge k$$$ (which is exactly the problem discussed in this blog post).

That problem isn’t trivial to maintain (or maybe I just don’t know how yet, haha), but it does exhibit some elegant properties: during the two-pointer process, we only move the pointers $$$l$$$ and $$$r$$$ to the right.

• When moving $$$r$$$ to the right, we know that the interval $$$[l, r-1]$$$ does not contain any pair of indices $$$l \le i \le j \le r-1$$$ such that $$$a_i \oplus a_j \ge k$$$. Therefore, if the interval $$$[l,r]$$$ satisfies the condition, there must exist some $$$l \le i \le r$$$ such that $$$a_i \oplus a_r \ge k$$$. This problem becomes simple: just find the element in the current Trie that maximizes the XOR with $$$a_r$$$.

• When moving $$$l$$$ to the right, we can consider backtracking to the point when $$$r$$$ was last moved to the right (it can be proven that such a point always exists). At that time, the interval $$$[l', r-1]$$$ did not contain any pair $$$l' \le i \le j \le r$$$ such that $$$a_i \oplus a_j \ge k$$$, but there existed some $$$l \le i \le r$$$ such that $$$a_i \oplus a_r \ge k$$$. Therefore, as the pointer $$$l$$$ moves to the right, we only need to remove the contribution of $$$a_l$$$ from the Trie and compute the current maximum XOR with $$$a_r$$$ in the Trie.

The time complexity of this algorithm is $$$O(n \log V)$$$, and it can be solved using this approach.

Code(LANG = C++)

#pragma GCC optimize(3,"Ofast","inline","unroll-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200100;
struct Node{
    int son[2],cnt;
    Node(){cnt=son[0]=son[1]=0;}
}tree[N<<5];
int idx;
void ins(int x,int v){
    int now=0;tree[0].cnt+=v;
    for(int i=29;~i;--i){
        if(!tree[now].son[x>>i&1])tree[now].son[x>>i&1]=++idx;
        now=tree[now].son[x>>i&1];
        tree[now].cnt+=v;
    }
}
int query(int x){
    int now=0,val=0;
    for(int i=29;~i;--i){
        if(tree[now].son[~x>>i&1]&&tree[tree[now].son[~x>>i&1]].cnt)now=tree[now].son[~x>>i&1],val|=(1<<i);
        else now=tree[now].son[x>>i&1];
    }
    return val;
}
int a[N];
signed main(){
    int T;cin>>T;
    while(T--){
        for(int i=0;i<=idx+1;++i)tree[i]=Node();
        idx=0;
        int n,k;cin>>n>>k;
        for(int i=1;i<=n;++i)cin>>a[i];
        int l=1,r=1,mi=1e18;
        while(l<=n&&r<=n){
            ins(a[r++],1);
            while(l<r&&query(a[r-1])>=k)mi=min(mi,r-l),ins(a[l++],-1);
        }
        if(mi>1e17)mi=-1;
        cout<<mi<<'\n';
    }
}

Submission.

Maintains a data structure that supports the following operations:

• inserts an element $$$x$$$ into the set $$$S$$$
• deletes an element $$$x$$$ from the set $$$S$$$
• queries the maximum value of xor for each pair of elements in the set ( $$$\max\limits_{i,j\in S}i\oplus j$$$ )

Can this problem be solved within $$$O(n^2)$$$ better time complexity?

Here, I don't think this is ABC355

UPD: it seems fixed now

They're always posting shit blogs and comments to amuse themselves, which is seriously detrimental to the CodeForces community and buried some really useful blogs

e.g. RPdreamer gatrmani sunsetinParis 2471CoconutMilk

UPD: WhiteSupremacy

UPD2: I think they're motivated to do this by people downvoting in order to get them to the bottom of the contribution list, so I propose that everyone upvote their blogs/comments, which should reduce the frequency of them posting shit.

In today's competition, I only realized in the last minute that problem D could be solved using regret greedy rather than DS with DP. How should I train to quickly recognize when a problem can be solved using regret greedy?

UPD: Thank you to all who have responded to this blog, I have read your comments carefully. Hope to be able to quickly solve it the next time I meet it.