I recently participated in Coding Quest, a programming competition created by Paul Baumgarten that is aimed at secondary students with challenges based around A Level/IB level curriculum and difficulty. There are 10 challenges released over the course of two weeks, one every weekday, and with all programming contests the faster you solve the problem the better your rank. However, this differs from the usual slightly in that you do not submit your program for remote judging, but a single answer to a large test case. I did this competition last year, but at that time I was just starting competitive programming and it took me sometimes days to figure out the solution to certain problems. My goal this year: after all this progress, solve every problem on the day of release and get to the top 10 on the leaderboards (out of 1318 people). Thus begins a thrilling tale of competition, time, and googling.
Week 1
The first week, the problems are all mostly messing with data, which is quite different from algorithmic challenges. So, the problems were fairly simple and I won’t go over them here.
Week 2 – Day 3
Now the fun begins! Admittedly the first week was a bit rough, I was around 25th at that point, so I needed to work hard if I wanted to get to the top 10. After the first two days (2D arrays and a snake game simulation), I was now 20th. The third day, being part of the school Orchestra, I had to attend a concert starting at 6pm, exactly one hour before Coding Quest. As there existed an intermission, I knew that the concert would certainly run until around 8pm. But the intermission also meant my only hope: I could only hope that the 15-minute interval would begin slightly before 7, and allow me to finish the problem.
The intermission started at the best time possible. I got my code files open and begun: it was a travelling salesman problem. I had never studied this problem before, so as there were only 12 nodes I just opted for a DFS solution, as I knew that the program would run in less than 10 seconds. The rule of thumb was that if the time complexity was \(O(10^7)\)(10 million), then the program would run in approximately 2 seconds. Using google, I calculated that \(11!\) was just under 40 million, so giving it a little room I ended up at 10 seconds.
That’s all well and good, unfortunately what wasn’t was my program. Here it was:
Broken code 🙁 . Spot the mistake!
#include <iostream>
using namespace std;
int ans = 1000000, dist[13][13];
bool vis[13];
void dfs(int cnt, int cur, int d) {
if (cnt >= 11) {
ans = min(ans, d + dist[cur][1]);
return;
}
for (int i = 2; i <= 12; i++)
if (!vis[i]) {
vis[i] = true;
dfs(cnt + 1, i, d + dist[cur][i]);
vis[i] = false;
}
}
int main() {
freopen("input.txt", "r", stdin);
for (int i = 1; i <= 12; i++)
for (int j = 1; j <= 12; j++)
cin >> dist[i][j];
dfs(1, 1, 0);
cout << ans;
return 0;
}Then the intermission was over, and I had to go back on stage, waiting for another hour to fix my code. As soon as it was over, I grabbed my laptop and (oh, the concert went fine by the way) flipped my laptop open. In a single minute I had discovered the bug.
It was an extra minus sign – the depth limit in my DFS function was wrong.
As there were 12 nodes, after I had travelled through all of them I had to go back to the beginning. In terms of my function, It should be cnt > 11, and sure enough I completed the problem with ranking 17th. My career was over! I would never forgive myself for overlooking such an elementary thing!
Just kidding, these sorts of things pop up a whole lot. In fact, it was these simple mistakes that kept me down in the first week. I could go on and on about them, not just in programming too. Moving on.
Week 2 – Day 4
The penultimate challenge was one of binary trees. I had not really worked with them before, but from my experience with graphs I thought this challenge was decently straightforward. The goal was to multiply the maximum width(of a layer) by the depth of the tree. I created a map with an integer to a pair of integers, representing the left and right leaf nodes. I didn’t use arrays to represent the tree because the size of the labels of the nodes would crash my computer. I have tried initialising an array with a trillion indices before, don’t do that.
Here’s my code, read the question if you want to understand the tree creation function.
#include <iostream>
#include <queue>
#include <map>
#define int long long
using namespace std;
map<int, pair<int, int> > tree;
int root, width[10001], depth, ans;
void dfs(int cur, int pos) {
if (cur < pos) {
if (!tree[pos].first) tree[pos].first = cur;
else dfs(cur, tree[pos].first);
} else {
if (!tree[pos].second) tree[pos].second = cur;
else dfs(cur, tree[pos].second);
}
}
struct node {
int val, layer;
};
queue<node> q;
signed main() {
freopen("input.txt", "r", stdin);
for (int i = 1; i <= 10000; i++) {
string hex;
cin >> hex;
int a = stoll(hex, 0, 16);
if (i == 1) root = a;
else dfs(a, root);
}
q.push((node){root, 1});
while (!q.empty()) {
node cur = q.front();
q.pop();
depth = max(depth, cur.layer);
width[cur.layer]++;
if (tree[cur.val].first)
q.push((node){tree[cur.val].first, cur.layer + 1});
if (tree[cur.val].second)
q.push((node){tree[cur.val].second, cur.layer + 1});
}
for (int i = 1; i <= depth; i++)
ans = max(ans, width[i]);
cout << ans << ' ' << depth << ' ' << ans * depth;
return 0;
}Ranking: still 17th.
The Final Challenge
Well, seeing as the previous challenges weren’t too much of a challenge, I was quite confident in my ability to pick up some real places now. As to the difficulty of the challenge, well, it was pretty straightforward – finding the minimum distance to traverse a graph from point A to point B. I quickly (in 20 minutes) solved the problem. It really was quite anticlimactic – a simple DFS did the trick, though of course Djikstra would be a more optimal solution. Unfortunately I didn’t save my code for this problem, so it is left as an exercise to the reader.
Conclusion
13th’s good enough I guess.
For my part I’ve realised now that rank number one isn’t an achievement, it’s a prison which forces you to dedicate your life to defending a temporary title. But now, with the war finally over . . .
I’m free.
Technoblade – Skyblock Potato War 3
