contest duration: 2025-10-05(Sun) 20:00 — 2025-10-05(Sun) 22:30 (local time) (150 minutes)

but meanwhile, down here:

duration: 120 minutes

so what's the true duration.

Interesting score distribution.

Why (Do you live in Japan?* -> No) still need Date of birth* ?

AtCoder's point values sum (×)

Another ACM-ICPC mode (√)

That one guy who has the best strat to get most points: WHY IS EVERYTHING 800 >-<

I am the opposite of that one guy :)

horrible 800

When you want to decide your order of solving problems: 800-800-800-800-800

Yet another ICPC round.

ICPC * 800.

Welp I failed. Gj to those who even did 1 Q

For D, a better way of thinking is to observe that, assume $$$n$$$ is odd, then the winner of the medium row always wins the whole game. In this way, one can naively write a simple dp to calculate the result of the medium row without any further thinking needed.

upd: this solution is not correct, we should keep the medium $$$3$$$ rows and do the dp.

I reduced Problem A to the following task:

Let $$$w=\sum a - X$$$. Count the number of permutations $$$p$$$ of length $$$n$$$ such that $$$\sum \min(a_i,p_i-1)\ge w$$$.

Clearly $$$w \lt n^2$$$. Since we are counting permutations, this can be converted into counting matchings in a bipartite graph between $$${a_1,a_2,\dots,a_n}$$$ and $$${0,1,2,\dots,n-1}$$$. So I place these $$$2n$$$ numbers together, sort them in nonincreasing order, and decide them one by one. I design a DP state $$$f_{i,j,k,l}$$$ meaning that after processing the first $$$i$$$ elements, there are $$$j$$$ unmatched $$$a_i$$$-type elements and $$$k$$$ unmatched index-type elements; the transitions are:

if (a[i].second == 0) {
    // it means it comes from a[i]
    
    if (k) Add(g[j][k - 1][l + a[i].first], mul(f[j][k][l], k));  // match with an index (p_i-1)
    Add(g[j + 1][k][l], f[j][k][l]); // leave this a[i] unmatched
} else {
    // it means it comes from an index (value i-1)

    if (j) Add(g[j - 1][k][l + a[i].first], mul(f[j][k][l], j));  // match with an a (a_i)
    Add(g[j][k + 1][l], f[j][k][l]); // leave this index unmatched
}

This is $$$O(n^5)$$$. However, if I record which DP states are nonzero and only perform transitions from those states, it surprisingly passes.

Does anyone know why that is? Thanks.

Submission record: https://atcoder.jp/contests/arc207/submissions/69911719

How I solved D...

I got stucked on C and went to D.

I remembered that in the 1D version we only need to look at the (at most) $$$3$$$ characters in the middle.

Then I guessed that we also can just look at the central $$$3\times 3$$$ area in the original problem.

I submitted that algorithm but got WA.

I was disappointed. I thought my algorithm was completely wrong and hopelessly changed the area to $$$4\times 4$$$ then submitted it again.

...Then I got Accepted!

I wrote a strange solution for C and it got AC.Can anybody tell me why the probability of WA is sufficiently low?

Here is the code:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<chrono>
#include<random>
#include<queue>
using namespace std;
int n,a[200010],log_2[200010],f[200010][3];
struct ST_Table
{
	int num[200010][20];
	void build()
	{
		for(int i=1;i<=n;i++) num[i][0]=a[i];
		for(int i=1;i<=log_2[n];i++)
			for(int j=1;j+(1ll<<i)-1<=n;j++)
				num[j][i]=num[j][i-1]|num[j+(1ll<<(i-1))][i-1];
	}
	int query(int l,int r)
	{
		int k=log_2[r-l+1];
		return num[l][k]|num[r-(1ll<<k)+1][k];
	}
}ST;
char ch;
int read()
{
	int x=0,xishu=1;
	while(ch<'0'||ch>'9')
	{
		ch=getchar();
		if(ch=='-') xishu=-1;
	}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*xishu;
}
void write(int x)
{
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int main()
{
	n=read();
	for(int i=2;i<=2*n;i++)
		log_2[i]=log_2[i/2]+1;
	for(int i=1;i<=n;i++) a[i]=read();
	ST.build();
	f[0][0]=0;
	f[0][1]=0;
	mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
	for(int i=1;i<=n;i++)
	{
		long long l=0,r=i-1,res=0;
		while(l<=r)
		{
			long long mid=(l+r)>>1;
			long long val1=ST.query(f[mid][1]+1,mid),val2=ST.query(mid+1,i);
			if(val1<=val2)
			{
				res=mid;
				l=mid+1;
			}
			else r=mid-1;
		}
		f[i][0]=f[res][0]+1;
		f[i][1]=res;
		if(i==1) continue;
		for(int j=1;j<=min(i-1,30);j++)
		{
			int k=rnd()%i;
			int val1=ST.query(f[k][1]+1,k),val2=ST.query(k+1,i);
			if(val1<=val2&&f[k][0]+1>f[i][0])
			{
				f[i][0]=f[k][0]+1;
				f[i][1]=k;
			}
		}
	}
	cout<<endl;
	write(f[n][0]);
}

For Problem C, I have a solution with a superior time complexity of O(n log V), where V represents the value range, which is more efficient than the one provided in the Editorial. For details, please refer to: https://atcoder.jp/contests/arc207/submissions/69905415

In problem B, I wrote a brute-force to get an answer from 2 to 8. And I find it can be solved by bipartite graph.

It could be less rating critera

In problem C, I used a very simple approach: let $$$f_i$$$ denote the length of the longest non-decreasing subsequence ending at $$$i$$$, and $$$g_i$$$ denote the minimum value of the last segment in such a subsequence. Then, I performed direct transitions using binary search. This solution passed all test cases, and I want to ask about the correctness of this approach.

Code

#include<bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pb emplace_back
#define ll long long
#define all(b) b.begin(),b.end()
using namespace std;
const int N=2e5+10;
int n,f[N],g[N],a[N],cnt[31][N];
int l1[N],r1[N];
void ck(int i,int w,int d)
{
    if(w>f[i]) f[i]=w,g[i]=d;
    else if(w>=f[i]&&d<g[i]) g[i]=d;
}
void init(int x,int w)
{
    for(int i=0;i<30;i++) cnt[i][x]+=(w>>i&1);
}
inline int calc(int l,int r)
{
    int ans=0;
    for(int i=0;i<30;i++) if(cnt[i][r]-cnt[i][l-1]) ans+=(1<<i);
    return ans;
}
bool check(int i,int x)
{
    int l=l1[x],r=r1[x],ans=-1;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(calc(mid+1,i)>=g[mid]) ans=mid,l=mid+1;
        else r=mid-1;
    }
    if(ans==-1) return 0;
    ck(i,f[ans]+1,calc(ans+1,i));
    return 1;
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],init(i,a[i]);
    for(int i=0;i<30;i++) for(int j=1;j<=n;j++) cnt[i][j]+=cnt[i][j-1];
    for(int i=1;i<=n;i++)
    {
        ck(i,f[i-1],a[i]|g[i-1]);
        if(!check(i,f[i-1])) check(i,f[i-1]-1);
        if(f[i]==f[i-1]) r1[f[i]]=i;
        else l1[f[i]]=r1[f[i]]=i;
    }
    cout<<f[n];
    return 0;
}