Competitive Programming for Kids (2024-03-05)

breadcrumbs
1

We are working with my daughters (10 and 7 year old) on competitive programming. (This would be a great book title: “Competitive Programming for Kids” – maybe even adults would enjoy it.) We are creating a dedicated curriculum to make it easy for kids (1st through 5th grades) to dip their toes into CodeForces style programming.

Here is an example:

Problem

The 1st grade teacher at school needs to send an email to all student’s parents regarding open house. The text of the message will be “Dear (name of parent),\nCome to open house tonight at 6pm and see (name of student)'s work.”

Input

The teacher has the list of students, parent, and parent email. This is all stored in a file where the first line contains the number of students in the class and the remaining rows are comma-separated values of student name, parent name, parent email. It would look something like this:

4
student,parent,email
joey,cara,cara@example.com
sam,otto,o@example.com
zoe,beverley,bev@example.com

Output

The output should be the email and text for each email:

cara@example.com|Dear Cara,\nCome to open house tonight at 6pm and see Joey's work.
...

Bootstrap Code

We have not decided whether I’ll use Python or C++ (C) for this. Leaning towards C. It may be easiest to provide (and explain) the boilerplate code that would bootstrap this problem in a CodeForces-like environment.

#include <iostream>
using namespace std;
int main() {
    int numLines;
    cin >> numLines;
    // Solve the problem here
    cout << numLines; // remove this
   return 0
}

Here is how Gennady Korotkevich bootstraps a problem: touristream 019: SNWS 2022 Round 5.

We absolutely adore and admire the masterful use of Far Manager in this particular video and in general by Gennady (and many other competitive programmers from Eastern Europe). Here is a reminder on how to use Far Manager as IDE from Codeforces.

image

We enjoy browsing through Gennady’s CodeForces blog posts and problems solved. Here is Gennady’s solution to 1785A - Monsters (easy version)

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    sort(a.begin(), a.end());
    vector<int> b(n);
    b[0] = 1;
    for (int i = 1; i < n; i++) {
      b[i] = min(b[i - 1] + 1, a[i]);
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) {
      ans += a[i] - b[i];
    }
    cout << ans << '\n';
  }
  return 0;
}

We love Gennady’s succinct code, use of short (if unexplainable) variable names. This is perfect for competition-grade code!

What is Competition Grade code? It is meant to be read once (if ever) by one person and executed hundreds or thousands of time (on test cases) over the course of a few seconds. After this - the code is never ever looked at. No need to maintain it.

This is very similar to Startup Demo Code – write it fast to demo/sell/raise, then throw away and then actually build (hopefully) production-ready system.

but we digress…

Back to Competitive Programming for Elementary School Children

What we think this would teach elementary school children?

  • what main() means
  • why we need int in front of it, which would be a gateway into Operating Systems
  • what stdin and stdout is
  • how to create variables
  • how to print to stdout

Challenges with using C++

Splitting the input by new line is taken care of by cin >> line, but splitting comma is not trivial. Perhaps the most readable and easy to explain code would be:

vector<string> splitByComma(const string& str) {
    vector<string> result;
    stringstream sstream(str);
    string token;

    while (getline(sstream, token, ',')) {
        result.push_back(token);
    }

    return result;
}

So we could end up with something that is almost explainable to a 5th grader:

#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
vector<string> splitByComma(const string& str) {
    vector<string> result;
    stringstream sstream(str);
    string token;

    while (getline(sstream, token, ',')) {
        result.push_back(token);
    }

    return result;
}
int main() {
    int numLines;
    string line;
    cin >> numLines;
    cout << numLines << endl;
    for (int i=0; i<numLines; i++) {
        cin >> line;
        cout << line << endl;
        auto words = splitByComma(line);
        for (auto word : words) {
            cout << word << endl;
        }
    }
    return 0;
}

Python though…

import sys
for line in sys.stdin:
    line_without_n = line.strip('\n')
    words_in_line = line_without_n.split(',')
    for word in words_in_line:
        print(word)

Python is very easy to explain.

Would this lead into the exploration of the Operating System and how the computer works? We worry - it won’t!

Would teaching Python first cause dislike for C/C++? We worry - it will.

Let’s try and iterate on this curriculum!
Will post updates…