Blog entries - Codeforces

#	User	Rating
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

#	User	Contrib.
1	Qingyu	156
2	nik_exists	150
2	maspy	150
4	Um_nik	143
5	Errichto	139
6	adamant	137
7	AmShZ	135
8	maroonrk	133
9	BledDest	132
10	qwexd	129

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

Full text and comments »

StarSilk's blog