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

№	Пользователь	Рейтинг
1	Benq	3857
2	jiangly	3810
3	maroonrk	3534
4	tourist	3528
5	Kevin114514	3510
6	turmax	3411
7	Um_nik	3387
8	Radewoosh	3367
9	heuristica	3322
10	strapple	3317

№	Пользователь	Вклад
1	Qingyu	158
2	maspy	150
3	Um_nik	146
4	Errichto	139
5	adamant	136
6	maroonrk	134
7	DNR	133
8	nik_exists	131
8	Dominater069	131
10	Proof_by_QED	130

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;
}

RMSE

MAE

shstyle.

800

1100

1400

2300

2000

134.16

100.00

Phantasmagorias

800

1300

1500

2000

1600

2100

2600

3000

3200

433.33

366.67

SSerxhs

800

1200

1900

1800

2500

2700

3100

3500

272.85

211.11

wjy666

800

900

1200

1900

2600

2700

3000

3500

247.21

166.67

Tobo

900

1200

1600

2300

2000

2600

2800

3000

3300

284.80

233.33

Cai_Guang

900

1200

1800

2600

2100

2300

2700

2900

3100

432.05

377.78

yorisou

800

1200

1400

2000

1700

228.04

200.00

Theresa_Apocalypse

800

1200

1700

2000

291.55

200.00

StarSilk

800

1100

1200

2000

1700

2700

2500

2800

3300

324.89

255.56

LuCpp

800

1100

1400

2100

2000

2700

2900

3200

3300

185.59

144.44

golomb

800

1200

1400

2100

3000

258.20

200.00

sabino1

800

1300

1400

1800

1600

1900

536.97

416.67

_Sherbiny

800

1100

1300

2100

1900

118.32

100.00

add10k

800

1500

1800

2000

1900

2500

2300

444.01

371.43

average

814

1185

1450

2084

1878

2433

2650

3000

3314

305.66

254.44

median

800

1200

1400

2000

1900

2500

2700

3000

3300

290.59

244.44

answer

800

900

1200

2200

2000

3000

2900

3500

0.00

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; }

Комментарии (129)

Показать архивные | Написать комментарий?

MathModel

19 месяцев назад, скрыть # |

← Rev. 2 →

+15

In Editorial of C :

Unable to parse markup [type=CF_MATHJAX]

Fixed

→ Ответить

karanarjunjr

Unable to view Editorial for problem C

pilliamw

+42

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

19 месяцев назад, скрыть # ^ |

+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

RE_Prince

+53

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

Noobish_Monk

The score for E1 was less than for D

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

adiroy2

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

esh_war2

Your consistency is just awesome

Codender

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

ashish1729

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

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

sreecharanreddypacharla

Congratulations for consistency

jatt_da_muqabla

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

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 \lt a_1$$$, we reverse else not.

rick3300

Exactly, that's why I had done too!

← Rev. 3 →

Rating Prediction

ID	A	B	C	D	E1	E2	F	G	H	RMSE	MAE
shstyle.	800	1100	1400	2300	2000					134.16	100.00
Phantasmagorias	800	1300	1500	2000	1600	2100	2600	3000	3200	433.33	366.67
SSerxhs	800	1200	1200	1900	1800	2500	2700	3100	3500	272.85	211.11
wjy666	800	900	1200	1900	1900	2600	2700	3000	3500	247.21	166.67
Tobo	900	1200	1600	2300	2000	2600	2800	3000	3300	284.80	233.33
Cai_Guang	900	1200	1800	2600	2100	2300	2700	2900	3100	432.05	377.78
yorisou	800	1200	1400	2000	1700					228.04	200.00
Theresa_Apocalypse	800	1200	1700		2000					291.55	200.00
StarSilk	800	1100	1200	2000	1700	2700	2500	2800	3300	324.89	255.56
LuCpp	800	1100	1400	2100	2000	2700	2900	3200	3300	185.59	144.44
golomb	800	1200	1400	2100	2100			3000		258.20	200.00
sabino1	800	1300	1400	1800	1600	1900				536.97	416.67
_Sherbiny	800	1100	1300	2100	1900					118.32	100.00
add10k	800	1500	1800	2000	1900	2500	2300			444.01	371.43
average	814	1185	1450	2084	1878	2433	2650	3000	3314	305.66	254.44
median	800	1200	1400	2000	1900	2500	2700	3000	3300	290.59	244.44
answer	800	900	1200	2200	2000	3000	2900	3500	3500	0.00	0.00

avnlk

+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

+22

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).

Hey, how do I quote something like that?

"I like the variance in the predictions" in a different colour?

example

"> example"

thanks

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$$$.

bugdone

Why not add this to the editorial?

jonnnnnsinaga

why is it called the father and not parent ??

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!

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

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.

lwenkai

What does this mean?

there never exists a part of the sequence that goes: {i...i+1 ...i... i+1} without visiting both ends of the array

Imagine we visited {...2, 3, 2, 3...} at some point in our traversal. This is sub-optimal as the clocks after the first two moves are the same as after the fourth moves, but in the later all other clocks are two less. Hence we should delete the second {2,3};

This logic can be extended to any subsequence of the form {i, i+1, ...i+k,i+k-1,...i+1, i, i+1, ... i+k} where we can delete the everything after the first i+k and get a strictly better solution.

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.

Wax

dp solution of problem C[Check303116516..]

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

PG_Mazen

+57

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

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]])).

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.

Thanks a lot

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

I love you

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

walkieme

+12

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

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

+10

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?

well maybe it's just different to everyone :D

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.

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

+13

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?

-8

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.

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.

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 =)

Cinatit

Thank you so much! The best explanation I could find. Please, SSerxhs , set this as the official editorial for the problem C, I beg you!

ammahmed004

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

+11

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.

jkulanko

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.

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

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

Filaret14

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

Yeah I've got it figured out today. Here's my train of thoughts:

The goal is to minimize

$$$ans:=a_1+\sum_{u=2}^{n}\max\{0,a_u-a_{\text{fa}[u]}\}$$$

We could first try finding this value for all the other nodes of the tree before getting to the root.

$$$ans_u:=a_u+\sum_{v|u\in anc_v}\max\{0,a_v-a_{\text{fa}[v]}\}$$$

Setting $u=1$ yields $$$ans=ans_1$$$.

We try to find the minimum of $$$ans_u$$$ for every node $$$u$$$ first. Assume that we have fixed $$$a_v$$$ for all $$$v$$$ is in the subtree of $$$u$$$ when we fix node $$$1$$$ as root of the tree.

First try setting $$$a_u$$$ to $$$\max\{a_v\}$$$. There's no point in increasing $$$a_u$$$ as doing so would only increase $$$ans_u$$$. So $$$a_u\leq\min\{r_u, \max\{a_v\}\}$$$.

Decreasing $$$a_u$$$ by $$$1$$$ would result in a increment of $$$1$$$ in $$$\max\{0, a_v-a_u\}$$$ for at least one of $$$v$$$ for $$$v$$$ that satisfies $$$\text{fa}[v]=u$$$.

Thus to minimize $$$ans_u$$$ when all $$$a_v$$$ is fixed for every $$$v$$$ in the subtree of $$$u$$$ except for $$$u$$$ itself, it is optimal for $$$a_u$$$ to take the value of $$$\max\{l_u, \min\{r_u, \max\{a_v\}\}\}$$$.

It is optimal to construct $$$a$$$ such that $$$ans_u$$$ takes its minimum for every $$$u$$$. If we can get the value of every node in the subtree of $$$u$$$ to be $$$ans_u$$$, then with one operation in which we increase the value of all nodes in subtree of $$$u$$$ by $$$1$$$ while considering $$$\text{fa}[u]$$$ as the root of the tree, we could achieve the same value for $$$ans_1$$$ when $$$ans_u$$$ is not at its minimum. In other words, minimizing $$$ans_u$$$ wouldn't increase $$$ans_1$$$.

-archit-

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

conqueror_of_AloMeister

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 :)

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

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.

shinigami0031

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

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

mercyknight100

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

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.

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?

Yakumo_Ran

You don't need to recalculate them. It's similar to prefix sum: maintain the prefix lca in decreasing order of $$$w_i$$$.

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?

TyroWhizz

Does anyone have proof for why solution for D actually works?

imho, I don't see myself looking at D and thinking ohh well this should work. (maybe my skill issue).

Apart from that I wanted to say that I loved problem F.

taha06

I will explain how i approached the problem:

Lets root the tree at node $$$1$$$. We need to find the minimum value $$$V_u$$$ for the subtree of some node $$$u$$$. (we can always increase the value later if we need)

Assume the subtree of all of the children of $$$u$$$ have an equal value $$$V_i$$$. we have two cases:

$$$V_i \leq R_u$$$, we can just increase that subtree till $$$L_u \leq V_i$$$
$$$V_i \gt R_u$$$, we need to increase all of the tree except that subtree, the final answer increases by the difference $$$V_i - R_u$$$ and $$$V_i$$$ "decreases" till its at most $$$R_u$$$ (the only thing that changes is their relative difference)

The minimum value of the node $$$u$$$ is the maximum value among $$$V_i$$$ and the minimum value of a leaf is just $$$L_u$$$.

Code

The thing that is bugging me is why choosing any root for this operation is fine?

Consider an operation: root the tree at node $$$u$$$ and increase the subtree of node $$$v$$$ ($$$u \neq v$$$). we can always move the root $$$u$$$ towards $$$v$$$ as long as $$$u \neq v$$$ and the operation will have the same effect.

So the operations can be simplified to two adjacent nodes (an edge) or equal nodes (which just increases the entire tree).

That means if we root at any node $$$u$$$, the operation can be done on some edge and increase either the entire tree, the entire tree except a subtree or only the subtree. so we can just consider one root.

weiron_RX

Hello, pls someone help me to find mistake in my solution of D: My idea is that I am taking a leaf and its parent and trying to make them equal in minimal amount of steps, then just deleting leaf, cause it will behave like its parent

my submission

kr25161

the editorialist must explain in the D, why taking any node as root for the greedy strategy yields in same answer.

overnap

The DP of F is fun, but I have a question. How do you approach the required transformation of the max? Are these transformations common? I don't think I can come up with one even if I think about it for a week. I wonder how the rankers came up with it.

mike_chu

+1，I have absolutely no idea how to come up with this transformation. It's like magic...

Dominater069

+23

It is a fairly standard transformation of rotating the plane by 45 degrees
It is not necessary to solve the problem this way, you can argue the same without ever rotating the plane.

The actual observation is that a[i] + b[j] >= a[j] + b[i] means that a[i] — b[i] >= a[j] — b[j], and hence sorting by a — b is useful. You dont need a transformation to see this, and this was my first observation in the problem (not transforming the coordinates but observing when max takes one of the terms instead of the other)

jeroenodb

I had the following thought process: Place $$$2n$$$ points on the plane at positions $$$(a_i,b_i)$$$ and at $$$(-b_i,-a_i)$$$. If you take the distance metric that takes the max of the delta x and y, and calculate the distance between a positive and a negative point it is exactly the distance in the problem. Now because we have "king" distance it is a natural trick to turn the plane 45 degrees to convert to manhattan distance, as independence of coordinates could simplify things. From here the rest of the editorial eventually follows.

tmobradovic

Can you explain the last two senetences?
How can we "convert" king distance to manhattan distance by rotating the plane?

If we have a point with coordinates (x,y) distances from (0,0) (some ai and bi could be 0, says the problem) are king: max(x,y) and manhattan: x+y, aren't they?
By rotating them by 45 degrees coordinates will be ((x-y)/sqrt(2),(x+y)/sqrt(2)). Distances from (0,0) are king: max((x-y)/sqrt(2),(x+y)/sqrt(2)) and manhattan: x*sqrt(2).
First(before rotation) king distance is not like second(after rotation) manhattan distance. Furthermore, neither of the 4 distances are matching.

You can read more about this transformation here: Old codeforces blog Or searching "rotating plane by 45 degrees codeforced", with your favourite search engine.

Thanks! :)

bashkort

The initial formula is kinda ugly, and a natural thing to do is to try to make one side of the formula depended only on $$$i$$$, and the other only on $$$j$$$.

employed

in problem D

when the values are fixed its easy to prove that any root works but since L , R change , how to prove it'll never affect the final answer ?

Choosing a root has nothing to do with the operations that need to be performed. Selecting a root is simply to focus on observing how that root changes.

Vipattim_Jayati

17 месяцев назад, скрыть # ^ |

can we prove it like this since the function is convex in convex domain and since we want to minimize the objective function therefor there will be only one op[timum point causing the local optimum to be equal to the global optimum..

I am not sure about the proof

DCSNMGPSSIK

In problem F

How to prove that we need to have 2 vertexes start and end, after that, the rest just appear accord increasing of index (after sorted) ? I got stuck that the path is just a permutation :(

Because all remaining cities contribute x twice, this permutation does not affect x's contribution. Put all cities on the number line according to y, and the problem is like you need to walk from a fixed starting point to a fixed ending point on the number line, and then there are several points on the number line that need to be passed through. And y's contribution to the answer is the total distance you have traveled on the number line. This way, it is easy to see that this movement method obtains the shortest distance.

Oh thank you so much.

I just focus to ai and bi, not xi and yi

But is there any proof according just ai and bi ? Because I think the transfer to xi and yi is quite .... magic and it's hard to me to think about the solution which have xi and yi

Thank you so much :D

LXH-cat

It seems 3 sample inputs of problem H can form 3 quarters of a QR code. Is it a puzzle to a valid QR code?(after filling the missing one) (just curious)

Yes.

As I have mentioned in https://codeforces.me/blog/entry/138835?#comment-1241087

Thanks. I see.

newbie234

maybe i am too retarded to comprehend the problem C solution. Can anyone give me the more detailed explanation about it??

So, i imagine it as like this. The optimal solution could be displayed as an array with elements of the array is either 1 or 2.

Let's call it arr with size of k. So, it'll be like 12111122111.... something

Now, we know that swapping a 12 to become 21 is the same as doing multiplication by -1 to the result. But, i don't see how this couuld works!!

Let's say that we have calculate the sum of the array 12111. Changing it to become 21111 doesn't fkin means that i could multiply it by minus 1, right???

So, where's the correlation between the actual answer and us knowing the correlation between swapping elements and negating the answer ???

Please, my fucking brain has fried for even thinking it.........

alpha1215

first type of operation only changes sign of sum of $$$a$$$
for example if there are two adjacent elements $$$a_1..x,$$$ $$$y..a_n$$$
if you do 1 type opn $$$a$$$ will become $$$a_n..y,$$$ $$$x..a_1$$$
now if you do 2 type opn this adjacent pair contribute $$$x - y$$$
but if you didn't performed 1 type opn it will contribute $$$y - x$$$
so you have to check only abs(sum) for all lengths n to 1

so basically,

check sum of all ( assuming that we do NO operation at all)
until the element is one, wee find the absolute value of the sum of difference array. After than, we do operation 2
Now, the element is one. We can compare our temporary answer witth this element

is that the idea behind that ?

Yes

Falcon__

17 месяцев назад, скрыть # |

In D, why the best ans is the time of root is 1? how about other condition? if can not, should we use change root dp to fix it?

try to change the root by its adjacent vertices

0mar_alnatour

12 месяцев назад, скрыть # |

can someone explain to me problem b (im not understanding the tutorial)

EndpoInt

11 месяцев назад, скрыть # |

Has some one noticed that there are contradictory part of E2's explanation?

Or v must prevent Daiyousei from choosing this u.In other words, either wv≥wu, or u is within the subtree of v" but we know that u represent Daiyousei's choice and v represent Cirno's choice ,which means it is impossible for u is within the subtree of v

Блог пользователя StarSilk