Now that the Philippine IOI team has been selected and this year's competition cycle is ending, I'd like to post a series detailing my participation in our national olympiad's organizing team this year. (I'm also doing this because my contribution is dropping! That's why it's a series, so I get even more contribution. I will do anything for imaginary internet points.)
This year, I helped write, make data for, and test problems for our national olympiad. I hope that you'll learn something about problemsetting or testing from this series. And if not, then I hope to introduce you to our olympiad's excellent problems. And if you don't find our problems interesting, then this post isn't for you and I'm sorry for wasting your time.
In this first part, I'll talk introduce our olympiad, the NOI.PH, and how I contributed to our elimination round. Here's a picture I made for the elimination round that will maybe convince you to read more:
Note that this is a somewhat long post; I expect it to take around fifteen minutes to read. There are also a lot of pictures in this post. .
The NOI and me
The National Olympiad in Informatics – Philippines, or the NOI.PH, is a young olympiad. It started in 2014 when a couple of people got together to organize it.
I first joined the NOI unofficially in 2016, and a good performance convinced me to join in both 2017 and 2018. I qualified for the IOI both years, but was only able to go in 2018, and then I did really poorly (which is a story for another time). I also graduated from high school in 2018. Right now, I'm taking a break before I start college in August, which is why I decided to help as much as I can in the NOI, because I'll be busier when college starts.
A high school student goes through several rounds in the selection process for the IOI team. You can read about it on the website, so I'll just summarize what happened this year:
There was a nine-day, fourteen-problem elimination round held online last January.
The top 30 joined in a two-day, on-site contest, held last April. Each day had five problems for five hours.
The top 10 participated in online training for six weeks. Each week had a problem set and a five-hour contest at the end of the week.
Then there was an intensive week for four days. Each day had a five-hour contest.
Immediately after was an inhouse camp for three days. The first two days had two five-hour contests each. The last day had a six-hour contest.
These were then used as the basis to pick our IOI team: spacewalker, Something_hacker, dsjong, and Steve120.
In this post, I'll talk about our preparations for the elimination round, what we did right, and what we did... not-as-right.
Preparing early, kind of
The original schedule for the elimination round would be from January 4 to 13. The NOI president, verngutz, sent out emails to a bunch of people asking for volunteers for the scientific committee: problem proposals, making test data, testing problems, and writing stories. This was in early November, which is two months early. Preparing contests early is good!
I'll talk more about these roles later on, but you might be wondering about that last role: writing stories. One of the things that makes NOI.PH problems unique are stories that are funny, punny, or make references to Philippine pop culture or current events. Here's an example from 2018, for all of you tsunderes out there.
For the eliminations round, I volunteered to test problems and write stories. Later that November I sent five or six problem proposals for the eliminations. By early December I get feedback from verngutz. All of my proposals got rejected except for one. (Press F to pay respects.)
The working name for the proposal that made it was White Box, because it was supposed to be the opposite of the IOI problem Black Box. In White Box, you are given a $$$1 \times n$$$ box with reflectors. And instead of letting you put balls in the box and listen, the problem picks the balls for you and tells you the results. You then have to give the layout of any box that satisfies this.
I learned from this that coming up with ideas is easy, but coming up with good ideas is harder. If you try to write a problem around an algorithm, it could be too easy. If you try to write a problem around the real world, it could be too hard. White Box worked because it took an existing problem and reversed it, which was one of the ideas given in a Codeforces round. That is how I came up with the problem.
Then nothing happens until early January, due to several real-world things happening. This was very bad for the round! So much for preparing early, huh?
Wonderful spreadsheets
The eliminations round was originally scheduled from January 4 to 13. But it was already January 3 and nothing was happening, so I was worried. On January 6, verngutz messaged all of the test data makers and the story writers, telling us that the round would be postponed to January 18.
Ten of the problem ideas were done. Of these, two of the problems had data. The remaining five problem ideas would be written by robinyu. So this gave us two weeks to prepare data, write the stories, and test the remaining problems. Just to make it clear, two weeks is not a lot of time for this, and this is definitely something to avoid.
I was then introduced to the glorious, amazing, beautiful, wonderful, problem sets checklist.
To make the problemsetting and testing as organized as possible, the NOI.PH uses a spreadsheet as a checklist. On the top row are the names of the problems: here you can see the working names of the ten problem ideas. The first row is the story writer's task. The second row is the task of the person who makes the test data. Then, the remaining rows are the tasks of the tester. Note that one of the problem names is hidden. I will refer to this problem as problem $$$X$$$, because it eventually got removed from the problemset.
As I didn't know anything about problemsetting and testing yet, I decided to claim some problems to write the stories for. The first story I wrote was Super Rangers, which is a reference to the Power Rangers.
Then I write the stories for problem $$$X$$$, Exchange Gift, and Evening Gown, which are both references to Philippine culture. To write these two stories, I had to do research on the major news stories in the Philippines over the past year. (I went on Reddit to do research! That's new.)
You may have also noticed that the NOI.PH problems I've referenced so far have a picture at the beginning, which we call the header. All recent NOI problems have a header. Like the stories, a header is part of what distinguishes NOI problems, to make reading the statement more enjoyable. (This is not as big of an issue as putting pictures in Codeforces rounds, since speed is much less important for our contests.)
I think I am somewhat good at graphic design, so I volunteered to make most of the headers for the elimination round as well. On January 10 and 11, I make the headers for eight of the problems:
Let me make it clear at this point that the NOI.PH prioritizes problemsetting and testing. It's just that for the eliminations round, most of my contribution was writing the stories and making pictures, so that will be the nature of this post. In later posts in this series, you'll get to see just how much the NOI cares about setting good problems.
To emphasize the importance of testing, let's talk about how I tested my first problem!
Testing my first problem
One week before the round, the data for four of the problems have been made, and two of these has been tested. Then verngutz has made assignments for whom will test which problems. I am assigned to test one of the problems, Lots of Cookies. The spreadsheet looks like this now:
Let me explain our process of problemsetting and testing as it's done in the NOI. A similar process is probably done to prepare problems for most programming contests.
The problemsetter or the setter comes up with an idea. They write an initial statement.
The test data maker makes the test data for the problem. This involves writing the validator, checker, generators, and a model solution. I will explain what each of these are in the second part of this series, when I talk about making test data for the NOI.PH finals.
The tester then tests the problem by solving it, without asking for hints, if possible. They write a solution and check if it passes the test data. They check if the test data follows the constraints given in the problem statement. They make sure that slow solutions to the problem are TLE, and that incorrect heuristics get WA.
It is often the case that the setter and test data maker are the same person, and I will sometimes use "setter" to refer to both. However, the test data maker and the tester have to be different people. This redundancy is the key part of the setter–tester model, which helps reduce the amount of mistakes as much as possible. Therefore, making a problem involves at least two different people.
Testing a problem in the NOI.PH is as simple as filling out the column in our spreadsheet!
So to test Lots of Cookies, I:
carefully read the statement. Here's a summary of the original statement. Define $$$x_k = \left\lfloor\frac{x}{k}\right\rfloor$$$. You're given two fixed integers $$$a$$$ and $$$b$$$. Consider $$$\sum ax_k^2 + bx_k$$$, where the sum is taken over $$$k = 1, 2, \ldots$$$. Find this sum for $$$Q$$$ different values of $$$x$$$.
tried to solve it. While doing so, I saw that the sequence $$$\sum x_k$$$ for $$$x = 1, 2, \ldots$$$ was in the OEIS! And so was the sequence $$$\sum x_k^2$$$, and the OEIS gave a nice formula for both of these as well. Because the eliminations was a long contest, and contestants were allowed to look at resources, this was unacceptable. So Shisuko had to rewrite the problem to its current statement, and make all the data again.
carefully read the new statement, where $$$ax_k^2 + bx_k$$$ was changed to $$$ax_k^2 \oplus bx_k$$$ instead, where $$$\oplus$$$ is binary XOR. No obvious issues to me, and I did not see anything wrong with it aside from some minor typos. (kevinsogo eventually spotted that the summation notation needed to be explained.)
tried to solve it. I quickly put together the brute force that solved the first subtask, and found the full solution. However, I could not find the intended solution for the second subtask, which was one of my responsibilities. I also noticed that the solution was simpler when $$$a = 0$$$ or $$$b = 0$$$, because the answers were in the OEIS, as mentioned earlier. So I suggested to make a subtask for these.
checked that the test data followed the constraints in the problem statement, by checking the validator. It did, which was good.
checked the test data to make sure that edge cases were present. (In other words, checking if the constraints were tight.) In this problem, it meant that the minimum and maximum values for each of the variables was present in some test. They were there, which was good.
wrote a brute force solution, in C++, that passes the first subtask, and made sure it didn't pass the next subtasks. It did not, even after several constant optimizations, which was good.
wrote a full solution to the problem, in C++. It passed all the subtasks, but it was very close to the original time limit of 1 second. Hence the time limit for C++ was turned to 4 seconds instead.
wrote variations on the full solution that used slow input and output, since the input and output were large. These were TLE. So a note about using fast I/O was added to the statement.
changed the full solution to not use \t{long long}. It failed, which is good.
translated my full solution to Python. It failed, but this was okay, since we don't guarantee that the problem can be solved in Python.
asked what the intended solution to the second subtask was. Apparently it's an $$$O(Q\sqrt N)$$$ solution by summing over constant $$$x_k$$$.
wrote a solution for the second subtask to the problem, in C++. It passes the first two subtasks but failed the next subtasks, even after constant optimization, which was good.
wrote a solution for the third and fourth subtasks to the problem, in C++. This was after Shisuko accepted by suggestion and made test data for these subtasks.
And that was most of the entries in the column. So that's how we test a problem. You read the statement as carefully as you can, making sure that it's as clear and unambiguous as possible. Then you basically write a bunch of solutions, some correct, some slow, some wrong, solving different subtasks, and make sure that they each get the expected verdict.
It's not too different from what you do as a contestant, but the crucial difference is that you're trying to come up with wrong and partial solutions as well. Sometimes, this just means solving the problem normally. But sometimes, this also means trying to think what the common mistakes are.
Thorough problem testing is very important. You can see how much the problem itself improved during the process of problem testing. The whole process took around two hours, ignoring the time waiting for Shisuko to update the data. It's worth it! After all, the reason NOI.PH problems are well-polished is because of our testing process :D
We are definitely completely totally prepared
It is January 12 now, five days before the contest. We still have five problems left to fill out of the fifteen, and four more problems to make data for. This is very very bad and this shouldn't happen at all.
While reading the statement for one of the problems, Dagohoy Rock, I noticed an issue. The original statement had the same disallowed sequence LDL for everything, so each test case only had the input $$$N$$$. But this made the answers to the problem a sequence in the OEIS again! So Shisuko again rewrote the problem and remade the data. Take note, problemsetters and testers: you might want to check if the answers to your problem are in the OEIS.
Then, in January 13, kevinsogo comes to the rescue and adds another problem: Spratly Islands. Then, robinyu prepared the data for two more problems, Saishuu Shinpan and Almost Original. Then, the next day, verngutz prepares the data for Problem $$$X$$$, robinyu prepares the data for Skyscaping, and kevinsogo adds the final problem, Packing Problem. By now, the spreadsheet looks like:
Then, verngutz tells me that the statement for Super Rangers is wrong. I apparently misinterpreted the original problem statement, so my story needed a lot of fixing. After several rounds of going back and forth with kevinsogo, I get an acceptable problem statement. So if you're wondering why the Swords have wires joining them, well, that's the reason.
Now let me talk about the issue with Problem $$$X$$$. The issue with Problem $$$X$$$ is that, other than the intended solution, there was a weak heuristic solution that did work, but shouldn't work. And the test data maker, verngutz, couldn't figure out how to make test data against this. So on January 16, three days before the round, it got scrapped and replaced with another problem. I will call this problem Problem $$$Y$$$.
The final stretch
It is now the midnight before January 17. It is the night before the eliminations round, and the spreadsheet is nowhere being finished. This is very, very bad.
Two of the problems don't have data, and only three of the problems have been tested. I stay up until 3 AM writing the statements for Packing Problem, Spratly Islands, and Problem $$$Y$$$.
I want to take a moment to talk about the statement for Packing Problem. It is actually the third in a series of problems with a similar story, and I consider it a tribute to their story writer, guissmo. I am very proud of this statement because I managed to make some good puns, while still making a natural story for the problem. (If you don't get the puns, well... don't ask me, because I'm not telling.) Anyway, that's just a minor thing.
Then kevinsogo, in his infinite awesome power, tests ReMotion, Saishuu Shinpan, Skyscaping, and Almost Original, as well as prepares data for Spratly Islands, all in the same evening! Where would the NOI.PH be without his skills?
Since I don't have the capability to contribute to the test data preparation or the testing, I just help make more illustrations. I felt sad that I couldn't contribute more substantially, but anything helps, right?
It is now the day itself, January 18. verngutz and kevinsogo prepare the data for Super Rangers. That morning, the spreadsheet looked like this:
Problem $$$Y$$$ still did not have any data. Seven problems still need testing; although I could test them, I didn't think I had enough time. The problem statements are also missing sample explanations and illustrations, which was my job, and which I haven't done. So clearly, we were definitely, completely, totally prepared.
Haha, no we weren't. This was really bad, and at this point we were guaranteed to have a mistake. We could only hope that these mistakes would be caught and fixed during the round, or at least not affect the rankings if they aren't caught.
I was then assigned to test Spratly Islands. And through some magical power, I managed to solve it in time, so I managed to do some testing that afternoon. Then, kevinsogo marks Exchange Gift as tested. I make as many graphics as I can make in three hours, because what else can I do?
It was clear that there was not enough time to make data and test Problem $$$Y$$$, so it was decided to be postponed and used a different time. That's the reason why this year's eliminations only had fourteen problems, compared to the usual fifteen.
And then verngutz uploaded the problems to HackerRank, and the round began.
Pulling through
The moment the round opened, I read the problems that robinyu wrote, because I haven't read their statements yet. I offered to make headers for them, and he agreed, so we managed to push the following headers relatively quickly:
Over the next few days the remaining problems would eventually be tested, and editorials would be written. I wrote the editorials for Evening Gown, Exchange Gift, and Spratly Islands. I am very proud of my editorial for Evening Gown, which you can read here.
Our guaranteed mistakes did appear. There was a small issue with the checker for Exchange Gift, which was caught and fixed immediately after the contest. I also realized that the test data for Evening Gown was weak, which wasn't caught until weeks after the contest. Thankfully, neither of these affected the rankings that much.
These should have been caught during the testing phase, which was something we did wrong, because these were two of the problems that weren't tested that well. Mistakes like these are unavoidable. At least the thorough testing that did happen helped avoid many more possible mistakes.
That's one thing that we need to improve on next year: making sure the problems are more thoroughly tested. And the best way to do this is starting early, much, much earlier than two weeks in advance, especially for a fifteen-problem round like the NOI.PH Eliminations.
So that was my experience volunteering to organize this year's NOI.PH elimination round! In the end, I set one problem (Exchange Gift, which I am really proud of), and tested two problems (Lots of Cookies and Spratly Islands). It's not much, but I like to think I helped by writing the stories and making illustrations as well.
I hope you learned something! And if not, well, let me recommend some problems to try from the elimination round that I think were nice:
My problem, Exchange Gift. It's pretty easy, but I think it's a fun problem that's instructive for a beginner. There's a very, very nice way to solve it without writing a long program. For example, my Python solution is only thirty lines long. (With an average of 35 characters per line. It is really thirty lines long, no tricks.)
I thought Spratly Islands was nice. It's an interesting twist on a classic concept.
Yet Another Packing Problem, the hardest problem from the eliminations, is very fun. It was one of the two problems that none of the (official) contestants solved during the contest.
In the next post in the series, I'll talk about how I made test data for my first few problems, setting a problem for the NOI.PH finals, and other preparations we made.
