Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2) Editorial

#	User	Rating
1	jiangly	3898
2	tourist	3840
3	orzdevinwang	3706
4	ksun48	3691
5	jqdai0815	3682
6	ecnerwala	3525
7	gamegame	3477
8	Benq	3468
9	Ormlis	3381
10	maroonrk	3379

#	User	Contrib.
1	cry	167
2	-is-this-fft-	165
3	Um_nik	160
3	atcoder_official	160
5	Dominater069	159
6	djm03178	158
7	adamant	153
8	luogu_official	150
8	awoo	150
10	TheScrasse	147

2062A - String

Idea: StarSilk. Solution: StarSilk. Preparation: SSerxhs, StarSilk.

Rate this problem

Solution

Code (C++)

#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int T,n,i,ans;
	for(cin>>T;T>0;T--)
	{
		cin>>s;n=s.size();
		ans=0;
		for(i=0;i<n;i++)ans+=s[i]-'0';
		cout<<ans<<'\n';
	}
	return 0;
}

Code (Python)

for _ in range(int(input())):
    print(input().count('1'))

2062B - Clockwork

Idea: StarSilk. Solution: StarSilk. Preparation: SSerxhs, StarSilk.

Rate this problem

Solution

Code (C++)

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int T,n,i,t,flag;
	for(cin>>T;T>0;T--)
	{
		cin>>n;
		flag=0;
		for(i=0;i<n;i++)
		{
			cin>>t;
			if(t<=i*2||t<=(n-i-1)*2)flag=1;
		}
		if(flag)cout<<"NO\n";
		else cout<<"YES\n";
	}
	return 0;
}

Code (Python)

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    for i in range(n):
        if a[i]<=max(i,n-i-1)*2:
            print('NO')
            break
    else:
        print('YES')

2062C - Cirno and Operations

Idea: Yakumo_Ran. Solution: Yakumo_Ran. Preparation: Yakumo_Ran, SSerxhs, mejiamejia.

Rate this problem

Solution

Code (C++)

#include <bits/stdc++.h>
using namespace std;
 
long long a[1010];
 
int main(){
	int t;
	cin >> t;
	while (t--){
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		int now = n;
		long long ans = -1e18;
		for (int i = 1; i <= n; i++){
			long long sum = 0;
			for (int i = 1; i <= now; i++) sum = (sum + a[i]) ;
			if (i == 1) ans = max(ans, sum);
			else ans = max(ans, max(sum, ( - sum) ));
			for (int i = 1; i < now; i++) a[i] = (a[i + 1] - a[i]) ;
			now--;
		}
		cout << ans << endl; 
	}
	return 0;
}

Code (Python)

from math import *
for _ in range(int(input())):
	n=int(input())
	a=list(map(int,input().split()))
	ans=sum(a)
	while n>1:
		n-=1
		a=[a[i+1]-a[i] for i in range(n)]
		ans=max(ans,abs(sum(a)))
	print(ans)

2062D - Balanced Tree

Idea: StarSilk, SSerxhs. Solution: StarSilk, SSerxhs. Preparation: SSerxhs.

Rate this problem

Solution

Code (C++)

#include "bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(),(x).end()
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin >> T;
	while (T--)
	{
		int n, i;
		cin >> n;
		vector<int> l(n), r(n), a(n);
		for (i = 0; i < n; i++) cin >> l[i] >> r[i];
		vector e(n, vector<int>(0));
		for (i = 1; i < n; i++)
		{
			int u, v;
			cin >> u >> v;
			--u, --v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
		long long ans = 0;
		function<void(int)> dfs = [&](int u) {
			int mx = l[u];
			for (int v : e[u])
			{
				erase(e[v], u);
				dfs(v);
				mx = max(mx, a[v]);
			}
			a[u] = min(mx, r[u]);
			for (int v : e[u]) ans += max(0, a[v] - a[u]);
		};
		dfs(0);
		cout << ans + a[0] << "\n";
	}
}

Code (Python)

for _ in range(int(input())):
	n = int(input())
	l,r=[],[]
	for i in range(n):
		L,R=map(int,input().split())
		l.append(L)
		r.append(R)
	e=[[] for i in range(n)]
	for i in range(n-1):
		u,v=map(int,input().split())
		e[u-1].append(v-1)
		e[v-1].append(u-1)
	stk=[0]
	f=[-1]*n
	nfd=[]
	while stk:
		u=stk.pop()
		nfd.append(u)
		for v in e[u]:
			if v!=f[u]:
				f[v]=u
				stk.append(v)
	nfd.reverse()
	ans=0
	for u in nfd:
		for v in e[u]:
			if f[v]==u:
				l[u]=max(l[u],l[v])
		l[u]=min(l[u],r[u])
		for v in e[u]:
			if f[v]==u:
				ans+=max(0,l[v]-l[u])
	print(ans+l[0])

2062E1 - The Game (Easy Version)

Idea: Yakumo_Ran. Solution: Yakumo_Ran. Preparation: Yakumo_Ran,mejiamejia,SSerxhs.

Rate this problem

Solution

Code (C++)

#include "bits/stdc++.h"
using namespace std;
const int N=1e6+5;
vector<int> e[N];
int w[N],dfn[N],nfd[N],pre[N],suf[N],low[N];
bool ed[N];
int id;
void dfs(int u)
{
	if (ed[u]) return;
	ed[u]=1;
	dfn[u]=++id;
	nfd[id]=u;
	for (int v:e[u]) dfs(v);
	ed[u]=0;
	low[u]=id;
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cout<<fixed<<setprecision(15);
	int T; cin>>T;
	while (T--)
	{
		int n,m,i,j;
		cin>>n;
		for (i=1; i<=n; i++)
		{
			e[i].clear();
			id=0;
		}
		for (i=1; i<=n; i++) cin>>w[i];
		for (i=1; i<n; i++)
		{
			int u,v;
			cin>>u>>v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
		dfs(1);
		for (i=1; i<=n; i++) pre[i]=max(pre[i-1],w[nfd[i]]);
		suf[n+1]=0;
		for (i=n; i; i--) suf[i]=max(suf[i+1],w[nfd[i]]);
		int mx=0;
		for (i=1; i<=n; i++) if (max(pre[dfn[i]-1],suf[low[i]+1])>w[i]&&w[i]>w[mx]) mx=i;
		cout<<mx<<'\n';
	}
}

Code (Python)

for _ in range(int(input())):
	n = int(input())
	w=[int(x) for x in input().split()]
	wb=[[] for i in range(n)]
	for i in range(n):
		w[i]-=1
		wb[w[i]].append(i)
	e=[[] for i in range(n)]
	for i in range(n-1):
		u,v=map(int,input().split())
		e[u-1].append(v-1)
		e[v-1].append(u-1)
	stk=[0]
	f,dfn=[-1]*n,[0]*n
	nfd=[]
	while stk:
		u=stk.pop()
		dfn[u]=len(nfd)
		nfd.append(u)
		for v in e[u]:
			if v!=f[u]:
				f[v]=u
				stk.append(v)
	sz=[1]*n
	nfd.reverse()
	for u in nfd:
		if u==0:
			continue
		sz[f[u]]+=sz[u]
	wb.reverse()
	mx=-1;mn=n+1
	for v in wb:
		for u in v:
			if mn<dfn[u] or mx>dfn[u]+sz[u]-1:
				print(u+1)
				break
		else:
			for u in v:
				mn=min(mn,dfn[u])
				mx=max(mx,dfn[u])
			continue
		break
	else:
		print(0)

2062E2 - The Game (Hard Version)

Idea: SSerxhs. Solution: StarSilk,SSerxhs,PaperCloud,fallleaves01. Preparation: SSerxhs,mejiamejia.

Rate this problem

Solution

Code (C++)

#include "bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(),(x).end()
const int N = 5e5 + 2;
vector<int> e[N];
int dfn[N], nfd[N], low[N];
int id, n;
void dfs(int u)
{
	nfd[dfn[u] = ++id] = u;
	for (int v : e[u]) erase(e[v], u), dfs(v);
	low[u] = id;
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cout << fixed << setprecision(15);
	int T; cin >> T;
	while (T--)
	{
		int n, m, i, j;
		cin >> n;
		vector w(n, vector<int>());
		vector<int> c(n + 1), ans;
		for (i = 1; i <= n; i++)
		{
			e[i].clear(); id = 0;
			cin >> j;
			w[j - 1].push_back(i);
		}
		for (i = 1; i < n; i++)
		{
			int u, v;
			cin >> u >> v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
		dfs(1);
		int l = n + 1, r = 0;
		set<int> s;
		for (i = n - 1; i >= 0; i--)
		{
			if (s.size())
			{
				for (int u : w[i])
				{
					int mx = 0;
					for (j = dfn[u] - 1; j; j -= j & -j) mx = max(mx, c[j]);
					if ((*s.begin() < dfn[u] || *s.rbegin() > low[u]) && mx <= low[u] && dfn[u] <= l && low[u] >= r)
						ans.push_back(u);
				}
				for (int u : w[i])
				{
					int mn = *s.begin(), mx = *s.rbegin();
					int L = dfn[u], R = low[u];
					if (mn >= L && mx <= R) continue;
					if (mn >= L && mn <= R) mn = *s.upper_bound(R);
					if (mx >= L && mx <= R) mx = *prev(s.lower_bound(L));
					auto fun = [&](int x, int y) {
						if (x > y) swap(x, y);
						l = min(l, y), r = max(r, x);
						for (j = x; j <= n; j += j & -j) c[j] = max(c[j], y);
					};
					fun(mn, dfn[u]);
					fun(mx, dfn[u]);
				}
			}
			for (int u : w[i]) s.insert(dfn[u]);
		}
		sort(all(ans));
		cout << ans.size();
		for (int x : ans) cout << ' ' << x;
		cout << '\n';
	}
}

2062F - Traveling Salescat

Idea: StarSilk. Solution: StarSilk. Preparation: SSerxhs, StarSilk.

Rate this problem

Solution

Code (C++)

#include<bits/stdc++.h>
using namespace std;
struct apos{
	long long a;
	long long b;
	friend bool operator<(apos a,apos b){
		return a.b-a.a<b.b-b.a;
	}
}ap[3000];
long long dp[3001][3],tdp[3001][3],ans[3001],inf=1000000000000000000LL;
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int T,n,i,j,t;
	for(cin>>T;T>0;T--)
	{
		cin>>n;
		for(i=0;i<n;i++)cin>>ap[i].a>>ap[i].b;
		sort(ap,ap+n);
		for(i=0;i<=n;i++)
		{
			for(j=0;j<3;j++)
			{
				dp[i][j]=inf;
				tdp[i][j]=inf;
			}
			ans[i]=inf;
		}
		for(i=0;i<n;i++)
		{
			tdp[1][0]=min(tdp[1][0],ap[i].a*2);
			tdp[1][1]=min(tdp[1][1],ap[i].a);
			for(j=1;j<n;j++)
			{
				for(t=0;t<3;t++)tdp[j+1][t]=min(tdp[j+1][t],dp[j][t]+ap[i].a+ap[i].b);
				tdp[j+1][1]=min(tdp[j+1][1],dp[j][0]+ap[i].b);
				tdp[j+1][2]=min(tdp[j+1][2],dp[j][1]+ap[i].a);
				ans[j+1]=min(ans[j+1],dp[j][1]+ap[i].b);
				ans[j+1]=min(ans[j+1],dp[j][2]+ap[i].b*2);
			}
			for(j=1;j<=n;j++)
			{
				for(t=0;t<3;t++)
				{
					dp[j][t]=min(dp[j][t],tdp[j][t]);
					tdp[j][t]=inf;
				}
			}
		}
		for(i=2;i<=n;i++)cout<<ans[i]<<' ';
		cout<<'\n';
	}
	return 0;
}

Code (Python)

class Q:
	def __init__(this,x,y):
		this.x,this.y=x+y,x-y
	def __lt__(this,rhs):
		return this.y<rhs.y
for _ in range(int(input())):
	n=int(input())
	a=[0]*n
	for i in range(n):
		x,y=map(int,input().split())
		a[i]=Q(x,y)
	a.sort()
	l=[10**18]*(n+1)
	sl=l.copy();slt=l.copy();slrt=l.copy()
	s=10**18
	for m,t in enumerate(a):
		x,y=t.x,t.y
		for i in range(m,0,-1):
			slrt[i+1]=min(slrt[i+1],sl[i]+x+y,slt[i]+x*2+y*2)
			slt[i+1]=min(slt[i+1],slt[i]+x*2,sl[i]+x-y)
			sl[i+1]=min(sl[i+1],sl[i]+x*2,l[i]+x+y)
			l[i+1]=min(l[i+1],l[i]+x*2)
		sl[1]=min(sl[1],x-y)
		l[1]=min(l[1],x*2-y*2)
	print(*[x//2 for x in slrt[2:]])

2062G - Permutation Factory

Idea: StarSilk. Solution: StarSilk. Preparation: StarSilk, SSerxhs.

Rate this problem

Solution

Code (C++)

#include<bits/stdc++.h>
using namespace std;
struct linex{
	int v;
	int w;
	int nxt;
	int c;
};
int head[210],cnt,cpos[210],vis[210],qvis[210],totc,dis[210],inf=1000000000;
linex l[21000];
queue<int>que;
void add(int u,int v,int w,int c){
	l[cnt].nxt=head[u];
	head[u]=cnt;
	l[cnt].v=v;
	l[cnt].w=w;
	l[cnt].c=c;
	cnt++;
	l[cnt].nxt=head[v];
	head[v]=cnt;
	l[cnt].v=u;
	l[cnt].w=0;
	l[cnt].c=-c;
	cnt++;
}
int spfa(int st,int en,int n){
	int i,j,t;
	for(i=0;i<n;i++)
	{
		vis[i]=0;
		dis[i]=inf;
		cpos[i]=head[i];
	}
	que.push(st);
	dis[st]=0;
	vis[st]=1;
	qvis[st]=1;
	while(!que.empty())
	{
		t=que.front();
		que.pop();
		qvis[t]=0;
		for(j=head[t];j!=-1;j=l[j].nxt)
		{
			if(l[j].w>0&&dis[l[j].v]>dis[t]+l[j].c)
			{
				dis[l[j].v]=dis[t]+l[j].c;
				vis[l[j].v]=1;
				if(!qvis[l[j].v])
				{
					que.push(l[j].v);
					qvis[l[j].v]=1;
				}
			}
		}
	}
	return vis[en];
}
long long dfs(int p,int en,int curr){
	int x,j,flow=0;
	if(p==en)return curr;
	for(j=cpos[p];j!=-1&&flow<curr;j=l[j].nxt)
	{
		cpos[p]=j;
		qvis[p]=1;
		if(l[j].w>0&&dis[l[j].v]==dis[p]+l[j].c&&!qvis[l[j].v])
		{
			x=dfs(l[j].v,en,min(curr-flow,l[j].w));
			flow+=x;
			l[j].w-=x;
			l[j^1].w+=x;
			totc+=l[j].c*x;
		}
		qvis[p]=0;
	}
	return flow;
}
int p[100],q[100],id[100][100];
int cabs(int x){
	if(x<0)x=-x;
	return x;
}
struct point{
	int x;
	int y;
	int tx;
	int ty;
}pc[100];
vector<int>ansv[2];
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	srand(time(0));
	int T,n,i,j,flow,flag;
	for(cin>>T;T>0;T--)
	{
		cin>>n;
		for(i=0;i<n;i++)
		{
			cin>>p[i];
			p[i]--;
		}
		for(i=0;i<n;i++)
		{
			cin>>q[i];
			q[i]--;
		}
		for(i=0;i<n*2+2;i++)head[i]=-1;
		cnt=0;
		totc=0;
		flow=0;
		for(i=0;i<n;i++)
		{
			add(n*2,i,1,0);
			add(i+n,n*2+1,1,0);
			for(j=0;j<n;j++)
			{
				id[i][j]=cnt;
				add(i,j+n,1,cabs(i-j)+cabs(p[i]-q[j]));
			}
		}
		while(spfa(n*2,n*2+1,n*2+2))flow+=dfs(n*2,n*2+1,inf);
		for(i=0;i<n;i++)
		{
			pc[i].x=i;
			pc[i].y=p[i];
			for(j=0;j<n;j++)
			{
				if(l[id[i][j]].w==0)
				{
					pc[i].tx=j;
					pc[i].ty=q[j];
				}
			}
		}
		while(1)
		{
			flag=0;
			for(i=0;i<n;i++)
			{
				for(j=0;j<n;j++)
				{
					if(pc[j].tx<=pc[i].x&&pc[i].x<pc[j].x&&pc[j].x<=pc[i].tx)
					{
						ansv[0].push_back(pc[i].x);
						ansv[1].push_back(pc[j].x);
						swap(pc[i].x,pc[j].x);
						flag=1;
					}
				}
			}
			if(!flag)break;
		}
		while(1)
		{
			flag=0;
			for(i=0;i<n;i++)
			{
				for(j=0;j<n;j++)
				{
					if(pc[j].ty<=pc[i].y&&pc[i].y<pc[j].y&&pc[j].y<=pc[i].ty)
					{
						ansv[0].push_back(pc[i].x);
						ansv[1].push_back(pc[j].x);
						swap(pc[i].y,pc[j].y);
						flag=1;
					}
				}
			}
			if(!flag)break;
		}
		cout<<ansv[0].size()<<'\n';
		for(i=0;i<ansv[0].size();i++)cout<<ansv[0][i]+1<<' '<<ansv[1][i]+1<<'\n';
		ansv[0].clear();
		ansv[1].clear();
	}
	return 0;
}

2062H - Galaxy Generator

Idea: StarSilk. Solution: StarSilk. Preparation: StarSilk.

Rate this problem

Solution

Code (C++)

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
string s;
long long dp[15][15][1<<14],vl[200],sgvl[15][15][15][15];
long long dp2[15][1<<14],dpvl2[15][1<<14];
int psum[15][15];
long long getvl(long long l,long long r,long long x,long long y){
	if(l>=r||x>=y)return 0;
	return vl[psum[r][y]-psum[l][y]-psum[r][x]+psum[l][x]];
}
long long f(long long l,long long r,long long x,long long y){
	long long ans=0,i,c,tl,tr,tx,ty;
	for(i=0;i<16;i++)
	{
		c=0;
		tl=l;
		tr=r;
		tx=x;
		ty=y;
		if(i&1)
		{
			c^=1;
			tl++;
		}
		if(i&2)
		{
			c^=1;
			tr--;
		}
		if(i&4)
		{
			c^=1;
			tx++;
		}
		if(i&8)
		{
			c^=1;
			ty--;
		}
		if(c)ans=(ans+mod-getvl(tl,tr,tx,ty))%mod;
		else ans=(ans+getvl(tl,tr,tx,ty))%mod;
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int T,n,i,j,t,p,l,r,len,cmsk;
	long long ans;
	for(cin>>T;T>0;T--)
	{
		cin>>n;
		vl[0]=0;
		for(i=1;i<=n*n;i++)vl[i]=(vl[i-1]*2+1)%mod;
		for(i=0;i<=n;i++)
		{
			for(j=0;j<=n;j++)psum[i][j]=0;
		}
		for(i=0;i<n;i++)
		{
			cin>>s;
			for(j=0;j<n;j++)psum[i+1][j+1]=s[j]-'0';
		}
		for(i=0;i<n;i++)
		{
			for(j=0;j<=n;j++)psum[i+1][j]+=psum[i][j];
		}
		for(i=0;i<=n;i++)
		{
			for(j=0;j<n;j++)psum[i][j+1]+=psum[i][j];
		}
		for(l=0;l<=n;l++)
		{
			for(r=l+1;r<=n;r++)
			{
				for(i=0;i<=n;i++)
				{
					for(j=i+1;j<=n;j++)sgvl[l][r][i][j]=f(l,r,i,j);
				}
			}
		}
		for(i=0;i<=n;i++)
		{
			for(j=0;j<=n;j++)
			{
				for(t=0;t<(1<<n);t++)dp[i][j][t]=0;
			}
		}
		for(i=0;i<=n;i++)dp[i][i][0]=1;
		for(len=1;len<=n;len++)
		{
			for(l=0;l+len<=n;l++)
			{
				r=l+len;
				for(i=l+1;i<r;i++)
				{
					for(j=1;j<(1<<n);j++)
					{
						for(t=0;t<n;t++)
						{
							cmsk=j;
							for(p=t;p<n&&(j>>p&1^1);p++)
							{
								cmsk|=(1<<p);
								dp[l][r][cmsk]=(dp[l][r][cmsk]+dp[l][i][j]*sgvl[i][r][t][p+1])%mod;
							}
						}
					}
				}
				for(j=1;j<(1<<n);j++)
				{
					for(i=0;(j>>i&1^1);i++);
					for(t=n-1;(j>>t&1^1);t--);
					sgvl[l][r][i][t+1]=(sgvl[l][r][i][t+1]+mod-dp[l][r][j])%mod;
				}
				for(i=0;i<n;i++)
				{
					cmsk=0;
					for(t=i;t<n;t++)
					{
						cmsk|=(1<<t);
						dp[l][r][cmsk]=(dp[l][r][cmsk]+sgvl[l][r][i][t+1])%mod;
					}
				}
				if(len==1)continue;
				for(j=0;j<(1<<n);j++)dp[l][r][j]=(dp[l][r-1][j]+dp[l][r][j])%mod;
			}
		}
		for(i=0;i<=n;i++)
		{
			for(j=0;j<(1<<n);j++)
			{
				dp2[i][j]=0;
				dpvl2[i][j]=0;
			}
		}
		dp2[0][0]=1;
		for(l=0;l<n;l++)
		{
			for(j=0;j<(1<<n);j++)
			{
				dp2[l+1][j]=(dp2[l+1][j]+dp2[l][j])%mod;
				dpvl2[l+1][j]=(dpvl2[l+1][j]+dpvl2[l][j])%mod;
			}
			for(r=l+1;r<=n;r++)
			{
				for(j=0;j<(1<<n);j++)
				{
					for(i=0;i<n;i++)
					{
						cmsk=j;
						for(t=i;t<n&&(j>>t&1^1);t++)
						{
							cmsk|=(1<<t);
							dp2[r][cmsk]=(dp2[r][cmsk]+dp2[l][j]*sgvl[l][r][i][t+1])%mod;
							dpvl2[r][cmsk]=(dpvl2[r][cmsk]+(dp2[l][j]+dpvl2[l][j])*sgvl[l][r][i][t+1])%mod;
						}
					}
				}
			}
		}
		ans=0;
		for(j=1;j<(1<<n);j++)ans=(ans+dpvl2[n][j])%mod;
		cout<<ans<<'\n';
	}
	return 0;
}

const int N=1e6+5; vector<int> tree[N]; int down[N]; int up[N]; int id; bool visited[N]; int p[N]; void dfs(int u) { if(visited[u])return; down[u]=++id; visited[u]=1; p[id]=u; for(auto it:tree[u]) { dfs(it); } up[u]=++id; } bool comp(pair<int,int>&a,pair<int,int>&b) { return a.first>b.first; } void solve() { int n; cin>>n; for (int i=1; i<=n; i++) { tree[i].clear(); id=0; visited[i]=0; } vector<int>wt(n+1,0); for(int i=1;i<=n;i++) { cin>>wt[i]; } for(int i=0;i<n-1;i++) { int x,y; cin>>x>>y; tree[x].push_back(y); tree[y].push_back(x); } dfs(1); vector<pair<int,int>>ans; for(int i=1;i<=n;i++) { int l=down[i]; int r=up[i]; for(int j=1;j<=id;j++) { if(j>=l && j<=r)continue; if(p[j]<=n && wt[p[j]]>wt[i]){ ans.push_back({wt[i],i}); } } } for(int i=0;i<=3*n;i++) { p[i]=0; } if(ans.size()==0) { cout<<0<<endl; return; } sort(ans.begin(),ans.end(),comp); cout<<ans[0].second<<endl; }

Comments (105)

Write comment?

MathModel

21 hour(s) ago, # |

← Rev. 2 →

+15

In Editorial of C :

Unable to parse markup [type=CF_MATHJAX]

Fixed

→ Reply

karanarjunjr

Unable to view Editorial for problem C

SmartyNotchy

+34

We're not beating the speedforces allegations with this one!

21 hour(s) ago, # ^ |

+32

In all seriousness I enjoyed A-C even if they were rather guessable, but there really should have been a problem in between C and D/E1

utkarsh031

5 hours ago, # ^ |

why so serious

RE_Prince

+44

D>>>>>>>>>>>>>>>>>>>>>E1

Noobish_Monk

17 hours ago, # ^ |

The score for E1 was less than for D

16 hours ago, # ^ |

well yeah, i didnt expect E to be easier

arctano

nah, no way, I got C wrong cus I forgot to use LL

303138777 and 303120425

julianbl

same, spent like 20 min trying to find the mistake, but got it eventually

array

same. i spent almost 2 hours + 5 WAs.. T_T

adiroy2

First time i solved a b AND c in div1+2. Hope to get +ve delta :). thank you!

esh_war2

19 hours ago, # ^ |

Your consistency is just awesome

Codender

Me too! (Although this was my first Codeforces contest...)

ashish1729

12 hours ago, # ^ |

yeah I saw your profile too, what a consistent account, keep it up.. really awesome

9 hours ago, # ^ |

Can't believe I reached specialist! Ngl I think I will now do a few virtuals and solve 16-1800s now I guess, before my next contest

Spark1707

Great to see your progress brother. And the consistency is really inspiring. Congratulations for becoming specialist

jatt_da_muqabla

for B should the condition be ti>2max(i−1,n−i)

SSerxhs

We are fixing it

knoothopian

I think for C, one could additionally use the fact that in an array of length $$$n$$$, the sum of differences is $$$a_n - a_1$$$. Thus if $$$a_n < a_1$$$, we reverse else not.

rick3300

Exactly, that's why I had done too!

walkieme

In the editorial for B it should be max instead of min

Rating Prediction

avnlk

20 hours ago, # ^ |

← Rev. 3 →

+20

There should be a row with the average and median. ^_^;

I like the variance in predictions

I'd like to update it after the actual rating comes out and calculating the errors together

Benq

+12

On the contrary, I'm surprised that the variance isn't higher, I personally would have rated H < G < E2 (unfortunately, I spent most of the contest debugging my approach for E2).

TheArcticWolf

C clearly had more than expected solves in the contest. shame on these cheaters.

800 800 800 2400 1600 ? 2700 ? ?

sparkfire

+14

The editorial for C and D is not very clear. What does fa mean in D?

The father of $$$u$$$.

not convinced(or did not fully understand) the proof of problem C. please help.

Assuming that in the optimal answer the sequence of operations is 1211121221.

Consider swapping two adjacent operations: 12→21 ... which is equivalent to taking the negation.

so, are we proving that instead of doing 1211121221 we can simply do 1111112222? Then we may need to do negation of all elements based on number of 12 operation swaps?

and of course since 111111 -> no-op we might as well only do 2222?

I think I understand now. However please let me know if I understood something incorrectly. thanks!

No, the argument is that operation 1 simply negates each term of the array, thereby all it does is change the sign of the sum. Thus, it is enough to perform operation 2 and take the absolute value of the sum at each step (Because if the sum was negative then you could have performed operation 1 before and gotten $$$-sum$$$)

Sorry for mixing up 1 and 2. It has been corrected now, and your understanding is correct.

Got it, Thanks!

arujbansal

But why doesn't it matter what the array looked like before you perform operation 1 or 2? The 12 -> 21 negating sum condition only applies to the sum right. But we can get different sums by performing operation 2 on different arrays (different elements at each index). Am I wrong?

For example, applying 2 to 1212 gives you a different individual elements than applying it to 2121. Wouldn't it?

hihitherethere

Think 2121 gives same output as 11

gabriel

Yeah, I was wondering exactly that, and the editorial lacks so much explanation that you really can't assume that the negative of the array won't generate possibly new (and larger) sums after you apply some other operations on it. That's why I wrote a comment explaining it with proofs of (almost) everything (except trivial things). I think you could like my explanation, so, please, take a look at my comment (somewhere below on this comment section).

nathanballman

I feel like the editorial for B is incomplete, especially for beginners. The most crucial part of the solution is that there never exists a part of the sequence that goes: {i...i+1 ...i... i+1} without visiting both ends of the array which allows one to show that the only optimal sequence is one in which we bounce back and forth from opposite ends of the array.

20 hours ago, # |

What is meant by "Since 2 does not change the sum of the sequence" in C's editorial? Doing the operation changes the sum right?

Same as above, sorry for mixing up 1 and 2. I have corrected it, but it takes some time to update.

The_Last_Run

dp solution of problem C[Check303116516..]

maruf004

Can anybody explain why this is got WA. I can't understand the editorial for problem C. Here's the submission of c — https://codeforces.me/contest/2062/submission/303119038

BLACKCOFFEE-420

B>>>>>>>>>C

itsraajjjuuuu

I did B in like 5 min and 40 minutes for C, why people with good ratings are fumbling in B? even CM in friendlist got 3WA on B. Overthinking?

justplaygame

B is nice problem , but it was not harder then c

Knight_Fury_

Quite helpful. Thank you

PAinO5

-35

poor contest and even worse editorial

PG_Mazen

+54

The editorial for D is made for people who have successfully solved the problem in the contest. The editorial is not clear at all !

Surya__1234

Even I feel so,Can Someone Please provide a more detailed explanation.

timg8710

11 hours ago, # ^ |

+22

The operation can be rephrased as follows: choose any edge in the tree, consider the two subtrees resulting from removing that edge, choose one of those subtrees, and increment all values in it by 1.
Consider any assignment of initial values to the nodes. For any two nodes connected by an edge, if they have different initial values, they can only become equal if we perform the operation selecting the edge between them, and incrementing the subtree of the smaller node.
Now, consider what the value of node i will be in the end. We can find this value by rooting the tree at i. The final value after the tree becomes balanced will be val[i] + sum(max(0, val[u] — val[par[u]])). Basically if val[par[u]] < val[u], we will need to increment everything above u.
We can prove that actually rooting at any node j != i will yield the same result as i. One way to prove this is by considering what happens to the result when we move from i to a neighbor.
Finally, this means we can just root arbitrarily, and greedily minimize sum(max(0, val[u] — val[par[u]])).

8 hours ago, # ^ |

I hope there was an option to pin a comment!

This really helped. Thanks :)

masonpop

I think it's quite clear for me. Can u explain which part made u confused pls?

Super_D_Man

Hi, I really don't understand the second part of the editorial. I don't see how we get to the conclusion that au should always be no less than the maximum value of its child nodes av. The proof involves something about decreasing ai and I don't know why do we need to decrease anything?

hmm just have a look to the formula ig. let u be the father and v be one of its child,and it's $$$\sum \max(a_v-a_u,0)$$$. let $$$M$$$ be the maximum value of a's among all these $$$v$$$. if we have $$$a_u$$$ smaller than $$$M$$$, just consider what will happen if we "push" the value of $$$a_u$$$ to bigger side(and of course,smaller than $$$r_u$$$). if we set $$$a_u\rightarrow a_u+1$$$, the value of $$$\sum \max(a_v-a_u,0)$$$ will decrease at least one, while the value of $$$\max(a_u-a_{fa},0)$$$ will increase at most one. thus it's not worse than the previous $$$a_u$$$. so it's always optimal to set $$$a_u$$$ bigger when $$$a_u\le M$$$, which lead to the observasion in the editorial.

11 minutes ago, # ^ |

Thanks a lot

4 hours ago, # ^ |

"decrease" means comparing taking the maximum with maximum -1

10 minutes ago, # ^ |

I love you

3 hours ago, # ^ |

Thanks, but it's okay now. One of my friends already explained it to me.

18 hours ago, # |

Please don't use symbols that are hard to understand in editorials like in E1 for example: w,dfn,nfd,pre,suf,low

I am really trying to understand the solution, but I can't really fathom it due to them.

randombernie

18 hours ago, # ^ |

Yes. I can't identify/understand which algorithm is being used in the solutions for E1, and the variable names are far from helpful.

low is definitely not a good name as a variable since it collides with the low in tarjan algorithm. maybe using end or ed will be better?

PLDlS

For people learning tarjan algorithm, they often come up with low because it has similar operations (max the dfn).

dfn stands for dfs number, which is the order of the DFS process in the algorithm. e.g., dfn[root] = 1.

low stands for the maximun dfn in the subtree. e.g., low[root] = n.

I use low as the variable name too and I just come up with the name myself. Is this a coincidence?

119 minutes ago, # ^ |

well maybe it's just different to everyone :D

jkulanko

13 hours ago, # ^ |

Not sure why you're being downvoted. I thought the same thing.

I am also not able to make sense of techniques used to find greater elements in subtree from the code, but now the editorial has been updated and it explains what they are doing.

7 hours ago, # ^ |

It is actually pretty clear now after they updated.

Can someone explain why this code fails:

https://codeforces.me/contest/2062/submission/303155437

TheEgoist

Can someone tell me why it doesn't get TLE? I literally brute-forced the operations and memoized the array itself. Submission Thanks

All the second operation does is multiply the array by -1 after the next operation of the first type, this means applying the second operation twice undoes itself no matter how many operations of type one are performed inbetween. Hence you only have 2*N states.

KeNaj712

+10

I somehow misread the problem B and thought we need to spend an additional second if we want to reset the clock. Does anyone know if this version of the problem is solvable?

I'm pretty sure the strategy of simply walking back and forth still is optimal, so you can solve the problem by updating the length of the walk as you have to reset an additional clock each cycle.

15 hours ago, # ^ |

It doesn't really work, e.g. in test like 10 100 100 100 100 you can just restart "big" clocks one by one between restarting the small one and the answer would be YES, whereas your strategy fails.

16 hours ago, # |

Below I explain the solution to exercise C, doing exactly what the editorial didn't do.

Let's call the reverse instruction as '1' and the difference instruction as '2'. Let's create a new instruction, the "negative" instruction, that I will call from here on as '3'. That instruction multiplies each element of the input array by -1.

Theorem 1) Applying operation 1 two consecutive times is the same as not doing anything (proof omitted)

Theorem 2) Applying operation 3 two consecutive times is the same as not doing anything (proof omitted)

Theorem 3) Applying operation 1 does not change the sum of the input array (proof omitted)

Theorem 4) Applying operations "12" to a sequence is the same as applying operations "231".

Proof:

Let the input array be [a1, a2, a3, ..., an]. Applying "12" on it leads to:

After 1: [an, a(n-1), a(n-2), ..., a1]

After 2: [a(n-1)-an, a(n-2)-a(n-1), ..., a1-a2]

Applying "231" to [a1, a2, a3, ..., an]:

After 2: [a2-a1, a3-a2, ..., an-a(n-1)]

After 3: [a1-a2, a2-a3, ..., a(n-1)-an]

After 1: [a(n-1)-an, a(n-2)-a(n-1), ..., a1-a2]

So, the sequences of operations "12" and "231" are equivalent.

Theorem 5) Applying operations "23" to a sequence is the same as applying operations "32".

Let the input array be [a1, a2, a3, ... an]. Applying "23" on it leads to:

After 2) [a2-a1, a3-a2, ..., an-a(n-1)]

After 3) [a1-a2, a2-a3, ..., a(n-1)-an]

And applying "32" to [a1, a2, a3, ... an]:

After 3) [-a1, -a2, -a3, ..., -an]

After 2) [a1-a2, a3-a2, ..., a(n-1)-an]

So, the sequences of operations "23" and "32" are equivalent.

===================

With those theorems in hand, let's solve the exercise.

Let s be any sequence of operations that leads to the maximum possible sum. For example, s may look something like this:

s = 11112221212212112111

According to Theorem 1, I can remove every pair of consecutive 1's, which would give me the following sequence:

s = 222121221221

According to Theorem 3, I can remove the last 1 of the sequence:

s = 22212122122

Now, from the left to the right of the sequence, let's change any appearance of "12" to "231". That won't change the final sum because Theorem 4 says those instructions are equivalent. If, while changing "12" to "231", we end up with consecutive 1's, we simply remove them (because of Theorem 1). If we end up with a 1 on the end, we simply remove it (because of Theorem 3). Below I simulate that process:

s = 222231122122 (Theorem 4)

s = 2222322122 (Theorem 1)

s = 22223222312 (Theorem 4)

s = 222232223231 (Theorem 4)

s = 22223222323 (Theorem 3)

As you can see, we ended up with a sequence made only of 2's and 3's. Now, let's apply Theorem 5 several times and move all the 3's to the end:

s = 22222222333

And now let's remove consecutive pairs of 3's, because Theorem 2 allows us to:

s = 222222223

This simulation gives us a general idea of what any optimal sum sequence looks like: it is either:

An empty sequence (s = "")
A sequence of 1 or more 2's followed by none or only one 3 (s = "222...2223", s = "22...2", etc)

Now, our algorithm should simply try all of those sequences and grab the one with the highest sum, as shown here: (303162845)

shaunak81

Thank you for such clear explanation.

I'm happy it was helpful =)

ammahmed004

15 hours ago, # |

is there any solution for E2 using small to big and segment tree

this is my attempt for this problem. if anyone can explain why my code gives me wa or gives a corner case for my code thanks.

https://codeforces.me/contest/2062/submission/303162086

vuysztrcKJBHVIUVbkjbkhj

13 hours ago, # |

Sadly i was not aware that if we resubmit a accepted qestion then the time of resubmition will be considered for that problem and my rank droped by 4000.

Can anyone recommend me some resources to solve E1? I got the idea in the contest but the editorial isn't clear about how to achieve the idea. Looking at others solutions, I feel like there's a gap in my knowledge somewhere on the topic.

I have updated more detailed information on how to achieve it.

Thanks! That helps a lot.

guesswhetherIamXJK

I didn’t solve D just because I didn’t consider the tree with only one point, which resulted in me doing nothing for the last hour. That's funny.

LiuXingJian

12 hours ago, # |

Thanks for the excellent contest. Problems D,E and F are all intersting!

Filaret14

11 hours ago, # |

How is the construction of array $$$a$$$ in Problem D’s editorial optimal?

oooooorz

9 hours ago, # |

problem C, the case 9 9 7 9 -9 9 -8 7 -8 9 why the answer is 2056?

-archit-

8 hours ago, # |

Can someone who have solved E1 tell how they solved it and came to the conclusion their method was right?

MinbaevBaiysh

56 minutes ago, # ^ |

At first we need to sort all node by their weight, then our strategy is choosing second biggest node (when it sorted by weight), and checking if in its subtree contains all bigger weight node or not, if not we will choose it, next player will choose the biggest, so there will be no other option, so we win. If it contains all, just check next smaller weights, until we find answer. If we dont find it, then there no answer. I solved that intuitively, that's why I wasn't sure if its correct or not :)

7 hours ago, # |

Problem D: Anyone getting Runtime Error in Test 8? Please help me how my solution got accepted in 7 test cases but runtime error in test 8?

https://codeforces.me/contest/2062/submission/303196494

6 hours ago, # ^ |

I found the answer, thanks to Eunha His code helped me understand the problem. The recursion limit in Python is too low for test case 8 so we have to use a stack.

Surprisingly adding sys.setrecursionlimit(500000) is also not solving the problem.

Anyone knows any other way of increasing recursion limit? To do this without stack using recursive dfs?

https://codeforces.me/blog/entry/91490#comment-800269

Found a way to run recursive dfs in problem D.

See my solution: 303208534

PS: pajenegod you are the python god!

Neev4321

How does the C++ solution of D work?
Why does this line erase(e[v], u); not TLE?
Should it not be $$$O(n^2)$$$?

djm03178

The total time these erase operations take throughout the whole DFS is $$$\mathcal{O}(E)$$$, because this operation is done for each vertex only once and for each vertex it takes time proportional to the number of edges attached to it. Since this is a tree, it's also $$$\mathcal{O}(V)$$$.

Got it.

walterhwhite

6 hours ago, # |

Is there any proof for B ?

shinigami0031

why O(n^2) gives TLE in E1, even when time limit is 4 sec ?

55 minutes ago, # ^ |

N^2 is about 1e10 operations, which will be done in 100 seconds.

2c237c6

Is the reason why the first comparison in question C did not take an absolute value compared to the prefix sum without operation?

Kami_1276

4 hours ago, # |

2062B Clockwise ans in c++ is wrong my code is also similar except var name . testcase 1 both code passed but testcase 2 failed both.

Xiao_2710

This had such an uneducative C, the previous round's B was better than this round's C. Just simple observation that sum of differences is an-a1,solves this.

mercyknight100

3 hours ago, # |

Anyone have material For understanding E1 problem i see sol but that is beyond my understanding since some are using eulertour or something can someone provide problem resource for this pls

51 minute(s) ago, # ^ |

I solved it with small to large trick, it was needed to maintain how many nodes V in subtree U satisfy this condition: w[U] < w[V]. Here you can read more details about it.

46 minutes ago, # ^ |

Thanks bro!

Hooded_Hood

E1 editorial says "Additionally, we can enumerate the nodes in descending order of wi and maintain their lowest common ancestor (LCA). If the LCA of all v satisfying wv>wu is not a descendant of u, then there must exist a node v outside the subtree of u that satisfies wv>wu."

what if there are n/2 nodes with maximum w[v] and we need to check each one of them with every other w[u] to find the answer and exactly the last one we check is the answer?

isn't it O(n^2lg)? or even O(n^2)?

can someone explain if I'm wrong?

2 hours ago, # |

Don't know if anyone can't understand the implementation of E2 from official editorial but here is my own code, based totally on what the editorial said, using LCA and basic data structures. maybe it's easier to understand?

Never_ending_debugging

88 minutes ago, # ^ |

I will give it a try!! Thank you!

89 minutes ago, # |

You can also use Small To Large for problem E1.

Idea : - If the current value don't contain the previous larger values then the node containing it is definitely winnable. Or if it does contain, if the previous larger values do exist outside of the subtree of this node then it is also a winnable node.

This is my code :

https://codeforces.me/contest/2062/submission/303225889

StarSilk's blog