CS academy Round 40

It seems that I need more practice.

Problem link

A Erase Value

int n;
int val[maxn];

void solve()
{
	sa(n);
	
	int sum = 0;
	repp(i,1,n)
	{
		sa(val[i]);
		sum+=val[i];
	}
	repp(i,1,n)
	{
		int cnt=0;
		repp(j,1,n)
		{
			if(val[i]==val[j])continue;
			cnt+=val[j];
		}
		sum=min(sum,cnt);
	}
	printf("%d\n", sum);
}

B Move the Bishop

A straightforward BFS.

int r1,c1,r2,c2;
int val[10][10];

void solve()
{
	sa(r1),sa(c1),sa(r2),sa(c2);
	memset(val,-1,sizeof(val));

	queue< pair<int,int> >que;
	que.push(mp(r1,c1));
	val[r1][c1] = 0;
	while(!que.empty())
	{
		auto now = que.front();
		que.pop();
		int x = now.first;
		int y = now.second;
		repp(k,1,4)
		{
			repp(step,1,10)
			{
				int nx = x + step*dx44[k];
				int ny = y + step*dy44[k];
				if(nx>=1&&nx<=8&&ny>=1&&ny<=8)
				{
					if(val[nx][ny]==-1||val[nx][ny]>val[x][y]+1)
					{
						val[nx][ny]=val[x][y]+1;
						que.push(mp(nx,ny));
					}
				}
			}
		}
	}

	printf("%d\n", val[r2][c2]);
}

C Switch the Lights

Given the initial state of $n$ lights, every position has a switch that flips $[i,r_i]$ at cost $c_i$. Find the minimum final cost, or output $-1$ if it is impossible.

Think carefully: the solution is forced. Scan from $1$ to $n$; if light $i$ is on, you must flip $[i,r_i]$. Keep tracking the state as you go.

int n;
char val[maxn];
int v[maxn];
int r[maxn],c[maxn];

void solve()
{
	sa(n);
	scanf("%s",val+1);
	repp(i,1,n)
	{
		sa(r[i]);
	}
	repp(i,1,n)
	{
		sa(c[i]);
	}
	ll cost = 0;
	int state = 0;
	repp(i,1,n)
	{
		state ^= v[i];
		if(state ^(val[i]-'0'))
		{
			state ^= 1;
			cost += c[i];
			v[r[i]+1] ^= 1;
		}
	}
	printf("%lld\n", cost);
}

D Restricted Permutations

Given $n$ numbers and the relative ordering of each $i$ and $i+1$, count the valid permutations.

Dynamic programming: for $x$ numbers, count the ways for $x$ to occupy each position from $1$ to $x$, then transition according to the relation between $x$ and $x+1$.

int n;
int val[2005];

vector<int>PlaceBefore(vector<int>&val)
{
	int n = val.size();
	vector<int>next(n + 1, 0);

	int sum = 0;
	for (int i = n - 1; i >= 0; i--)
	{
		sum += val[i];
		sum %= mod;
		next[i] = sum;
	}
	return next;
}

vector<int>PlaceAfter(vector<int>&val)
{
	int n = val.size();
	vector<int>next(n + 1, 0);

	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		sum += val[i - 1];
		sum %= mod;
		next[i] = sum;
	}
	return next;
}

void solve()
{
	sa(n);
	repp(i, 2, n)
	{
		sa(val[i]);
	}
	vector<int>pos = { 1 };
	repp(i, 2, n)
	{
		if (val[i])
		{
			pos = PlaceAfter(pos);
		}
		else
		{
			pos = PlaceBefore(pos);
		}
	}

	int sum = 0;
	for (auto itr : pos)
	{
		sum += itr;
		sum %= mod;
	}
	printf("%d\n", sum);
}

E Direct the Graph

Given an undirected complete graph on $n$ vertices, orient every edge to maximise the number of directed 3-cycles. Output that maximum and a construction.

The answer is: all triangles minus bad triangles.

All triangles: $C(n,3)$.

A bad triangle is formed by any two edges pointing in the same direction at one vertex.

ll n;
void solve()
{
	cin>>n;
	ll ans = n*(n-1)*(n-2)/6;
	ll bad = (n-1)/2;
	bad = (bad*(bad-1)/2+(n-1-bad)*(n-1-bad-1)/2);
	bad = n*bad/2;
	ans = ((ans-bad)%mod+mod)%mod;
	cout<<ans<<endl;
	ll cnt = (n-1)/2;
	for (int i=n-1;i>=0;i--)
	{
		string c1(i-cnt,'0');
		string c2(cnt,'1');

		cnt-=1;
		cnt=max(cnt,0ll);
		cout<<c1<<c2;
	}
}