2017 ACM Arabella Collegiate Programming Contest

Chong Wang Lv6
  2017-05-01 20:41:26 2017-05-01 20:41:26 Created   2026-10-09 14:30:20 2026-10-09 14:30:20 Updated  

A set of problems on CF GYM, reportedly only Div. 2 difficulty. The early ones were fine, but the later ones took a long time to finish.

There were two months left before my summer internship, with plenty to do: read more and exercise more.

Problem link

A. Sherlock Bones

Given a binary string, count triples $i,j,k$ such that the number of 1s in $[i,j]$ equals the number of 1s in $[j,k]$.

Count the zeroes between every pair of consecutive 1s, identify the pattern, and calculate each segment’s contribution separately.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
char x[maxn];
int  last_le[maxn], suf[maxn];
vector<int>val;
void solve()
{
	val.clear();
	memset(suf, 0, sizeof(suf));

	int len;
	sa(len);
	scanf("%s", x + 1);

	int last = 0;
	repp(i, 1, len)
	{
		last_le[i] = last;
		if (x[i] == '1')
		{
			last = 0;
		}
		else
		{
			last++;
		}
	}
	repp(i, 1, len)
	{
		if (x[i] == '1')
		{
			val.push_back(last_le[i]);
		}
	}
	if (x[len] == '0')
		val.push_back(last_le[len] + 1);
	else
		val.push_back(0);
	ll ans = 0;
	for (int i = 1; i < val.size(); i++)
	{
		ans += 1LL * val[i] * val[i - 1];
	}
	for (int i = val.size() - 1; i >= 0; i--)
	{
		suf[i] = suf[i + 2] + val[i] + 1;
	}
	for (int i = 0; i < val.size(); i++)
	{
		ans += 1LL*(val[i] + 1)*suf[i + 3];
	}
	printf("%lld\n", ans);
}

B. Unusual Team

An easy problem: compare the values.

1
2
3
4
5
6
7
8
9
10
11
12
13
int a,b;
void solve()
{
	sa(a),sa(b);
	if(a<b)
	{
		puts("WeWillEatYou");
	}
	else
	{
		puts("FunkyMonkeys");
	}
}

C. Cheap Kangaroo

There are $n$ people, each needing $x_i$ units of food. The plate size and cost both equal the amount of food, and everyone wants plates of the same size. Find the minimum total cost and the largest usable plate size.

The wording is convoluted, but it is another easy problem: sum for the minimum cost, and take the GCD of all values for the largest plate.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n;
int val[maxn];

void solve()
{
	sa(n);
	ll sum=0;
	repp(i,1,n)
	{
		sa(val[i]);
		sum+=val[i];
	}
	int res=val[1];
	repp(i,1,n)
	{
		res=gcd(res,val[i]);
	}
	printf("%lld %d\n",sum,res);
}

D. Magical Bamboos

There are $n$ bamboos of heights $h_i$. Decrease one bamboo by $1$ and increase every other bamboo by $1$ in each move. Can all heights eventually become equal?

An interesting problem that I overthought that night. First, several bamboos of the same height can be treated as one. Decrease the tallest by 1 and increase the rest by 1; for the tallest and second-tallest to meet, they must have the same parity. Treat those two as one and continue inductively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n;
int val[maxn];

void solve()
{
	sa(n);
	repp(i,1,n)
	{
		sa(val[i]);
	}
	sort(val+1,val+n+1);
	repp(i,2,n)
	{
		if((val[i]+val[i-1])&1)
		{
			puts("no");
			return;
		}
	}
	puts("yes");
}

E. Competitive Seagulls

Start with $n$ white points in a row. In each turn, let $L$ be the longest consecutive run of white points. A player may choose a prime length $P \le L/2$ and color such a run black. The player who cannot move loses. Given $n$, determine the outcome under optimal play.

For $n \ge 4$, the first player can color two or three middle points to leave identical parts on both sides, forcing a loss for the second player.

F. Monkeying Around

There are $N$ monkeys seated and telling jokes. Each joke has a type and range. When a monkey hears a joke it has not heard before, it leaves its seat; when it hears a familiar joke, it returns. Given all jokes, find how many monkeys are seated at the end.

Convert it into an interval problem: sort all left endpoints and right endpoints. For each monkey, maintain the jokes affecting that position; if the final joke occurs at least twice, the monkey is seated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
int n, m;
struct no
{
	int id;
	int le;
	int ri;
}node1[maxn], node2[maxn];

int val[maxn];
bool cmp1(const no&a, const no &b)
{
	return a.le<b.le;
}
bool cmp2(const no&a, const no &b)
{
	return a.ri<b.ri;
}
int num[maxn];
set<int>s;

void solve()
{
	s.clear();
	memset(num, 0, sizeof(num));

	sa(n), sa(m);
	repp(i, 1, m)
	{
		int x, in, k;
		sa(x), sa(in), sa(k);
		val[i] = in;
		node1[i].le = x - k;
		node1[i].ri = x + k;
		node1[i].id = i;

		node2[i].le = x - k;
		node2[i].ri = x + k;
		node2[i].id = i;
	}
	sort(node1 + 1, node1 + m + 1, cmp1);
	sort(node2 + 1, node2 + m + 1, cmp2);

	int c1 = 1, c2 = 1;
	int ans = 0;
	repp(i, 1, n)
	{
		while (c1 <= m&&node1[c1].le <= i)
		{
			num[val[node1[c1].id]]++;
			s.insert(node1[c1].id);
			c1++;
		}
		while (c2<=m&&node2[c2].ri<i)
		{
			num[val[node2[c2].id]]--;
			s.erase(node2[c2].id);
			c2++;
		}
		if (s.empty())ans++;
		else
		{
			int k = *s.rbegin();
			if (num[val[k]] > 1)ans++;
		}
	}
	printf("%d\n", ans);
}

G. Snake Rana

A problem from HihoCoder.

$K \le 20$; use inclusion-exclusion.

First count all rectangles. The number of rectangles of size $r \times c$ is $(N-r+1)(M-c+1)$; enumerate $r$ and $c$.
$$
\sum_{r=1}^{N}\sum_{c=1}^{M}(N-r+1)(M-c+1) = \frac{(N+1)*N}{2}*\frac{(M+1)*M}{2}
$$
Then use inclusion-exclusion: subtract rectangles containing one black cell, add those containing two, and so on.

To count rectangles containing $g$ black cells, compute the maximum and minimum $x,y$ coordinates: $maxx,maxy,minx,miny$. The result is $minx\cdot miny\cdot(N-maxx+1)\cdot(N-maxy+1)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int n,m,k;
int vx[25],vy[25];

void solve()
{
	sa(n),sa(m),sa(k);
	rep(i,0,k)
	{
		sa(vx[i]),sa(vy[i]);
	}
	ll ans=1LL*n*(n+1)/2*m*(m+1)/2;
	for(int i=1;i<(1<<k);i++)
	{
		int g=i;
		int cnt=0;
		while(g)
		{
			cnt+=(g&1);
			g>>=1;
		}
		int minx=1e9,maxx=-1,miny=1e9,maxy=-1;
		rep(h,0,k)
		{
			if((i>>h)&1)
			{
				maxx=max(maxx,vx[h]);
				maxy=max(maxy,vy[h]);
				minx=min(minx,vx[h]);
				miny=min(miny,vy[h]);
			}
		}
		ll res=1LL*minx*miny*(n-maxx+1)*(m-maxy+1);
		if(cnt&1)ans-=res;
		else ans+=res;
	}
	printf("%lld\n", ans);
}

H. Mirrored String I

An easy simulation of the statement.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int a,b;
bool check(char x)
{
	return x=='A'||x=='H'||x=='I'||x=='M'||x=='O'||x=='T'||x=='U'||x=='V'||x=='W'||x=='X'||x=='Y';
}
void solve()
{
	string x;
	cin>>x;
	int le=0,ri=x.length()-1;
	while(le<=ri)
	{
		if(x[le]!=x[ri])
		{
			puts("no");
			return;
		}
		if(!check(x[le]))
		{
			puts("no");
			return;
		}
		le++,ri--;
	}
	puts("yes");
}

I. Mirrored String II

Count the palindromic substrings.

The length is at most $1000$, so use DP.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
char val[maxn];
int dp[maxn][maxn];

bool check(char x)
{
	return x == 'A' || x == 'H' || x == 'I' || x == 'M' || x == 'O' || x == 'T' || x == 'U' || x == 'V' || x == 'W' || x == 'X' || x == 'Y';
}

void solve()
{
	memset(dp, -1, sizeof(dp));
	scanf("%s", val + 1);
	int n = strlen(val + 1);
	//cout << n << endl;
	repp(i, 1, n)
	{
		if (check(val[i]))dp[i][i] = 1;
	}
	repp(i, 2, n)
	{
		if ((!check(val[i])) || (!check(val[i])))
		{
			continue;
		}
		if (val[i] == val[i - 1])dp[i - 1][i] = 1;
	}
	
	for (int len = 3; len <= n; len++)
	{
		for (int st = 1; st <= n; st++)
		{
			int en = st + len - 1;
			if (en > n)continue;
			if ((!check(val[st])) || (!check(val[en])))
			{
				dp[st][en] = -1;
				continue;
			}
			if (val[st] == val[en] && dp[st + 1][en - 1] != -1)
			{
				dp[st][en] = 1;
			}
		}
	}
	int maxx = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = i; j <= n; j++)
		{
			if (dp[i][j] == 1)
			{
				maxx = max(maxx, j - i + 1);
			}
		}
	}
	printf("%d\n", maxx);
}

J. Lazy Physics Cat

A circle contains a triangle whose vertices are the center and two points on the circumference. Find the area of the sector after removing the triangle.

1
2
3
4
5
6
7
8
9
10
11
12
13
double len,a;
void solve()
{
	scanf("%lf%lf",&len,&a);
	double k =a;
	//cout<<a<<endl;
	a=a/180.0*PI;
	double all = PI*len*len*k/360;
	//printf("%lf\n",a);
	//printf("%lf\n",0.5*len*len*sin(a));
	double res=all-0.5*len*len*sin(a);
	printf("%lf\n",res);
}

K. Owl Geeks

By this point there had been too many easy problems. This one is also a direct simulation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
int a,b,n;
vector<int>val;
int vis[maxn];
int cnt[15];

void solve()
{
	val.clear();
	memset(vis,0,sizeof(vis));
	sa(a),sa(b),sa(n);
	repp(x,1,n)
	{
		ll v=1LL*a*x*x+1LL*b*x;
		if(v>n||vis[v])continue;
		vis[v]=1;
		val.push_back(v);
	}
	if(val.size()==0)
	{
		puts("-1");
		return;
	}
	memset(cnt,0,sizeof(cnt));
	for(int i=0;i<val.size();i++)
	{
		int k=val[i];
		int c[15];
		memset(c,0,sizeof(c));
		while(k)
		{
			c[k%10]++;
			k/=10;
		}
		int maxx=0;
		repp(j,0,9)
		{
			maxx=max(maxx,c[j]);
		}
		repp(j,0,9)
		{
			if(c[j]==maxx)cnt[j]++;
		}
	}
	int maxx=0;
	repp(i,0,9)
	{
		maxx=max(maxx,cnt[i]);
	}
	repp(i,0,9)
	{
		if(cnt[i]==maxx)
		{
			printf("%d\n",i);
			return;
		}
	}
}

L. All’s Wall That Ends Wall

A LeetCode-style trapping-rain-water problem: given heights, find the water trapped in one dimension (there is also a 2D priority-queue version). With $Q$ queries, increase the height at position $X$ by $V$ and dynamically report the trapped water.

I thought about it for a long time, could not solve it, and looked at other solutions.

Maintain an increasing sequence from left to right to calculate water volume, and similarly from right to left.

After each update, inspect the relevant positions before and after it.

The complexity of this approach still feels a little mysterious to me.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
int n,q;
ll ans;
ll sum[maxn],h[maxn];
set< pair<ll,ll> >leval,rival;
set< pair<ll,ll> >::iterator it;

int lowbit(int x)
{
	return x&(-x);
}

void add(int x,int val)
{
	while(x<=n)
	{
		sum[x]+=val;
		x+=lowbit(x);
	}
}

ll getsum(int x)
{
	ll res=0;
	while(x)
	{
		res+=sum[x];
		x-=lowbit(x);
	}
	return res;
}

ll cal(ll le,ll ri,ll pre)
{
	if(le==0||ri==n+1)return 0;
	ll t=getsum(ri)-getsum(le-1);
	ll res = 1LL*pre*(ri-le+1)-t;
	return res;
}

void upA(int x,int v)
{
	it = leval.lower_bound(mp(x,h[x]));
	if(it==leval.end())
	{
		--it;
		if(h[x]+v>it->second)
		{
			ans+=cal(it->first,x-1,it->second);
			leval.insert(mp(x,h[x]+v));
		}
		return;
	}
	int ph,px;
	if(leval.count(mp(x,h[x])))
	{
		ph=h[x];
		px=x;
		leval.erase(mp(x,h[x]));
	}
	else
	{
		--it;
		if(h[x]+v<=it->second)
		{
			ans-=v;
			return;
		}
		px=x;
		ph=it->second;
	}
	while(true)
	{
		it = leval.lower_bound(mp(x,0));
		if(it==leval.end())break;
		ans-=cal(px,it->first-1,ph);

		if(h[x]+v<it->second)
		{
			ans+=cal(x,it->first-1,h[x]+v);
			ans-=v;
			break;
		}
		px=it->first;
		ph=it->second;
		leval.erase(it);
	}
	leval.insert(mp(x,h[x]+v));
}

void upB(int x,int v)
{
	it = rival.lower_bound(mp(-x,h[x]));
	if(it==rival.end())
	{
		it--;
		if(h[x]+v>=it->second)
		{
			ans+=cal(x+1,-it->first,it->second);
			rival.insert(mp(-x,h[x]+v));
		}
		return;
	}
	int ph,px;
	if(rival.count(mp(-x,h[x])))
	{
		ph=h[x];
		px=x;
		rival.erase(mp(-x,h[x]));
	}
	else
	{
		--it;
		if(h[x]+v<it->second)
		{
			ans-=v;
			return;
		}
		px=x;
		ph=it->second;
	}
	while(true)
	{
		it = rival.lower_bound(mp(-x,0));
		if(it==rival.end())break;
		ans-=cal(-it->first+1,px,ph);

		if(h[x]+v<=it->second)
		{
			ans+=cal(-it->first+1,x,h[x]+v);
			ans-=v;
			break;
		}
		px=-it->first;
		ph=it->second;
		rival.erase(it);
	}
	rival.insert(mp(-x,h[x]+v));
}

void solve()
{
	ans=0;
	leval.clear();
	rival.clear();

	sa(n),sa(q);
	repp(i,1,n)sum[i]=0;
	repp(i,1,n)
	{
		scanf("%lld",&h[i]);
		add(i,h[i]);
	}
	int px=0,ph=0;
	repp(i,1,n)
	{
		if(h[i]>ph)
		{
			ans+=cal(px,i-1,ph);
			px = i;
			ph = h[i];
			leval.insert(mp(i,h[i]));
		}
	}
	px=n+1,ph=0;
	for(int i=n;i>=1;i--)
	{
		if(h[i]>=ph)
		{
			ans += cal(i+1,px,ph);
			px = i;
			ph = h[i];
			rival.insert(mp(-i,h[i]));
		}
	}
	char op[5];
	repp(i,1,q)
	{
		scanf("%s",op);
		if(op[0]=='P')
		{
			printf("%lld\n",ans);
		}
		else
		{
			int x,v;
			sa(x),sa(v);
			upA(x,v);
			upB(x,v);
			h[x]+=v;
			add(x,v);
		}
	}
}

M. Make Cents?

Given various currencies and exchange rates, find the final amount of money.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int c,n;
char val[15];
map<string,double>hax;
void solve()
{
	hax.clear();
	sa(c),sa(n);
	repp(i,1,c)
	{
		double num;
		scanf("%s%lf",val,&num);
		string s=val;
		hax[s]=num;
	}
	hax["JD"]=1;
	double sum=0;
	repp(i,1,n)
	{
		double num;
		scanf("%lf%s",&num,val);
		string s=val;
		sum+=1.0*num*hax[s];
	}
	printf("%.6lf\n",sum);
}
On this page
2017 ACM Arabella Collegiate Programming Contest
  1. A. Sherlock Bones
  2. B. Unusual Team
  3. C. Cheap Kangaroo
  4. D. Magical Bamboos
  5. E. Competitive Seagulls
  6. F. Monkeying Around
  7. G. Snake Rana
  8. H. Mirrored String I
  9. I. Mirrored String II
  10. J. Lazy Physics Cat
  11. K. Owl Geeks
  12. L. All’s Wall That Ends Wall
  13. M. Make Cents?