CCC 2020

Posted Mar 25, 2020

By Eric Pei 10 min read

This year’s Canadian Computing Competition was held on February 12, 2020. Here I will dissect the results of the Senior Division contest.

Contest Analysis

CCC 2019	CCC 2020

This year’s S1 and S2 average scores were significantly lower than last year’s. This is because the difficulty of these early problems has increased. S3 had a higher average score but a lower non-zero average score. I’m not sure what to make of this, but know that the nature of this year’s S3 is different. Last year’s S3 tested the contestant’s ability to come up with an “ad hoc” solution and then debug it. This is in contrast to this year’s S3 which (straightforwardly) tested for knowledge of string algorithms. As seen in the non-zero scores, S4 and S5 were easier this year.

CCC 2019	CCC 2020

Due to an easier S4 and S5, the 2020 CCO cut-off is 57 and 25 contestants have been invited. In comparison, last year’s cut-off was 48 and 31 were invited.

This year’s Honour Roll cut-off of 37, down from last year’s 39.

Problem Analysis

S1: Surmising a Sprinter’s Speed

Solution: sort the points by time. Then, loop over consecutive pairs to find the constant speed in each interval. The answer is the maximum of the speeds.

Time complexity: $\mathcal{O}(N \log(N))$.

S2: Escape Room

Solution: Perform a depth-first search (DFS) on the cells. There are $N \cdot M$ cells and individually finding the factors of each number has complexity $\mathcal{O}(\sqrt{\text{max_cell_number}})$. This results is a loose upper bound of $NM \cdot \sqrt{\text{max_cell_number}} = 10^3 \cdot 10^3 \cdot \sqrt{10^6} = 10^9$ operations. Although it appears that this solution cuts close to the time limit, it can pass.

For a faster solution, observe that when the cell at $(i, j)$ has value $v$, a cell of product $i \cdot j$ can reach a cell of product $v$. Let us add an edge from node $i \cdot j$ to node $v$. The answer is “yes” iff there exists a path from node $1$ to node $n \cdot m$.

Time complexity: $\mathcal{O}(NM)$ or $\mathcal{O}(NM \sqrt{ \text{max_cell_number} })$.

S3: Searching for Strings

Let $S$ be a substring of $H$ with length $|N|$. To check whether $S$ is a permutation of $N$, keep a count of each of the 26 letters of the alphabet. If the counts of $S$ and $N$ all match, then they are permutations of each other. To do this quickly, loop through the $S$s from left to right. This way, at most two characters are added or removed each time we shift right by one character. This lets us know which substrings can satisfy the “permutation” requirement.

Now we will find the number of distinct subtrings $S$ that work. Let $T$ be the set of all such $S$. To eliminate duplicates, we need a quick way of comparing the elements of $T$. This can be done quickly by using a rolling hash. We insert valid $\text{hash}(S)$s into set $T$. Finally, the answer is the cardinality of $T$.

Time complexity: $\mathcal{O}(|H|)$ or $\mathcal{O}(|H| \log(|H|))$.

S4: Swapping Seats

First, let us solve the problem where the $1^{st}$ person and $N^{th}$ person are not adjacent. After all our swaps, segments of $A$, $B$, and $C$ type people will be contiguous. The order that these segments appear in is a permutation of $ABC$ (e.g. $ABC$, $ACB$, $BAC$, …). We can try all 6 permutations. In each permutation, the table is split into 3 segments that will eventually be occupied $A/B/C$ people. Let’s call these “final groups”. If a person of group $X$ is already in the final group of $X$, there is no point in moving him. If an $X$ and a $Y$ person can end up in their correct final groups by swapping the two, swap them. Otherwise, we will have a non-negative number of triples of three people—one from each group—who can all end up where they need to be in $2$ swaps (this looks like shifting $(X, Y, Z)$ to $(Y, Z, X)$). This algorithm is guaranteed to give the minimum number of swaps needed. Notice that all we care about is which group each person is from and which $A/B/C$ final segment he is currently in. If we go back to the circular case and everyone shifts left by one seat, only three people will be in different final groups. Thus, we can shift the table $N$ times and check the required swap-count each time. The answer is the minimum of the swap-counts.

Time complexity: $\mathcal{O}(N)$.

S5: Josh’s Double Bacon Deluxe

Let $P_i$ be the probability that John does not get his burger if the $i^{th}$ person does not get his burger. The base case is $P_N = 0$. For all $i$, $ i\neq 1$, if $b_i = b_1$, $i$ will take the coach’s burger and everyone after $i$ gets the correct burger. Otherwise, if there exists a person $j$ after $i$ who ordered the same burger as person $i$, person $i$ will take person $j$’s burger. In this case, $P_i = P_j$. Otherwise, $i$ will take a remaining burger at random. If $i$ takes the coach’s burger, then everyone behind $i$ will get his own burger. Otherwise, if $i$ takes $j$’s burger, then the probability in this case is $P_j$. Here, $P_i = \frac{1 + \sum_{j = i+1}^{n} {P_j}}{n-i+1}$. We can also use this recurrence to calculate $P_1$, which is our final answer.

\[P_i=\begin{cases} 0& \text{if } i = N\\ 1& \text{if } i \neq 1, b_i = b_1\\ P_j& \text{if } i \neq 1, \exists \,\, j \, | \, j > i, b_j = b_i\\ \frac{1 + \sum_{j = i+1}^{n} {P_j}}{n-i+1}& \text{otherwise} \end{cases}\]

Finding whether there exists a $j$ for a given $i$ can be done in $\mathcal{O}(1)$ many different ways. Finding the suffix sums of $P$ can be done in $\mathcal{O}(1)$ each time if we find $P_i$s in decreasing order of $i$.

Time complexity: $\mathcal{O}(N)$.

Summary

I enjoyed solving this year’s CCC problems and I hope that you enjoy them as well. My solutions in C++ are available here and at the bottom of the page.

My Solutions in C++

S1

  
// S1 solution in O(N log N)
#include <bits/stdc++.h>
using namespace std;

pair<double, double> a[100005];
int n;
double ans;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i = 0; i < n; i++)
		cin>>a[i].first>>a[i].second;
	sort(a, a+n);
	for(int i = 1; i < n; i++){
		ans = max(ans, abs(a[i].second-a[i-1].second)/(a[i].first-a[i-1].first));
	}
	cout<<fixed<<setprecision(9)<<ans<<'\n';
}

S2

  
// S2 solution in O(NM)
#include <bits/stdc++.h>
using namespace std;
constexpr int MM = 1e6+5;

int n, m;
bool vis[MM];
vector<int> adj[MM];

void go(int u){
	if(u == n){
		cout<<"yes\n";
		exit(0);
	}
	vis[u] = 1;
	for(int i: adj[u])
		if(!vis[i])
			go(i);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i = 1,k; i <= n; i++){
		k = i;
		for(int j = 1,v; j <= m; j++, k += i){
			cin>>v;
			adj[k].emplace_back(v);
		}
	}
	n *= m;
	go(1);
	cout<<"no\n";
}

S3

  
// S3 solution in O(|H| log |H|)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MM = 2e5+5;

int n, m, cnta[30], cntb[30];
char sa[MM], sb[MM];
set<pair<ll, ll>> st;
ll base = 131, mod = 1685518853;
ll base2 = 131, mod2 = 1494318097;
ll h[MM], p[MM], h2[MM], p2[MM];

void go(int j){
	for(int i = 0; i < 30; i++)
		if(cnta[i] != cntb[i])
			return;
	ll hs = ((h[j] - h[j-n]*p[n])%mod+mod)%mod;
	ll hs2 = ((h2[j] - h2[j-n]*p2[n])%mod2+mod2)%mod2;
	st.insert({hs, hs2});
}

int main(){
	scanf("%s %s", sa+1, sb+1);
	n = strlen(sa+1), m = strlen(sb+1);
	p[0] = p2[0] = 1;
	for(int i = 1; i <= m; i++){
		p[i] = p[i-1]*base%mod;
		h[i] = (h[i-1]*base + sb[i])%mod;
		p2[i] = p2[i-1]*base2%mod2;
		h2[i] = (h2[i-1]*base2 + sb[i])%mod2;
	}
	for(int i = 1; i <= n; i++){
		cnta[sa[i]-'a']++;
		cntb[sb[i]-'a']++;
	}
	go(n);
	for(int i = n+1; i <= m; i++){
		cntb[sb[i]-'a']++;
		cntb[sb[i-n]-'a']--;
		go(i);
	}
	printf("%ld\n", st.size());
}

S4

  
// S4 solution in O(N)
#include <bits/stdc++.h>
using namespace std;
constexpr int MM = 1e6+2;

int n, cnt[3][3], ans = 1e9, num[3], na, nb, nc;
char s[MM], ins[MM];
int aa[] = {0, 1, 2};

void go(){
	int tot = n-cnt[0][0]-cnt[1][1]-cnt[2][2], res = 0;
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < i; j++){
			int sub = min(cnt[i][j], cnt[j][i]);
			res += sub;
			tot -= sub*2;
		}
	}
	assert(tot % 3 == 0);
	res += tot/3*2;
	ans = min(ans, res);
}

void run(){
	memset(num, 0, sizeof num);
	memset(cnt, 0, sizeof cnt);
	for(int i = 0; i < n; i++){
		s[i] = aa[ins[i]];
		num[s[i]]++;
	}
	na = num[0], nb = num[1], nc = num[2];

	auto gp = [](int i){
		if(i < na)
			return 0;
		if(i < na+nb)
			return 1;
		return 2;
	};

	for(int i = 0; i < n; i++)
		cnt[gp(i)][s[i]]++;

	go();

	auto at = [](int i){
		i %= n;
		if(i < 0) i += n;
		return i;
	};

	for(int sh = 0; sh <= n; sh++){
		cnt[0][s[at(na-1-sh)]]--;
		cnt[1][s[at(na-1-sh)]]++;
		
		cnt[1][s[at(na+nb-1-sh)]]--;
		cnt[2][s[at(na+nb-1-sh)]]++;
		
		cnt[2][s[at(n-1-sh)]]--;
		cnt[0][s[at(n-1-sh)]]++;
		go();
	}
}

int main(){
	scanf("%s", s);
	n = strlen(s);
	for(int i = 0; i < n; i++){
		s[i] -= 'A';
		ins[i] = s[i];
	}

	do{
		run();
	} while(next_permutation(aa, aa+3));
	
	printf("%d\n", ans);
}

S5

  
// S5 solution in O(N log N)
#include <bits/stdc++.h>
using namespace std;
constexpr int MM = 1e6+2;

int n, a[MM];
map<int, int> mp;
double dp[MM], suf;

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", a+i);
	
	if(a[1] == a[n])
		return printf("1\n"), 0;

	mp[a[n]] = n;
	
	for(int i = n-1; i > 1; i--){
		if(a[i] == a[1]){
			dp[i] = 1;
			mp[a[i]] = i;
		}
		else if(mp[a[i]])
			dp[i] = dp[mp[a[i]]];
		else
			dp[i] = (suf+1)/(n-i+1);
		
		mp[a[i]] = i;
		suf += dp[i];
	}
	
	printf("%.8lf\n", accumulate(dp+2, dp+n, 1.0)/n);
}

Contests

CCC

This post is licensed under CC BY 4.0 by the author.