Codeforces Round 896 (Div. 1, Div. 2) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Hint 1

Hint 2

Solution

Implementation

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n; cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	if (n & 1) {
		cout << "4" << '\n';
		cout << "1 " << n - 1 << '\n';
		cout << "1 " << n - 1 << '\n';
		cout << n - 1 << ' ' << n << '\n';
		cout << n - 1 << ' ' << n << '\n';
	} else {
		cout << "2" << '\n';
		cout << "1 " << n << '\n';
		cout << "1 " << n << '\n';
	}
	return;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		solve();
	}
}

Rate the problem

1869B - 2D Traveling

Author: programpiggy

Hint

Solution

Implementation

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n, k, s, t; cin >> n >> k >> s >> t;
	vector<int> x(n + 1), y(n + 1);
	for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
	ll ans = llabs(x[s] - x[t]) + llabs(y[s] - y[t]);
	ll mins = LLONG_MAX / 2, mint = LLONG_MAX / 2;
	for (int i = 1; i <= k; i++) {
		mins = min(mins, llabs(x[s] - x[i]) + llabs(y[s] - y[i]));
		mint = min(mint, llabs(x[t] - x[i]) + llabs(y[t] - y[i]));
	}
	ans = min(ans, mins + mint);
	cout << ans << '\n';
	return;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		solve();
	}
}

Rate the problem

1868A - Fill in the Matrix

Author: Error_Yuan

Hint 1

Hint 2

Solution

Implementation

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n, m;
	cin >> n >> m;
	if (m == 1) cout << 0 << '\n';
	else if (n > m - 1) cout << m << '\n';
	else cout << n + 1 << '\n';
	for (int i = 0; i < min(m - 1, n); i++) {
		for (int j = 0; j < m; j++) {
			cout << (j + i) % m << ' ';
		}
		cout << '\n';
	}
	if (n > m - 1) {
		for (int i = m - 1; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << j << ' ';
			}
			cout << '\n';
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		solve();
	}
}

Rate the problem

1868B1 - Candy Party (Easy Version)

Author: Error_Yuan

Hint 1

Hint 2

Hint 3

Solution

Implementation

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n; cin >> n;
	vector<ll> a(n); ll sum = 0;
	for (int i = 0; i < n; i++) cin >> a[i], sum += a[i];
	if (sum % n) return cout << "No" << '\n', void();
	sum /= n;
	vector<int> bit(31, 0);
	auto lowbit = [](int x) {
	    return x & (-x);
	};
	for (int i = 0; i < n; i++) {
		if (a[i] == sum) continue;
		int d = abs(a[i] - sum);
		int p = lowbit(d);
		int e = d + p;
		if (__builtin_popcount(e) == 1) {
		    if (a[i] > sum) bit[__lg(e)]++, bit[__lg(p)]--;
		    else bit[__lg(e)]--, bit[__lg(p)]++;
		} else {
		    cout << "No" << '\n';
		    return;
		}
	}
	for (int i = 0; i < 31; i++) {
		if (bit[i]) {
			cout << "No" << '\n';
			return;
		}
	}
	cout << "Yes" << '\n';
	return;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		solve();
	}
}

Rate the problem

1868B2 - Candy Party (Hard Version)

Author: Error_Yuan
Please, read the tutorial for B1 first.

Hint 4

Hint 5

Hint 6

Solution

Implementation

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n; cin >> n;
	vector<ll> a(n); ll sum = 0;
	for (int i = 0; i < n; i++) cin >> a[i], sum += a[i];
	if (sum % n) return cout << "No" << '\n', void();
	sum /= n;
	vector<int> bit(31, 0), pow1(31, 0), pow2(31, 0);
	for (int i = 0; i < n; i++) {
		int flag = 0;
		if (a[i] == sum) continue;
		for (int j = 0; j < 31; j++) {
			if (a[i] + (1 << j) == sum) {
				pow1[j]++;
				flag = 1;
				continue;
			}
			if (a[i] - (1 << j) == sum) {
				pow2[j]++;
				flag = 1;
				continue;
			}
		}
		if (flag) continue;
		flag = 0;
		for (int j = 0; j < 31; j++) {
			for (int k = 0; k < 31; k++) {
			    if (a[i] + (1 << j) - (1 << k) == sum) {
			        flag = 1;
			        bit[j]++;
			        bit[k]--;
			    }
			}
		}
		if (!flag) {
			cout << "No" << '\n';
			return;
		}
	}
	for (int i = 30; i >= 0; i--) {
		bit[i] += (pow1[i] - pow2[i]);
		if (i == 0) break;
		if (bit[i] < 0) {
			pow1[i - 1] -= -bit[i];
			bit[i - 1] -= -bit[i];
			if (pow1[i - 1] < 0) {
				cout << "No" << '\n';
				return;
			}
		} else {
			pow2[i - 1] -= bit[i];
			bit[i - 1] += bit[i];
			if (pow2[i - 1] < 0) {
				cout << "No" << '\n';
				return;
			}
		}
	}
	if (bit[0] == 0) cout << "Yes" << '\n';
	else cout << "No" << '\n';
	return;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		solve();
	}
}

Rate the problem

1868C - Travel Plan

Author: programpiggy

Hint 1

Hint 2

Hint 3

Hint 4

Hint 5

Solution

$$$\mathcal O(\sum(m\log n+\log^3n))$$$ solution by programpiggy:

Implementation

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
#pragma GCC optimize("Ofast")

ll tot[505],n,m,dp[125][125],dp2[125],g[125][125],g2[125],f[125],pw[100005][125];
const ll mod=998244353;

inline ll dep( ll root) {
	if (root>n)return 0;
	return dep(root*2)+1;
}

inline ll dep2( ll root) {
	if (root>n)return 0;
	return dep2(root*2+1)+1;
}

inline bool full( ll root) {
	return dep(root)==dep2(root);
}

void dfs( ll root) {
	if (root*2>n) {
		g2[0]=dp2[0]=1;
		return;
	}
	if (root*2==n) {
		g2[0]=2,g2[1]=1;
		dp2[0]=1,dp2[1]=1;
		return;
	}
	ll d=0;
	if (full(root*2)) {

		d=dep(root*2);
		dfs(root*2+1);
	} else {
		d=dep(root*2+1);
		dfs(root*2);
	}
	ll mx=2*d+4;
	for (ll i=0; i<=mx; i++) {
		g2[i]+=g[d][i];
		for (ll j=0; j<=min(d+2,i); j++) {
			g2[i+2]+=dp2[j]*dp[d][i-j]%mod;
		}
	}
	for (ll i=mx; i>0; i--)dp2[i]=(dp2[i-1]+dp[d][i-1])%mod;
	dp2[0]=1;
	for (ll i=0; i<=mx; i++)g2[i]+=dp2[i],g2[i]%=mod;
}

inline ll qkp(ll a,ll k) {
	ll ans=1;
	while (k) {
		if (k&1)ans*=a,ans%=mod;
		a*=a,a%=mod;
		k>>=1;
	}
	return ans;
}

int main() {
	ll t;
	scanf("%lld",&t);
	for (ll i=1; i<=60; i++) {
			dp[i][0]=1;
			for (ll j=1; j<=i-1; j++) {
				dp[i][j]=2*dp[i-1][j-1]%mod;
			}
			for (ll j=0; j<=2*i-2; j++) {
				g[i][j]+=g[i-1][j]*2;
				g[i][j]+=dp[i][j];
				g[i][j]%=mod;
				for (ll k=0; k<=j; k++) {
					g[i][j+2]+=dp[i-1][k]*dp[i-1][j-k]%mod;
					g[i][j+2]%=mod;
				}
			}
		}
	while (t--) {
		scanf("%lld%lld",&n,&m);
		
		// log n^3
		dfs(1);
		ll d=dep(1),ans=0;
		for (ll j=0; j<=m; j++) {
			pw[j][0]=1;
			for (ll i=1; i<=2*d; i++) {
				pw[j][i]=pw[j][i-1]*j%mod;
			}
		}

		for (ll i=0; i<=2*d-2; i++) {
			for (ll j=1; j<=m; j++) {
				f[i]+=(pw[j][i+2]+mod-pw[j-1][i+1]*j%mod)%mod;
				f[i]%=mod;
			}
			if (n>=i+1)
				ans+=f[i]*g2[i]%mod*qkp(m,n-i-1)%mod;
			ans%=mod;
		}
		printf("%lld\n",ans);
		for (ll i=1;i<=60;i++){
			for (ll j=0;j<=2*i-2;j++){
				f[j]=g2[j]=dp2[j]=0;
			}
		}
	}

	return 0;
}

$$$\mathcal O(\sum \log^3n)$$$ solution by sszcdjr:

Implementation

#include <bits/stdc++.h>
#define int long long
#define double long double
#define mid ((l+r)>>1)
using namespace std;
const int mod=998244353;
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
int fac[1000005],inv[1000005];
void init(){
	fac[0]=1;
	for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[1000000]=qp(fac[1000000],mod-2);
	for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int i,int j){
	if(i<0||j<0||i<j) return 0;
	return fac[i]*inv[i-j]%mod*inv[j]%mod;
}
int cnt=0;
int reg[100005][131],reg2[100005][131];
unordered_map<int,int> mp;
void dfs(int now){
	if(mp[now]) return ;
	mp[now]=++cnt;
	if(now==0) return ;
	reg[cnt][0]++,reg2[cnt][0]++;
	if(now==1) return ;
	int i=0;
	for(i=1;i<=62;i++) if((1LL<<i)-1>=now) break;
	i-=2;
	int lnum=(1LL<<i)-1,rnum=(1LL<<i)-1,lft=now-(1LL<<(i+1))+1;
	if(lft<=(1LL<<i)) lnum+=lft;
	else lnum+=(1LL<<i),rnum+=(lft-(1LL<<i));
	dfs(lnum),dfs(rnum);
	int ml=mp[lnum],mr=mp[rnum],mn=mp[now];
	for(int i=0;i<=130;i++){
		for(int j=0;j<=130;j++){
			if(i+j+2>=130) break;
			(reg2[mn][i+j+2]+=(reg[ml][i]*reg[mr][j]))%=mod; 
		}
	}
	for(int i=0;i<=129;i++) (reg[mn][i+1]+=reg[ml][i]+reg[mr][i])%=mod,(reg2[mn][i+1]+=reg[ml][i]+reg[mr][i])%=mod,(reg2[mn][i]+=reg2[ml][i]+reg2[mr][i])%=mod;
}
int pw[100005][150],tot[205];
signed main(){
	init();
	int t; cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		dfs(n);
		int nn=mp[n];
		int ans=0;
		tot[0]=(m-1)%mod;
		for(int i=2;i<=135;i++){
			tot[i-1]=(qp((m-1)%mod+1,i)+mod-1)%mod;
			for(int l=2;l<=i;l++) (tot[i-1]+=mod-C(i,l)*tot[i-l]%mod)%=mod;
		    (tot[i-1]*=qp(i,mod-2))%=mod;
		}
		for(int i=0;i<=min(130ll,n-1);i++){
			int tmp=(qp(m%mod,i+2)+mod-tot[i+1])%mod;
			(ans+=tmp*reg2[nn][i]%mod*qp(m%mod,n-(i+1)))%=mod;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

$$$\mathcal O(\sum \log^2n)$$$ solution by sszcdjr:

Implementation

#include <bits/stdc++.h>
#define int long long
#define double long double
#define mid ((l+r)>>1)
using namespace std;
const int mod=998244353;
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
int fac[1000005],inv[1000005];
void init(){
	fac[0]=1;
	for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[1000000]=qp(fac[1000000],mod-2);
	for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int i,int j){
	if(i<0||j<0||i<j) return 0;
	return fac[i]*inv[i-j]%mod*inv[j]%mod;
}
int cnt=0;
int reg[100005][131],dep[100005],depc[100005],rett[131],invi[131];
unordered_map<int,int> mp;
void dfs(int now){
	if(mp[now]) return ;
	mp[now]=++cnt;
	if(now==0) return ;
	dep[cnt]=1,depc[cnt]=1,reg[cnt][0]++;
	if(now==1) return ;
	int i=0;
	for(i=1;i<=62;i++) if((1LL<<i)-1>=now) break;
	i-=2;
	int lnum=(1LL<<i)-1,rnum=(1LL<<i)-1,lft=now-(1LL<<(i+1))+1;
	if(lft<=(1LL<<i)) lnum+=lft;
	else lnum+=(1LL<<i),rnum+=(lft-(1LL<<i));
	dfs(lnum),dfs(rnum);
	int ml=mp[lnum],mr=mp[rnum],mn=mp[now];
	if(dep[ml]>dep[mr]){
		dep[mn]=dep[ml]+1; depc[mn]=depc[ml];
		for(int i=0;i<=129;i++) reg[mn][i]=reg[ml][i];
	}
	else{
		dep[mn]=dep[ml]+1; depc[mn]=(depc[ml]+depc[mr])%mod;
		for(int i=0;i<=129;i++) reg[mn][i]=(reg[ml][i]+reg[mr][i])%mod;
		(reg[mn][dep[mn]*2-2]+=depc[ml]*depc[mr])%=mod;
	}
}
int pw[100005][150],tot[205],pw2[135];
signed main(){
	pw2[0]=1;
	for(int i=1;i<=130;i++) pw2[i]=pw2[i-1]*2%mod,invi[i]=qp(i,mod-2);
	init();
	int t; cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		int lg=0,lft;
		for(int i=0;i<=130;i++) rett[i]=0;
		for(lg=61;lg>=0;lg--){
			if(n>=(1LL<<(lg+1))-1){
				lft=n-((1LL<<(lg+1))-1);
				lft%=mod;
				break;
			}
		}
		for(int i=0;i<=lg;i++){
			for(int j=0;j<=lg;j++){
				int tt=max(i,j);
				(rett[i+j]+=(pw2[lg-tt+1]-1)*pw2[max(0ll,i-1)+max(0ll,j-1)]%mod)%=mod;
			}
		}
		for(int i=1;i<=lg+1;i++){
			for(int j=0;j<i;j++){
				(rett[i+j]+=lft*pw2[max(0ll,j-1)]%mod)%=mod;
			}
		}
		dfs(n);
		int nn=mp[n];
		if(n!=(1ll<<(lg+1))-1) for(int i=0;i<=130;i++) (rett[i]+=reg[nn][i])%=mod;
		int ans=0;
		tot[0]=(m-1)%mod;
		for(int i=2;i<=130;i++){
			tot[i-1]=(qp((m-1)%mod+1,i)+mod-1)%mod;
			for(int l=2;l<=i;l++) (tot[i-1]+=mod-C(i,l)*tot[i-l]%mod)%=mod;
		    (tot[i-1]*=invi[i])%=mod;
		}
		for(int i=0;i<=min(130ll,n-1);i++){
			int tmp=(qp(m%mod,i+2)+mod-tot[i+1])%mod;
			(ans+=tmp*rett[i]%mod*qp(m%mod,n-(i+1)))%=mod;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

$$$\mathcal O(\sum m\log n)$$$ solution by MatrixGroup:

Implementation

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,_##i##__end=(n);i<_##i##__end;++i)
#define rep1(i,n) for(int i=1,_##i##__end=(n);i<=_##i##__end;++i)
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
using namespace std;
const ll mod1=998244353;
int t;
ll n;
int m;
ll qkpw(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%mod1;
		a=a*a%mod1;
		b>>=1;
	}
	return ret;
}
ll val_full[114];
ll val_link[114];
pair<ll,ll> realget(ll P,unsigned long long c)
{
	if((c&(c+1))==0)
	return mp(val_link[bit_width(c)-1],val_full[bit_width(c)-1]);
	if(c==2)
	return mp((P*P+P)%mod1,(P*P+P+P)%mod1);
	if(c&(bit_floor(c)>>1))
	{
		pair<ll,ll> A=realget(P,bit_floor(c)-1),B=realget(P,c-bit_floor(c));
		return mp((A.fi+B.fi+1)*P%mod1,(A.se+B.se+(1+A.fi)*(1+B.fi)%mod1*P)%mod1);
	}
	pair<ll,ll> A=realget(P,c-(bit_floor(c)>>1)),B=realget(P,(bit_floor(c)>>1)-1);
	return mp((A.fi+B.fi+1)*P%mod1,(A.se+B.se+(1+A.fi)*(1+B.fi)%mod1*P)%mod1);
}
ll get_value(ll P,ll c)
{
	val_full[0]=P;val_link[0]=P;
	rep1(i,64)
	{
		val_full[i]=(val_full[i-1]*2+(1+val_link[i-1])*(1+val_link[i-1])%mod1*P)%mod1;
		val_link[i]=((val_link[i-1]*2+1)*P)%mod1;
	}
	return realget(P,c).second;
}
void Q()
{
	cin>>n>>m;
	ll cur=((n%mod1)*(n%mod1+1)/2%mod1)*qkpw(m,n+1)%mod1;
	ll INV_M=qkpw(m,mod1-2);
	rep(i,m) cur=(cur-qkpw(m,n)*get_value(i*INV_M%mod1,n)%mod1+mod1)%mod1;
	cout<<cur<<endl;
}
int main()
{
	cin>>t;while(t--)Q();
}

Rate the problem

1868D - Flower-like Pseudotree

Author: sszcdjr

Hint 1

Hint 2

Hint 3

Hint 4

Hint 5

Solution

Implementation

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
struct node{
	int d,pos;
}a[1000005];
bool cmp(node x,node y){
	return x.d>y.d;
}
void pe(int x,int y){
	cout<<a[x].pos<<" "<<a[y].pos<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t; cin>>t;
	while(t--){
		int n,tot=0; cin>>n; for(int i=1;i<=n;i++) cin>>a[i].d,a[i].pos=i,tot+=a[i].d;
		if(tot!=2*n){
			cout<<"No\n"; continue;
		}
		if(n==1){
			cout<<"No\n"; continue;
		}
		sort(a+1,a+n+1,cmp);
		if(a[1].d==2){
			cout<<"Yes\n";
			for(int i=1;i<=n;i++) pe(i,i%n+1);
			continue;
		}
		if(a[2].d==2){
			cout<<"No\n"; continue;
		}
		int cntb=0;
		for(int i=3;i<=n;i++) cntb+=(a[i].d>1);
		int num[n+1]; for(int i=1;i<=n;i++) num[i]=a[i].d;
		if(!(cntb&1)){
			cout<<"Yes\n";
			pe(1,2),pe(1,2);
			num[1]-=2,num[2]-=2;
			for(int i=3;i<=cntb+2;i++) pe(i,i-2),num[i]--,num[i-2]--;
			int it=1;
			for(int i=cntb+3;i<=n;i++){
				while(!num[it]) it++;
				num[it]--,pe(i,it);
			}
			continue;
		}
		if(a[1].d==3){
			if(a[3].d==2){
				cout<<"No\n"; continue;
			}
			if(cntb==1){
				cout<<"Yes\n";
				pe(1,2),pe(2,3),pe(3,1);
				pe(1,4),pe(2,5),pe(3,6);
				continue;
			}
			if(a[5].d==2&&cntb==3){
				cout<<"No\n"; continue;
			}
			if(cntb==3){
				cout<<"Yes\n";
				pe(1,2),pe(2,3),pe(3,4),pe(4,5),pe(5,1);
				pe(1,6),pe(2,7),pe(3,8),pe(4,9),pe(5,10);
				continue;
			}
			cout<<"Yes\n";
			pe(1,2),pe(1,2),pe(1,3),pe(2,4),pe(3,5),pe(3,6),pe(4,7);
			num[1]-=3,num[2]-=3,num[3]-=3,num[4]-=2,num[5]--,num[6]--,num[7]--;
			for(int i=8;i<=cntb+2;i++) pe(i-2,i),num[i]--,num[i-2]--;
			int it=1;
			for(int i=cntb+3;i<=n;i++){
				while(!num[it]) it++;
				num[it]--,pe(i,it);
			}
			continue;
		}
		else{
			if(a[3].d==2&&cntb==1){
				cout<<"No\n"; continue;
			}
			if(cntb==1){
				cout<<"Yes\n";
				pe(1,2),pe(2,3),pe(3,1);
				num[1]-=2,num[2]-=2,num[3]-=2;
				int it=1;
				for(int i=4;i<=n;i++){
					while(!num[it]) it++;
					num[it]--,pe(i,it);
				}
				continue;
			}
			cout<<"Yes\n";
			pe(1,2),pe(1,2),pe(1,3),pe(1,4),pe(2,5);
			num[1]-=4,num[2]-=3,num[3]-=1,num[4]-=1,num[5]-=1;
			for(int i=6;i<=cntb+2;i++) pe(i,i-2),num[i]--,num[i-2]--;
			int it=1;
			for(int i=cntb+3;i<=n;i++){
				while(!num[it]) it++;
				num[it]--,pe(i,it);
			}
			continue;
		}
	}
	return 0;
}

Rate the problem

1868E - Min-Sum-Max

Author: duck_pear
Huge thanks to Kubic for the development of this problem!

Hint 1

Hint 2

Hint 3

Hint 4

Fun Fact

Solution

Implementation (by Artyom123)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <random>
#include <ctime>
#include <string_view>
#include <queue>
#include <cassert>

using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define pb emplace_back
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define ld long double

const int INF = 1e9 + 1;
const ll INFLL = 1e18;

bool contains(ll x, ll l, ll r) {
    return (x >= l) && (x <= r);
}

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 1) {
        cout << 1 << "\n";
        return;
    }
    vector<ll> pr(n + 1);
    for (int i = 0; i < n; i++) pr[i + 1] = pr[i] + a[i + 1];
    vector<vector<vector<int>>> dp_leftmin(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
    vector<vector<vector<int>>> dp_leftmax(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
    vector<vector<vector<int>>> dp_rightmin(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
    vector<vector<vector<int>>> dp_rightmax(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
    vector<pair<ll, int>> b(n + 1);
    for (int i = 0; i <= n; i++) b[i] = mp(pr[i], i);
    sort(all(b));
    vector<vector<int>> next_left(n + 1, vector<int>(n + 1, -1));
    vector<vector<int>> next_right(n + 1, vector<int>(n + 1, -1));
    for (int i = 0; i <= n; i++) {
        int prev = -1;
        for (int j = 0; j <= n; j++) {
            next_left[i][j] = prev;
            if (pr[j] == pr[i]) prev = j;
        }
        prev = n + 1;
        for (int j = n; j >= 0; j--) {
            next_right[i][j] = prev;
            if (pr[j] == pr[i]) prev = j;
        }
    }
    for (int len = 0; len <= n; len++) {
        for (int i = 0; i <= n && i + len <= n; i++) {
            int j = i + len;
            for (int k = 0; k <= n; k++) {
                if (contains(pr[i], pr[i], pr[k]) && contains(pr[j], pr[i], pr[k])) dp_leftmin[i][j][k] = min(len, 1);
                if (contains(pr[i], pr[k], pr[i]) && contains(pr[j], pr[k], pr[i])) dp_leftmax[i][j][k] = min(len, 1);
                if (contains(pr[i], pr[j], pr[k]) && contains(pr[j], pr[j], pr[k])) dp_rightmin[i][j][k] = min(len, 1);
                if (contains(pr[i], pr[k], pr[j]) && contains(pr[j], pr[k], pr[j])) dp_rightmax[i][j][k] = min(len, 1);
            }
            if (len <= 1) continue;
            for (int x = i; x <= j; x++) {
                if (next_left[i][x] >= i) {
                    int y = next_left[i][x];
                    if (pr[x] >= pr[i]) dp_leftmin[i][j][x] = max(dp_leftmin[i][j][x], dp_leftmin[i][y][x] + dp_leftmax[x][j][i] + 1);
                    if (pr[x] <= pr[i]) dp_leftmax[i][j][x] = max(dp_leftmax[i][j][x], dp_leftmax[i][y][x] + dp_leftmin[x][j][i] + 1);
                }
                if (next_left[j][x] >= i) {
                    int y = next_left[j][x];
                    if (pr[x] >= pr[j]) dp_rightmin[i][j][x] = max(dp_rightmin[i][j][x], dp_rightmin[x][j][x] + dp_rightmin[i][y][x] + 1);
                    if (pr[x] <= pr[j]) dp_rightmax[i][j][x] = max(dp_rightmax[i][j][x], dp_rightmax[x][j][x] + dp_rightmax[i][y][x] + 1);
                }
                if (next_right[i][x] <= j) {
                    int y = next_right[i][x];
                    if (pr[x] >= pr[i]) dp_leftmin[i][j][x] = max(dp_leftmin[i][j][x], dp_leftmin[i][x][x] + dp_leftmin[y][j][x] + 1);
                    if (pr[x] <= pr[i]) dp_leftmax[i][j][x] = max(dp_leftmax[i][j][x], dp_leftmax[i][x][x] + dp_leftmax[y][j][x] + 1);
                }
                if (next_right[j][x] <= j) {
                    int y = next_right[j][x];
                    if (pr[x] >= pr[j]) dp_rightmin[i][j][x] = max(dp_rightmin[i][j][x], dp_rightmin[y][j][x] + dp_rightmax[i][x][j] + 1);
                    if (pr[x] <= pr[j]) dp_rightmax[i][j][x] = max(dp_rightmax[i][j][x], dp_rightmax[y][j][x] + dp_rightmin[i][x][j] + 1);
                }
            }
            int mx_left = -INF;
            int mx_right = -INF;
            for (int k = 0; k <= n; k++) {
                int p = k;
                while (p <= n && b[p].fi == b[k].fi) {
                    mx_left = max(mx_left, dp_leftmin[i][j][b[p].se]);
                    mx_right = max(mx_right, dp_rightmin[i][j][b[p].se]);
                    p++;
                }
                for (int l = k; l < p; l++) {
                    dp_leftmin[i][j][b[l].se] = mx_left;
                    dp_rightmin[i][j][b[l].se] = mx_right;
                }
                k = p - 1;
            }
            mx_left = -INF;
            mx_right = -INF;
            for (int k = n; k >= 0; k--) {
                int p = k;
                while (p >= 0 && b[p].fi == b[k].fi) {
                    mx_left = max(mx_left, dp_leftmax[i][j][b[p].se]);
                    mx_right = max(mx_right, dp_rightmax[i][j][b[p].se]);
                    p--;
                }
                for (int l = k; l > p; l--) {
                    dp_leftmax[i][j][b[l].se] = mx_left;
                    dp_rightmax[i][j][b[l].se] = mx_right;
                }
                k = p + 1;
            }
        }
    }
    int ans = -INF;
    ans = max(ans, dp_leftmin[0][n][n]);
    ans = max(ans, dp_leftmax[0][n][n]);
    for (int x = 0; x <= n; x++) {
        for (int y = x + 1; y <= n; y++) {
            ans = max(ans, dp_rightmin[0][x][y] + dp_leftmax[y][n][x] + 1);
            ans = max(ans, dp_rightmax[0][x][y] + dp_leftmin[y][n][x] + 1);
        }
    }
    cout << ans << "\n";
}

int main() {
    #ifdef LOCAL
        freopen("input", "r", stdin);
        freopen("output", "w", stdout);
    #else 
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Rate the problem

1868F - LIS?

Author: Error_Yuan

Hint 1

Hint 2

Hint 3

Solution

Implementation

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using point = pair<ll, ll>;

const int _N = 5e5 + 5;

int n;
ll a[_N], pre[_N], suf[_N], ans;
struct interval{
	int l, r; 
	ll d, dneed;
	int type, pos; // type0 - l, type1 - r
};
struct cmp{
	bool operator () (const interval &a, const interval &b) {
		return a.dneed - a.d > b.dneed - b.d;
	}
};

ll ceildiv(ll a, ll b) {
	// return a/b;
	if (a * b > 0) return a / b;
	else return a / b - !!(a % b);
}

namespace sg_left{ // [l, r] -> hull of point l-1 to r-1
	vector<int> hull[_N << 2];
	point pt[_N];
	void get_hull(int p, int l, int r) {
		int head = 0, tail = -1;
		for (int i = l; i <= r; i++) {
			while (head < tail && (pt[hull[p][tail]].second - pt[hull[p][tail - 1]].second) * (pt[i].first - pt[hull[p][tail]].first) <= (pt[i].second - pt[hull[p][tail]].second) * (pt[hull[p][tail]].first - pt[hull[p][tail - 1]].first)) {
				tail--;
				hull[p].pop_back();
			}
			tail++;
			hull[p].emplace_back(i);
		}
	}
	void build(int p, int l, int r) {
		get_hull(p, l - 1, r - 1);
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(p * 2, l, mid);
		build(p * 2 + 1, mid + 1, r);
	}
	pair<int, int> query(int p, int l, int r, int L, int R, point o) {
		if (l >= L && r <= R) { // do ternary search
			int tl = 1, tr = hull[p].size();
			while (tl < tr) {
				int m1 = (tl + tr) / 2, m2 = (tl + tr) / 2 + 1;
				auto p1 = pt[hull[p][m1 - 1]], p2 = pt[hull[p][m2 - 1]];
				if ((o.second - p1.second) * (o.first - p2.first) >= (o.second - p2.second) * (o.first - p1.first)) {
					tl = m1 + 1;
				} else tr = m2 - 1;
			}
			return {ceildiv((o.second - pt[hull[p][tl - 1]].second), (o.first - pt[hull[p][tl - 1]].first)), hull[p][tl - 1] + 1};
		}
		int mid = (l + r) >> 1;
		pair<int, int> res = {-1, -1};
		if (L <= mid) {
			res = query(p * 2, l, mid, L, R, o);
		} 
		if (R > mid) {
			auto res2 = query(p * 2 + 1, mid + 1, r, L, R, o);
			if (res == make_pair(-1, -1)) return res2;
			else {
				if (res2.first <= res.first) {
					return res2;
				} else return res;
			}
		}
		return res;
	}
	void test() {
		auto res = query(1, 1, n, 1, n, pt[n]);
		cout << res.first << ' ' << res.second << '\n';
	}
};
namespace sg_right{ // [l, r] -> hull of point l+1 to r+1
	vector<int> hull[_N << 2];
	point pt[_N];
	void get_hull(int p, int l, int r) {
		int head = 0, tail = -1;
		for (int i = l; i <= r; i++) {
			while (head < tail && (pt[hull[p][tail]].second - pt[hull[p][tail - 1]].second) * (pt[i].first - pt[hull[p][tail]].first) < (pt[i].second - pt[hull[p][tail]].second) * (pt[hull[p][tail]].first - pt[hull[p][tail - 1]].first)) {
				tail--;
				hull[p].pop_back();
			}
			tail++;
			hull[p].emplace_back(i);
		}
	}
	void build(int p, int l, int r) {
		get_hull(p, l + 1, r + 1);
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(p * 2, l, mid);
		build(p * 2 + 1, mid + 1, r);
	}
	pair<int, int> query(int p, int l, int r, int L, int R, point o) {
		if (l >= L && r <= R) { // do ternary search
			int tl = 1, tr = hull[p].size();
			while (tl < tr) {
				int m1 = (tl + tr) / 2, m2 = (tl + tr) / 2 + 1;
				auto p1 = pt[hull[p][m1 - 1]], p2 = pt[hull[p][m2 - 1]];
				if ((o.second - p1.second) * (o.first - p2.first) <= (o.second - p2.second) * (o.first - p1.first)) {
					tl = m1 + 1;
				} else tr = m2 - 1;
			}
			return {ceildiv(-(o.second - pt[hull[p][tl - 1]].second), (o.first - pt[hull[p][tl - 1]].first)), hull[p][tl - 1] - 1};
		}
		int mid = (l + r) >> 1;
		pair<int, int> res = {-1, -1};
		if (L <= mid) {
			res = query(p * 2, l, mid, L, R, o);
		} 
		if (R > mid) {
			auto res2 = query(p * 2 + 1, mid + 1, r, L, R, o);
			if (res == make_pair(-1, -1)) return res2;
			else {
				if (res.first <= res2.first) {
					return res;
				} else return res2;
			}
		}
		return res;
	}
	void test() {
		auto res = query(1, 1, n, 1, n, pt[1]);
		cout << res.first << ' ' << res.second << '\n';
	}
};


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];
	if (n == 1) {
		cout << max(a[1] + 1, 0ll) << '\n';
		return 0;
	}
	sg_left::pt[0] = {0, 0}; sg_right::pt[n + 1] = {n + 1, 0};
	for (int i = 1; i <= n; i++) {
		pre[i] = pre[i - 1] + a[i];
		sg_left::pt[i] = {i, pre[i]};
	}
	for (int i = n; i >= 1; i--) {
		suf[i] = suf[i + 1] + a[i];
		sg_right::pt[i] = {i, suf[i]};
	}
	sg_left::build(1, 1, n);
	sg_right::build(1, 1, n);
	ll ans = 0;
	priority_queue<interval, vector<interval>, cmp> q;
	pair<int, int> resL = sg_left::query(1, 1, n, 1, n, sg_left::pt[n]);
	pair<int, int> resR = sg_right::query(1, 1, n, 1, n, sg_right::pt[1]);
	if (resL.second == 1) q.push({1, n, 0, resR.first + 1, 1, resR.second});
	else if (resR.second == n) q.push({1, n, 0, resL.first + 1, 0, resL.second});
	else if (resL.first <= resR.first) q.push({1, n, 0, resL.first + 1, 0, resL.second});
	else q.push({1, n, 0, resR.first + 1, 1, resR.second});
	while (!q.empty()) {
		auto x = q.top(); q.pop();
		if (x.d < x.dneed) {
			ans += x.dneed - x.d;
			x.d = x.dneed;
		}
		//split
		if (x.type == 1) x.pos++;
		int l = x.l, r = x.r;
		resL = sg_left::query(1, 1, n, l, x.pos - 1, sg_left::pt[x.pos - 1]);
		resR = sg_right::query(1, 1, n, l, x.pos - 1, sg_right::pt[l]);
		if (l == x.pos - 1) {
			ans += max(0ll, a[l] - x.d + 1);
		} else {
			if (resL.second == l) q.push({l, x.pos - 1, x.d, resR.first + 1, 1, resR.second});
			else if (resR.second == r) q.push({l, x.pos - 1, x.d, resL.first + 1, 0, resL.second});
			else if (resL.first <= resR.first) q.push({l, x.pos - 1, x.d, resL.first + 1, 0, resL.second});
			else q.push({l, x.pos - 1, x.d, resR.first + 1, 1, resR.second});
		}
		resL = sg_left::query(1, 1, n, x.pos, r, sg_left::pt[r]);
		resR = sg_right::query(1, 1, n, x.pos, r, sg_right::pt[x.pos]);
		if (x.pos == r) {
			ans += max(0ll, a[r] - x.d + 1);
		} else {
			if (resL.second == l) q.push({x.pos, r, x.d, resR.first + 1, 1, resR.second});
			else if (resR.second == r)q.push({x.pos, r, x.d, resL.first + 1, 0, resL.second});
			else if (resL.first < resR.first) q.push({x.pos, r, x.d, resL.first + 1, 0, resL.second});
			else q.push({x.pos, r, x.d, resR.first + 1, 1, resR.second});
		}
	}
	cout << ans << '\n';
}

Bonus

Hint for Bonus

Bonus solution by duck_pear:

Implementation

/*  
  hmz is cute!
--------------------------------------------
  You've got to have faith
  Don't let them cut you down cut you down once more
*/
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define TY long long
#define IL inline
#define umap unordered_map
#define ull unsigned long long
#define pq priority_queue
#define mp make_pair
#define pb push_back
#define mod (TY)(1e9+7)
#define MAXN 500005
#define MAXM 200005
#define MAXK 27
#define INF (TY)(1e9)
#define block 300
#define For(i,a,b) for(TY i=(a);i<=(b);++i)
#define FOR(i,a,b) for(TY i=(a);i<(b);++i)
#define Rof(i,a,b) for(TY i=(a);i>=(b);--i)
#define ROF(i,a,b) for(TY i=(a);i>(b);--i)
IL TY qr(){
	TY x=0,f=1;char op=getchar();
	for(;op<'0'||op>'9';op=getchar())if(op=='-')f=-1;
	for(;op>='0'&&op<='9';op=getchar())x=x*10+(op^48);
	return x*f;
}IL bool ischar(char op){
	if(op>='a'&&op<='z')return true;
	if(op>='A'&&op<='Z')return true;
	return false;
}IL char getc(){
	char op=getchar();
	while(!ischar(op))op=getchar();
	return op;
}IL string qs(){
	string op="";char u=getchar();
	while(!ischar(u))u=getchar();
	while(ischar(u))op+=u,u=getchar();
	return op;
}IL void qw(long long x){
	if(!x){putchar('0');return;}
	if(x<0)putchar('-'),x=-x;
	if(x>=10)qw(x/10);putchar(x%10+'0');
}IL void qw(long long x,char op){qw(x),putchar(op);}
IL void ws(string s){FOR(i,0,s.size())putchar(s[i]);}
IL TY Ceil(TY a,TY b){return a/b+(a%b!=0);}
IL TY Mod(TY a){return (a>=mod?a-mod:a);}
IL TY Abs(TY a,TY b){return a>b?a-b:b-a;}
IL TY Pow(TY a,TY b){
	TY ans=1,base=a;
	while(b){
		if(b&1)ans=ans*base%mod;
		base=base*base%mod;b>>=1;
	}return ans;
}TY n,a[MAXN],b[MAXN],sum[MAXN],lenx[MAXN],leny[MAXN],ans;
vector<signed> e1[MAXN],e2[MAXN],HH;
TY Sum[MAXN],SSum[MAXN];
bool vis[MAXN];
signed L[MAXN],R[MAXN],LL[MAXN],RR[MAXN],ok[MAXN],nxtx[MAXN],nxty[MAXN];
struct node{TY l,r,tag,op;};queue<node> q;
IL void init(TY l,TY r,TY tag){
    For(i,l,r)e1[i].clear(),e2[i].clear();
    vector<pair<TY,TY> > pre,nxt;
    For(i,l,r){
        while(!pre.empty()){
            TY ch=(pre.back().second*-1+tag)*(i-pre.back().first)+sum[i]-sum[pre.back().first];
            if(ch<0){
                nxtx[pre.back().first]=i;
                pre.pop_back();continue;
            }else{
                lenx[i]=pre.back().second+Ceil(ch+1,i-pre.back().first);
                pre.push_back({i,pre.back().second+Ceil(ch+1,i-pre.back().first)});
                break;
            }
        }if(pre.empty()){
            lenx[i]=Ceil(sum[i]-sum[l-1]+tag*(i-l+1)+1,i-l+1);
            pre.push_back({i,Ceil(sum[i]-sum[l-1]+tag*(i-l+1)+1,i-l+1)});
        }
    }while(!pre.empty())nxtx[pre.back().first]=r+1,pre.pop_back();
    Rof(i,r,l){
        while(!nxt.empty()){
            TY ch=(nxt.back().second*-1+tag)*(nxt.back().first-i)-sum[i-1]+sum[nxt.back().first-1];
            if(ch<0){
                nxty[nxt.back().first]=i;
                nxt.pop_back();continue;
            }else{
                leny[i]=nxt.back().second+Ceil(ch+1,nxt.back().first-i);
                nxt.push_back({i,nxt.back().second+Ceil(ch+1,nxt.back().first-i)});
                break;
            }
        }if(nxt.empty()){
            leny[i]=Ceil(sum[r]-sum[i-1]+tag*(r-i+1)+1,r-i+1);
            nxt.push_back({i,Ceil(sum[r]-sum[i-1]+tag*(r-i+1)+1,r-i+1)});
        }
    }while(!nxt.empty())nxty[nxt.back().first]=l-1,nxt.pop_back();
    For(i,l,r)if(nxtx[i]!=r+1)e1[nxtx[i]].pb(i);
    Rof(i,r,l)if(nxty[i]!=l-1)e2[nxty[i]].pb(i);
}int main(){
    //freopen("data.in","r",stdin);
    /* init */
    n=qr();For(i,1,n)a[i]=qr(),sum[i]=sum[i-1]+a[i];
    q.push({1,n,0,0});
    while(!q.empty()){
        TY l=q.front().l,r=q.front().r,tag=q.front().tag,op=q.front().op;
        if(l>r||l<=0||r>n)continue;
        q.pop();
        if(op==0){
            vector<pair<TY,TY> > tmp;
            TY c=0;TY lst=-1;
            For(i,l,r)b[i]=a[i]+tag;
            For(i,l,r){
                if((b[i]>=0)!=lst){
                    lst=(b[i]>=0);
                    ++c;L[c]=R[c]=i;
                    Sum[c]=b[i];
                }else R[c]=i,Sum[c]+=b[i];
            }For(i,1,c)LL[i]=i,RR[i]=i,SSum[i]=Sum[i],ok[i]=0,vis[i]=1;
            Sum[c+1]=0;RR[c+1]=INF;
            For(i,1,c)if(Sum[i]<0){
                ok[i]=(Sum[i-1]+Sum[i]>=0)+(Sum[i+1]+Sum[i]>=0);
                if(ok[i]==2)HH.pb(i),ok[i]=INF;
            }else{
                ok[i]=(Sum[i-1]+Sum[i]<0)+(Sum[i+1]+Sum[i]<0);
                if(ok[i]==2)HH.pb(i),ok[i]=INF;
            }while(!HH.empty()){
                TY now=HH.back(),nowL=LL[now],nowR=RR[now];
                TY k=SSum[nowL]+SSum[nowL-1]+SSum[nowR+1],pre=LL[LL[nowL-1]-1],nxt=RR[nowR+1]+1;
                HH.pop_back();
                if(SSum[nowL]>=0){
                    if(pre>=1&&nxt<=c){
                        ok[LL[nowL-1]]=(k+SSum[pre]>=0)+(k+SSum[nxt]>=0);
                        if(ok[LL[nowL-1]]==2)HH.pb(LL[nowL-1]),ok[LL[nowL-1]]=INF;
                    }else ok[LL[nowL-1]]=INF;
                    if(pre>=1){
                        ok[pre]+=-(SSum[nowL-1]+SSum[pre]<0)+(SSum[pre]+k<0);
                        if(ok[pre]==2&&SSum[nowL-1]+SSum[pre]>=0)HH.pb(pre),ok[pre]=INF;
                    }if(nxt<=c){
                        ok[nxt]+=-(SSum[nowR+1]+SSum[nxt]<0)+(SSum[nxt]+k<0);
                        if(ok[nxt]==2&&SSum[nowR+1]+SSum[nxt]>=0)HH.pb(nxt),ok[nxt]=INF;
                    }
                }else{
                    if(pre>=1&&nxt<=c){
                        ok[LL[nowL-1]]=(k+SSum[pre]<0)+(k+SSum[nxt]<0);
                        if(ok[LL[nowL-1]]==2)HH.pb(LL[nowL-1]),ok[LL[nowL-1]]=INF;
                    }else ok[LL[nowL-1]]=INF;
                    if(pre>=1){
                        ok[pre]+=-(SSum[nowL-1]+SSum[pre]>=0)+(SSum[pre]+k>=0);
                        if(ok[pre]==2&&SSum[nowL-1]+SSum[pre]<0)HH.pb(pre),ok[pre]=INF;
                    }if(nxt<=c){
                        ok[nxt]+=-(SSum[nowR+1]+SSum[nxt]>=0)+(SSum[nxt]+k>=0);
                        if(ok[nxt]==2&&SSum[nowR+1]+SSum[nxt]<0)HH.pb(nxt),ok[nxt]=INF;
                    }
                }SSum[LL[nowL-1]]=SSum[RR[nowR+1]]=k;
                RR[LL[nowL-1]]=RR[nowR+1];
                LL[RR[nowR+1]]=LL[nowL-1];
            }Rof(i,c,1)if(Sum[i]>=0&&vis[i]){
                Rof(j,i,LL[i])vis[j]=0;
                tmp.pb({L[LL[i]],R[RR[i]]});
            }Rof(i,tmp.size()-1,0)q.push({tmp[i].first,tmp[i].second,tag,1});
        }else{
            if(l==r){
                ans+=a[l]+tag+1;
                continue;
            }queue<TY> fir,sec;
            init(l,r,tag);
            For(i,l,r)if(nxtx[i]==r+1)fir.push(i);
            Rof(i,r,l)if(nxty[i]==l-1)sec.push(i);
            TY lstl=l,lstr=r,lstcnt=0;
            while(lstl<lstr){
                while(!fir.empty()&&(lstl>fir.front()||fir.front()>lstr))fir.pop();
                while(!sec.empty()&&(lstl>sec.front()||sec.front()>lstr))sec.pop();
                TY id1=(fir.empty()?INF:fir.front()),id2=(sec.empty()?INF:sec.front());
                TY cnt1=(id1==INF?INF:lenx[id1]-lstcnt);
                TY cnt2=(id2==INF?INF:leny[id2]-lstcnt);
                if(cnt1<=cnt2){
                    fir.pop();
                    lstcnt=lenx[id1];
                    For(j,lstl,id1){FOR(i,0,e2[j].size())sec.push(e2[j][i]);e2[j].clear();}
                    q.push({lstl,id1,-lstcnt+tag,0});
                    lstl=id1+1;
                }else{
                    sec.pop();
                    lstcnt=leny[id2];
                    Rof(j,lstr,id2){FOR(i,0,e1[j].size())fir.push(e1[j][i]);e1[j].clear();}
                    q.push({id2,lstr,-lstcnt+tag,0});
                    lstr=id2-1;
                }
            }if(lstl==lstr)q.push({lstl,lstl,-lstcnt+tag,1});
            ans+=lstcnt;
        }
    }qw(ans);
    return 0;
}

Rate the problem

Comments (89)

Show archived | Write comment?

bodhijain9425

14 months ago, # |

-50

First Comment!!!

→ Reply

14 months ago, # ^ |

+93

Okay Sorry!!! I was just Excited..

meliodasssf

thanks for fast tutorial

bhoomikacherry

wtf!! 4 months ago?

Abito

+11

They prepare the blog before

_Untrackable_

anyone knows edge case of test case 3 of problem b?? my sumbission :- https://codeforces.me/contest/1869/submission/222740219

mkv29

Instead of m1=INT_MAX, assign it with a bigger value like LLOMG_MAX>>2.

TOMAS_SHELBY

what about mine wa2 B? https://codeforces.me/contest/1869/submission/222829174

sunkuangzheng

If $$$a > k$$$ and $$$b < k$$$,You will calculate the distance between $$$a$$$ and $$$b$$$ mistakely.

The code after changing can get AC.222837643

TheEgoist

Can you please help me, why my code is giving TLE ? I'm also solving the question in O(t*(n+k)) time complexity.

My submission : https://codeforces.me/contest/1869/submission/222959644

Nahida__

You should turn ll dist(int a, int b, vector<pair<ll, ll>> hash) into ll dist(int a, int b, vector<pair<ll, ll>> &hash)

How will passing by reference help in avoiding the tle?Please explain

If you don't add &,the code will copy a new vector<pair<ll,ll>.It's cost $$$O(n)$$$ time complexity,$$$n$$$ is the size of vector<pair<ll,ll> >。If you add that,only an Address is passed in.It cost $$$O(1)$$$ time complexity.

kriepiekrollie

ORZ fast tutorial

maxplus

Typo in B1, should be $$$\implies a_i<a_j$$$

Error_Yuan

+16

Sorry, it is fixed now.

TLE_kam

Why I am getting pretest failed in Problem A ? Here is the code

avnithv

try the case

3
1 1 1

← Rev. 2 →

when you do the last one, you are just replacing $$$a_{n}$$$ with $$$a_{n}$$$.

I am replacing a[n] with XOR of a[n] and a[n] which is 0 as p and r can be equal(given in the question's constraint)

l and r . Sorry for the typo

bycicle

You are replacing a[n] with a[n]. When you do the xor for only one number, you don't get the xor of 2 numbers. To make it more clear, assume the operation was multiplication in stead of xor. When you want to find the product of the numbers from l to r, where l = r = n, your answer is a[n], not a[n] * a[n]. I hope this approach helped you visualise your mistake.

The problem said you replace each $$$a_i$$$ with $$$a_l\oplus a_{l+1}\oplus\cdots\oplus a_r$$$, for $$$l\le i\le r$$$.

So for example,

if $$$l=1$$$ and $$$r=3$$$, you set each $$$a_i=a_1\oplus a_2\oplus a_3$$$.
if $$$l=1$$$ and $$$r=2$$$, you set each $$$a_i=a_1\oplus a_2$$$.
if $$$l=1$$$ and $$$r=1$$$, you set each $$$a_i=a_1$$$.

Do you see it now?

Yesh got it now...btw awesome explanation

soumil1234

← Rev. 4 →

Here is my solution using dijkstra's if anyone wants to have a look. Please check it here Great solution in the tutorial by the way, will get there one day.

i3mr125

TLE. how is that great

I meant in the editorial

oh ok

bro...

commonsense

Quick question, in 2D Traveling how are we making sure that there are 2 major cities in between source and destination?

edit — got it, it doesn't matter!!

In the shortest path, there are either 2 major cities between source and destination, or none.

0gnjen1

Well we don't have to verify that there are 2 cities.

Think of it like this, both cities A and B have a closest major city, except if k=0 in which case the answer is just the direct flight from A to B.

Using the fact that both A and B have a closest major city, we can calculate for both A and B which major city is closest to them, just by iterating over all major cities and calculating the distance and keeping track of the shortest distance.

Now we know that we can go from any major city to any other major city for 0 cost, and even if both A and B are closest to the same city, our solution still works.

Then we can simply say ans=min(AtoMAJOR+BtoMAJOR, AtoB).

Antoniopr

How to aproach MEX problems? i rarely got solve them

orange_trie

Practice more problems ...

2.(Might be silly tip):Use Pen and Paper while you do rough work especially for math ones.

K_vinay_123

got wa in b just because of taking max value for mins = 1e9

well yes, it should be 4e9

fonmagnus

Any simpler explanation for B2? I can't quite comprehend the way mentioned in the editorial lol

hos.lyric

+159

In D1B, I wonder how many people proved (before submitting) that we can always choose a starting point, or at least noticed that it needed a non-trivial work to prove... I think this part is the hardest part of the problem so I feel like it is "the more you think, the more you lose points" problem.

-12

Yep, the conclusion is quite guessable, but it's really hard to prove.

+28

Same, I've spent 15 minutes after writing a solution trying to prove it, shouldn't have done that.

SuperSat0001

-13

Could you outline the proof?

askd

+21

Ah funny, I just commented a similar thing below. I noticed but gave up on proving. I tried to write a solution that doesn't assume that, but I think it's really hard/tedious because of the $$$a[i]$$$ which are already equal to the mean.

I feel like this type of thing, where some proof detail is quite hard, happens somewhat often. It kind of destroys me psychologically in contest, because I don't believe in my solution anymore.

But other people can reliably umm... not have this problem I guess. I would like to know how lol.

Tagl

-25

For me it is a bit instinctual. Ideally, I'd like to prove it in my mind or on paper before submitting, but I think sometimes that is a waste of time. If I have convinced myself beyond reasonable doubt then I simply submit. Like in this problem, I didn't feel that I needed to prove it, it just felt very natural to me that it was possible.

I think this really depends on if you are a very mathematical person or not. I'm somewhere in between but I've had students on either end of that spectrum and their method works for them, but is a bit too extreme for my taste.

+38

1B1

kondasujay2

My solution for Div1 B1/B2 was (I think?) a bit simpler than the editorials. Basically, similar to the editorials we can get two numbers a and b where we must give a and receive b. This can be transformed into, if we gained b, we send a. This is kind of like a graph where there are n edges, each representing a transfer that needs to happen. Then, to check if this graph is valid, it's quite easy. All you have to do is check if the graph can be turned into a bunch of cycles that do not reuse edges. It's very similar to finding an Eulerian circuit, and the restriction for that (for directed graphs) is that the indegree and outdegree must be the same. Something important is that in the case of the number equalling the average, the edge is a self-edge but can be placed anywhere, and as long as you visit a node, it works. Then, for B2, note that if the distance is a power of two then you can change two operations into one. The change to the degree array is +2 -1 or -2 +1 so you can loop downwards and apply changes when needed if possible.

zAfnan

in problem A div2, when n is odd , if I perform [n,n] once instead of performing [n-1,n] twice, it should give the correct answer right? as a[n] ^ a[n] = 0 .

xboy

Well no. Operation for [n, n] will do nothing. Think of it this way, operation[1, 2] is a[1] ^ a[2], operation[1,3] is a[1] ^ a[2] ^ a[3] then operation[1,1] will be a[1], that's it, no more xor taken from there. It is range, so range(1, 3) contains 3 elements, range(1,1) contains only 1 element.

BitSlayer

n,n just means the xor of the subarray (n,n) and you are replacing an with an only not by an^an;

Benny20

Nope, because you don't XOR a[n] twice. The XOR in the range [n, n] would just be a[n], leaving the array unchanged.

_MASTER__

-9

why? check the definition that they gave: Let s=al⊕al+1⊕…⊕ar right? and they said l<=r suppose l==r s=al xor ar no?? I actually got two wrong answers because of this! please prove me wrong :)

I see your point, but I think that's just standard mathematical notation: for example, I think you agree if I say that the sum of the numbers from 1 to n is n(n+1)/2, right? But according to your argument, for n = 1 it should be 1+1 = 2.

if we put n=1 in the formula blindly we will get it equal to 1 , not the same with their definition

Yeah, but the formula is not what I focused on. I just wanted to point out that when we talk about the sum of the numbers from 1 to n we typically denote it as $$$1 + ... + n$$$. This notation means "1" and not "1+1" when $$$n=1$$$.

DottedCalculator

+37

Fill in the missing expression in the sequence!!! 95% fail!!!

$$$\underline{\qquad}$$$, $$$1\oplus2$$$, $$$1\oplus2\oplus3$$$, $$$1\oplus2\oplus3\oplus4$$$, $$$\ldots$$$

Hint: The answer is $$$\textbf{not}$$$ $$$1\oplus1$$$!

manitianajay45

+19

Video Editorial for problem A,B,C,D1

Savior-of-Cross

+39

Why does only taking good interval give the min amount of operations on F?

silxi

+23

It appears that there are some typos in the editorial for B2. I believe these are the correct formulas:

For $$$x \leq cntDS_i$$$:

$$$cntS_i := cntS_i + x$$$
$$$cntS_{i+1} := cntS_{i+1} + cntDS_i - x$$$
$$$cntT_i := cntT_i + cntDS_i - x$$$

For $$$x \leq cntDT_i$$$:

$$$cntT_i := cntT_i + x$$$
$$$cntS_{i-1} := cntS_{i-1} + cntDT_i - x$$$
$$$cntT_i := cntT_i + cntDT_i - x$$$

Szanzi

Can anyone explain why does the solution to problem A (Div. 2) works?

For this problem I first considered if each of the $$$a_i$$$ are either $$$1$$$ or $$$0$$$, since it helps to think about the most extreme cases first sometimes.

Then notice that $$$1\oplus 1\oplus\cdots\oplus 1 = 0$$$ if the number of $$$1$$$'s is even, otherwise it's equal to $$$1$$$.

Also notice that $$$0\oplus 0\oplus\cdots\oplus 0 = 0$$$ for any number of $$$0$$$'s.

So clearly, if $$$r-l+1$$$ is even, then performing the operation on $$$a_l,a_{l+1},\dots,a_r$$$ will either make them all equal to $$$0$$$, or $$$1$$$, and then performing the operation again must always make $$$a_l=a_{l+1}=\cdots=a_r=0$$$.

But then the same must be true for any values of $$$a_i$$$, not only if they are in $$$\{0,1\}$$$, since the same will happen for all of the bits of the numbers.

So if $$$n$$$ is even, then we can just do the operation twice on the entire subarray.

If $$$n$$$ is odd, we perform the operation twice on the first $$$n-1$$$ elements, and then twice on the last $$$n-1$$$ elements to ensure that all the numbers in the array are $$$0$$$.

IHaveAbs

For 1869A — Make It Zero, why couldn't you do something like cout<<n<<" "<<n<<endl; ?
Edit: I didn't see the posts above my bad

That doesn’t do anything. It replaces the last element just by the last element itself. We need to replace it by 0.

programpiggy

bad cones\

silenttkillerr

For this example in Q D1/B1

1 3 6 4 8

We are getting YES , can anyone tell me method of distribution of candies

Test case -> 1 N -> 3 [6,4,8]

Wielomian

Last person gives 4 candy to the first one; First person gives 4 candy to the second one; Second person gives 2 candies to the third one.

First person: 6-4+4=6 Second person: 4-2+4=6 Third person: 8-4+2=6

ohh okay got it.

im_vengeance011

4 months ago, # ^ |

n=4 [8,16,13,12] how is this yes?

I don't know why you think it's a yes? The total number of candies is 8 + 16 + 13 + 12 = 49 which is not divisible by n = 4. So it's impossible that everyone have the same number of candies after swaps.

Igor_Parfenov

In problem Div1 C what is $$$f_{i,j}$$$ (one end being $$$i$$$ — what is it?) and what does this mean: The only difference is that only one $$$f_{i,j}$$$ is not $$$0$$$ under this circumstance and we can solve it in $$$O(log^2n)$$$?

Andalus

My approach to Div1B1/Div2D1 and Div1B2/Div2D2, with only 1D vectors and 1D maps and no graphs (though one can argue there is an implicit graph being considered):

Net Gain: The total sum never changes, so to make all values equal, each value must become equal to the average. If the average is not an integer, answer is NO. After calculating the average, we can easily determine, for each value, what number needs to be added/subtracted to reach the average. Each value has a required "net gain" to reach the average. For values above the average, the net gain is negative (since they actually need a net loss).

Validity of Net Gain: In order to reach the average, the net gain must be expressible as the difference between two powers of 2. For example, a net gain of 12 can be achieved by receiving 16 candies and giving 4 candies. But a net gain of 5 cannot be achieved. Checking whether a net gain value is valid, as well as determining what the respective powers of 2 are, is easy when considering the numbers in binary. Assuming $$$x > y$$$, then $$$2^x - 2^y = 2^y (2^{x - y} - 1)$$$ will have $$$(x - y)$$$ 1s in a row, followed by $$$y$$$ lagging 0s. Utilizing the __builtin_clz and __builtin_ctz functions can help in quickly determining whether a net gain value is valid or not, as well as what the corresponding powers of 2 are (but there are many other ways to do this as well). Note that we would also have to deal with scenarios for $$$x = y$$$ (net gain of 0) and $$$x < y$$$ (net gain is negative, but we can inspect the binary representation of the absolute/negated value instead).

Fulfilling all Net Gains (Easy Version): In the Easy version, if a net gain value is valid, i.e., expressible as $$$2^x - 2^y$$$, then the only way to achieve this net gain is to receive $$$2^x$$$ candies and give $$$2^y$$$ candies. To check whether this is possible for all values, I used a simple map mp, where for a positive integer p, an entry mp[k] = p indicates there are p values that want to give k candies, while an entry mp[k] = -p indicates that there are p values that want to receive k candies. For each value where net gain is non-zero, I determine $$$2^x$$$ and $$$2^y$$$, increment $$$mp[2^y]$$$ and decrement $$$mp[2^x]$$$. If all net gains can be fulfilled, then all map entries should be 0 at the end, since the number of people who want to give $$$k$$$ candies must match the number of people who want to receive $$$k$$$ candies, for all $$$k$$$.

Correctness: Having all map entries be 0 is a necessary condition for Yes, but is it sufficient? We don't have to worry about values with net gain 0, because we can simply have them pass a candy around to each other. Even if there is only one value with net gain 0, this person can be placed as a relay between someone who needs to give some candies to another person. The hard part was on checking whether there will always be someone who has enough candies to start the chain. Apparently this is always satisfied (according to the editorial), and while I don't have a proof either, I intuitively observed that the person with the largest number of candies in each cycle should have enough to start the chain.

Easy Submission: 222779990 (it has some artifacts from when I was trying to check whether it's always possible to start the chain, like sorting the values in reverse-order, and setting a flag when somebody has enough to do so, but this doesn't account for multiple independent chains)

Hard Version: If a valid net gain, $$$2^x - 2^y$$$ cannot be be written as $$$\pm 2^z$$$ for integer $$$z$$$, then the only way to achieve this net gain is through receiving $$$2^x$$$ candies and giving $$$2^y$$$ candies, which we have already dealt with in the Easy version. But if $$$2^x - 2^y = \pm 2^z$$$, then there are actually two options. Without loss of generality, if $$$2^x - 2^y = 2^z$$$, then we can either (A) receive $$$2^x$$$ and give $$$2^y$$$, or (B) simply receive $$$2^z$$$ and give nothing. Note that, in this case, we must have $$$x = z + 1$$$ and $$$y = z$$$.

How do we decide which of the two options to choose? My approach was to first deal with the values that have only one option (like Easy Version) and stores the values with two options in a separate vector to handle later. The map mp may have some non-zero entries at this point. For the remaining net gains (which are powers of 2, or their negations), I sorted them from highest absolute value to lowest absolute value. Let's say the largest value has a net gain of $$$2^z$$$. I consult the map to see if anybody else wanted to give $$$2^{z + 1}$$$ candies. If yes, then choose option A, i.e., receive the $$$2^{z + 1}$$$ and give $$$2^z$$$. If there is no such person, then choose option B, i.e., receive $$$2^z$$$ only and give nothing. The case of net gain $$$-2^z$$$ is handled similarly. In any case, we update the map and move on to the next value.

Correctness: The sorted descending order is crucial. When we process the value with net gain $$$2^z$$$, if there really is some value that wants to give $$$2^{z + 1}$$$ candies, then the only valid recipients are those with net gain $$$2^z$$$, since the remaining values afterwards would have smaller powers of 2, and cannot receive $$$2^{z + 1}$$$ candies. So option A is always valid in such a scenario.

But what about the scenario where we process a value with net gain $$$2^z$$$ and nobody wants to give $$$2^{z + 1}$$$ candies? Sometimes, option A might be valid here, i.e., receive $$$2^{z + 1}$$$ and give $$$2^z$$$, but this requires that there is a $$$-2^z$$$ value later on who will also choose option A, i.e., give $$$2^{z + 1}$$$ candies, but such a value would also have to receive $$$2^z$$$ candies, so these two people can simply swap with each other only. This is equivalent to both people choosing option B. Therefore, choosing option B is always guaranteed to work in this scenario (whereas option A would fail if there is no $$$-2^z$$$ later).

Hard Submission: 222851644 (still has the artifacts from Easy)

shorya2448

Thanks a lot.

HHY_zZhu

No matter what I do, I can't find the bug in my problem 1C. This is the first time I am completely unable to understand where my mistake is, even though my code can't pass the sample. I'm confused because the first three examples passed and there were no issues with overflow or out of bound or anything when I submitted it to Codeforces. Please, can someone help me take a look? I've been working on it all day. 222871376

Found the bug , I'm so silly.

pcumamahesh

Thanks for the great contest!

stefdasca

+10

I posted a video editorial of problem C from Div. 2, I hope you enjoy it and find it interesting.

BF_OF_Priety

D2 is great

Siyah

thanks for clear editorial ^^;

Nice E

Ariadne.w.

dX ain't so happy 'bout problem D&F... felt it's actually okay:)

MuhammadSawalhy

B2's tutorial needs a fix. Should be $$$a_i + 2^{x_i}$$$

Falcon__

-20

老子真草了，题出这么难干什么啊？

写题解不写完整是吧，证明留给读者，我真艹了你*了

-10

这D2的代码和题解真的弄的是一道题？后面的公式全是错的，真的，不想写可以不写的

ajCoder

13 months ago, # |

Would anyone like to help me find any logical errors in my code for 1868C?

Here is my code: https://codeforces.me/contest/1868/submission/230789950

13 months ago, # ^ |

I can't pass the case 49

Death_slayer89

11 months ago, # |

The code in Editorial getting wrong result for the first test case in Make it zero problem.

oximas

7 months ago, # |

I don't get it, why is it in problem A "make it zero" that when we take the xor operation twice for even values of "r-l+1" do we get zero no matter what the values x1,x2,x3... are?

gaurav03kr

7 months ago, # ^ |

Let's assume the size of the array is even and the values are x1,x2,x3,x4,x5,x6 When we take xor of all these values some y would be calculated then replace all entries in the array from x1 to x6 with y Now the array would be y,y,y,y,y,y as the xor of two same numbers is zero, take xor you will get 0.

4 months ago, # |

in div1 B1 n=4 [8,16,13,12] how is this yes?

got it:)

Error_Yuan's blog